Кратчайшее расстояние в пространстве

[tsiberev]

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

Понятно, что если прямая AB не пересекает поверхность - всё ясно.
А если пересекает, как искать огибающую?
Если бы поверхность вращения была сферой - способ решения задачи очевидна.
А как быть в общем случае. когда поверхность - не сферическая?

Проблема еще в том, что количество пар точек, для окторых нужно находиться расстояние - велико
И еще - в принципе приближенно эту задачу можно решать, натянув на всё это дело сетку и шагая по узлам её с использованием волнового алгоритма. Но точность такого решения будет очень низкой, если сетку брать не особо подробной. Брать её более мелкой не позволяют временнЫе ресурсы.
Буду благодарен за помощь.

[worm2]

Если поверхность выпукла, то кратчайший путь будет следующим:
1) От точки A до точки C на поверхности --- прямая, лежащая в плоскости, касательной к поверхности. Выписываем уравнение касательной плоскости к поверхности, условие принадлежности A этой плоскости и условие принадлежности C поверхности. Полученная система описывает некоторую кривую на поверхности, через которую оптимальный путь должен пройти. Можно попробовать параметризовать эту кривую параметром u: C = C(u).
2) От точки C до точки D по поверхности --- геодезическая.
3) От точки D до точки B --- аналогично 1-му пункту. Можно попробовать параметризовать получившуюся кривую параметром v: D = D(v).

Выписываем уравнение геодезической для данной поверхности, проходящей через точки С и D. Находим G(C,D) --- длину отрезка этой кривой, лежащей между С и D.
Получается задача безусловной минимизации функции двух переменных F(u, v) = r(A,C(u))+G(C(u),D(v))+r(D(v),B), где r(X,Y) --- обыкновенное Евклидово расстояние между точками X и Y. Решая её, получаем минимальное расстояние (заодно можно вычислить точки C=C(u), D=D(v), хотя, как показывает рассмотрение примера со сферой, центр которой лежит на прямой AB, эти точки не всегда однозначно определяются).
Успехов!

[ГАЗ-67]

Уточните , пожалуйста , условие . Что означает "кривая задана набором точек " ?

[ГАЗ-67]

Если поверхность задана аналитически , то есть возможность искать решение методами вариационного исчисления , а именно : рассмотреть задачу с негладкими экстремалями . Уточните постановку , пожалуйста .

[tsiberev]

ГАЗ-67 писал(а):

Если поверхность задана аналитически , то есть возможность искать решение методами вариационного исчисления , а именно : рассмотреть задачу с негладкими экстремалями . Уточните постановку , пожалуйста .

Вообще говоря - эта поверхность получена вращением кривой относительно некоторой оси. Кривая в плоскости есть несколько сопряженных дуг окружности.
Однако в большинстве случаев эта кривая является эллипсом.
То есть поверхность - это эллипсоид вращения.

Буду благодарен, если Вы приведет вариант решения.
Спасибо

Добавлено спустя 2 минуты 58 секунд:

worm2 писал(а):

Если поверхность выпукла, то кратчайший путь будет следующим:
1) От точки A до точки C на поверхности --- прямая, лежащая в плоскости, касательной к поверхности. Выписываем уравнение касательной плоскости к поверхности, условие принадлежности A этой плоскости и условие принадлежности C поверхности. Полученная система описывает некоторую кривую на поверхности, через которую оптимальный путь должен пройти. Можно попробовать параметризовать эту кривую параметром u: C = C(u).
2) От точки C до точки D по поверхности --- геодезическая.
3) От точки D до точки B --- аналогично 1-му пункту. Можно попробовать параметризовать получившуюся кривую параметром v: D = D(v).

Выписываем уравнение геодезической для данной поверхности, проходящей через точки С и D. Находим G(C,D) --- длину отрезка этой кривой, лежащей между С и D.
Получается задача безусловной минимизации функции двух переменных F(u, v) = r(A,C(u))+G(C(u),D(v))+r(D(v),B), где r(X,Y) --- обыкновенное Евклидово расстояние между точками X и Y. Решая её, получаем минимальное расстояние (заодно можно вычислить точки C=C(u), D=D(v), хотя, как показывает рассмотрение примера со сферой, центр которой лежит на прямой AB, эти точки не всегда однозначно определяются).
Успехов!

Красиво! Будем подумать

[uni]

По поводу геодезических на эллипсоиде вращения и вообще много чего по поводу геодезических см. здесь:
http://forum.exponenta.ru/viewtopic.php ... &start=150
и далее там по "вкладкам". Это форум по Mathcad, поэтому где есть документы - это расчёты в Mathcad.

[ГАЗ-67]

Предлагаю другой подход .
Исходную кривую аппроксимировать с достаточно высокой точностью отрезками . Тогда тело вращения будет состоять из усеченных конусов .
Конус является развёртываемой поверхностью и отрезок соединяющий две точки на развёртке его будет геодезической на конусе для соответствующих точек . Далее попробовать минимизировать общую длину .
Или попробовать аппроксимировать кривую центральными прямоугольниками .
Ещё лучше .

[uni]

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

[tsiberev]

uni писал(а):

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

Прочитал материалы по Вашей ссылке.
Если честно, то не очень понятно, как именно можно "найти весь путь - каждую точку с произвольной степенью точности"
Если Вы поняли, не могли бы пояснить мне?
Можно по почте.
tsiberev собака sarov . ru

[uni]

Итак, пример.

Эллипсоид вращения.
Пусть образующий эллипс с осями A = 20 (вдоль оси X), B = 10 (вдоль оси Y)
Пусть задана точка T1 = T1 (25,0,0)
И точка Т2 = T2 (-30,1,1)
Необходимо найти длину кратчайшей кривой (саму кривую определять не
обязательно), соединяющую точки Т1 и Т2 с учетом огибания поверхности
вращения.

Не знаю в какую сторону эллипс надо было вращать, потому взял (z/B)^2 последний компонент. На картинке обозначено:
"шарик" - эллипсоид, похож;
"зелёная ниточка" - это куски прямой и огибающая эллипсоида;
"странного вида крестики" - там где они - там точки пересечения прямой и эллипсоида
L - длина огибающей на эллипсоиде;
ну и плоскость - она и в Африке - плоскость.
Ах, да - "мошкара" на картинке - это дефекты (артефакты) реализации implicitplot3d() для Mathcad11.

Предположения (хотелось бы, чтобы так было):
1) Наикратчайшее растояние даст замкнутая (P.S. а хотя кто её знает) геодезическая, которая ползёт по эллипсу, пересекая 2 точки, которые заданы.
2) Тот же эллипс можно получить, если пересечь "шарик" плоскостью.
3) Как же плоскость найти? Я находил численным методом, решая системку. Системка такая: скалярное произведение вектора нормали к поверхности в точке пересечения X1 и нормали искомой плоскости должно равняться нулю, второе уравнение - направляющей вектор прямой скалярно помноженный на нормальный вектор искомой плоскости тоже должен быть равен нулю. Графически это значит, что ... ммм...что же это значит? Честно говоря... сам не понял, но работает.

P.S. Чёрт, всё-таки ошибся. Не, не канает. Буду думать дальше. Плоскость не та получается.
Видимо, придётся всё-таки действовать через длину пространственной кривой.

[Someone]

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

[tsiberev]

Someone писал(а):

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

Да, именно касаться. Я тут на рисунке нарисовал постановку, может так будет видно (использовал картинку UNI).
Есть точка А, точка B. Ну жно найти кратчайшее расстояние с учетом огибания эллипсоида.
Точка Ак - это точка касания эллипсоида со стороны А
Точка Bк - это точка касания эллипсоида со стороны B
Кривая АкBк - это наверно будет геодезической.

[uni]

Да, я понял теперь. Что-то вроде этого:

2tsiberev: Здесь больше отвечать не буду, все ответы на экспоненту, чтобы трафик не гнать лишний.

[uni]

Экспонента загнулась похоже на некоторое время. Придётся сюда перекочевать опять.


Итак, самое сложное, по-видимому, - это отыскание длины геодезической. Как было сказано на экспоненте, конус пересекает эллипсоид и кривая пересечения есть место точек, являющихся точками касания. На картинке выше я попытался численно восстановить эти точки для конкретного примера. Для каждого множества точек с обоих сторон эллипса я восстановил плоскости, т.е. численно получается, что кривая пересечения плоская, что упрощает задачу. Поскольку теперь мы можем однозначно определить все три участка "пути", то минимизацию можно было бы сделать следующим путём. Найти оба эллипса - точки касания. Взять длины 2-х касательных отрезков за параметры, третий параметр будет длина всего пути. Мы можем численно вычислить длины всех трёх участков, перебирая длины каждого из касательных отрезков. Чтобы найти длину геодезической на эллипсоиде придётся потрудиться. Не то, чтобы это было не возможно, просто не так просто как оказалось.
Вот одна из ссылок для ознакомления (pdf, ~1.23 Mb):
"Direct and inverse solutions of geodesics on the ellipsoid with application of nested equatioins"
http://www.ngs.noaa.gov/PUBS_LIB/inverse.pdf

Меняя два параметра (длины касательных), мы можем построить картинку в виде поверхности, где по двум осям откладываем длины касательных (последовательно перебирая точки вдоль кривых пересечения), а третий параметр - общая длина. Думаю, будет у такого графика глобальный минимум. Я пока не могу найти формул по-проще, чтобы длину геодезической посчитать по-быстрее.

Добавлено спустя 2 часа 55 минут 27 секунд:

Теперь только я вник в то, что написал worm2, именно это я проделал в численном виде. Я не обратил внимания на его ответ, т.к. уж слишком он что-то там мудрёного наплёл с непонятными для меня словами. Вот когда уже практически позанимаешься, то находишь корреляцию между результатами и словами. Только я так и не понял, что значит параметризовать кривую с параметром u, возможно, что у меня таким параметром был бы угол обхода эллипса касания одной касательной. Мы меняем его от 0 до 2*Pi - полный оборот - перебрали все возможные касательные с одной стороны.
Теперь хоть знаю, что это называется задачей безусловной минимизации.

[worm2]

uni писал(а):

Только я так и не понял, что значит параметризовать кривую с параметром u, возможно, что у меня таким параметром был бы угол обхода эллипса касания одной касательной. Мы меняем его от 0 до 2*Pi - полный оборот - перебрали все возможные касательные с одной стороны.
Теперь хоть знаю, что это называется задачей безусловной минимизации.

М-да, пожалуй, мой ответ был излишне академичен...
Насчёт параметризации Вы совершенно правильно меня поняли. Если есть система уравнений, описывающая кривую в пространстве F(x,y,z) = 0, G(x, y, z) = 0 (в данном случае первое, например, уравнение, может явяться уравнением Вашего тела вращения), то параметризация --- это запись той же самой кривой в виде x=x(t), y=y(t), z=z(t). Всё правильно, угол можно использовать в качестве параметра. Просто нужно постараться выбрать параметр так, чтобы уравнения были по возможности проще. Иногда для этого удобнее взять не угол, а некоторую функцию от него: t=f(угол). А иногда вообще не удаётся так подобрать параметр t, чтобы x, y и z являлись бы элементарными функциями от t (да что там элементарными --- даже в известных специальных функциях не всегда получается). Так что параметризация --- проблема. Поиск сносного выражения для геодезических на эллипсе, как выясняется --- тоже проблема. А ведь ещё эти функции подставлять в минимизирующее выражение и решать задачу минимизации. Поэтому я так язвительно написал:

Цитата:

Успехов!

Т.е. Ваша задача очень сложная.

Правда,

ГАЗ-69 писал(а):

Исходную кривую аппроксимировать с достаточно высокой точностью отрезками . Тогда тело вращения будет состоять из усеченных конусов .
Конус является развёртываемой поверхностью и отрезок соединяющий две точки на развёртке его будет геодезической на конусе для соответствующих точек . Далее попробовать минимизировать общую длину .
Или попробовать аппроксимировать кривую центральными прямоугольниками .
Ещё лучше .

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