Расстояние между двумя кривыми

[JennyO]

Помогите, пожалуйста, разобраться со следующей задачей:

Даны две кривые, заданные точками(координатами этих точек).
Надо найти кратчайшее растояние между этими кривыми.

Идея состоит в том, что мы разбиваем каждую кривую одинаковыми отрезками, координаты которых можно определить.

Кратчайшее растояние будет состоять из суммы длин отрезков, соединяющих эти новые точки обеих кривых.
При этом все точки обеих кривых должны быть соединены между собой и одна точка первой кривой может быть соединена сразу с несколькими точками второй, если это уменьшает суммарное растояние между кривыми.

Начинается поиск с соединения первых двух точек обеих кривых и дальше должны последовательно просматриваться все точки обеих кривых. При этом составляется таблица растояний между точками обеих кривых.

Но я не пойму, по какому принципу просматривать эти точки, может, кто-нибудь знает, как решить эту задачу?

Буду очень благодарна за любую помощь.

[Brukvalub]

JennyO в сообщении #155635 писал(а):

Кратчайшее растояние будет состоять из суммы длин отрезков, соединяющих эти новые точки обеих кривых.

Вы уверены в этом?

[PAV]

Судя по формулировке, подозреваю, что задача компьютерная и результат интересен в "компьютерном" смысле, а не в чистом математическом. Я прав?

[gris]

Мне припоминается следующая задача: две достаточно гладкие кривые в многомерном пространстве заданы огроменными массивами координат своих точек, отсортированных по параметру (время, длина кривой). Надо найти минимальное расстояние между точками кривых методом, скорейшим, чем прямой перебор всех пар. Там действительно массивы разбиваются на серии последовательных точек. И потом идут методы линейного программирования.

В Вашем тексте непонятно, то ли надо найти вычислить определяемое некоторым образом расстояние между кривыми, то ли кратчайшее расстояние между точками этих кривых. И каких еще точек - заданных или с учетом возможной интерполяции. Как заданы кривые - массивами или уравнениями?

Начните с более строгого и точного изложения задачи.

[vvvv]

Если кривые заданы аналитически, то можно применить метод Лагранжа, если координаты заданы в виде массива, то можно так.

[Алексей К.]

Цитата:

Даны две кривые, заданные точками(координатами этих точек).

Фраза совсем непонятная. Точками (т.н. контрольными точками) задают специальный класс кривых. Если Вы имеете в виду их, то надо это явно написать. Если это произвольная параметризованная кривая, то никакими точками она не задаётся. Наконец, возможно, речь идёт просто о двух точечных множествах.

Цитата:

Надо найти кратчайшее растояние между этими кривыми.
Идея состоит в том, что мы разбиваем каждую кривую одинаковыми отрезками, координаты которых можно определить.

Идея состоит в том, что мы представляем каждую кривую дискретным множеством точек, расставленных по возможности равномерно с небольшим шагом.

Цитата:

Кратчайшее растояние будет состоять из суммы длин отрезков, соединяющих эти новые точки обеих кривых.
При этом все точки обеих кривых должны быть соединены между собой и одна точка первой кривой может быть соединена сразу с несколькими точками второй, если это уменьшает суммарное растояние между кривыми.

Кратчайшее растояние будет --- приближённо! --- наименьшим из расстояний между всеми парами точек, одна из которых принадлежит первой кривой, другая --- второй.

Какие-то умные (деревянные) алгоритмы перебора имеются, и принадлежат к области Computer Science.

Цитата:

Начинается поиск с соединения первых двух точек обеих кривых и дальше должны последовательно просматриваться все точки обеих кривых. При этом составляется таблица растояний между точками обеих кривых.

Составление таблицы излишне. Достаточно запоминать минимальный результат из всего просмотренного. Простейшая отпимизация --- сравнивать с текущим минимумом каждое очередное $|\Delta x|$, $|\Delta y|$. Если $|\Delta| \ge D_{min}$, пара игнорируется.

Цитата:

Но я не пойму, по какому принципу просматривать эти точки, может, кто-нибудь знает, как решить эту задачу?

--- в Computer Science сходите.

Для параметризованных кривых можно искать точное решение как минимум функции $D^2(t_1,t_2)$.

Добавлено спустя 8 минут:

gris в сообщении #155649 писал(а):

Начните с более строгого и точного изложения задачи

+1