Здравствуйте, коллеги.
Подскажите, пожалуйста, как мне рассчитать кратчайший путь по поверхности выпуклого многогранника между двумя заданными точками. Многогранник задан координатами своих вершин.

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

Решение будет основываться на том факте, что кратчайший путь при пересечении ребра ведет себя по правилу "угол падения равен углу отпадения" (доказательство: развернем грани так, чтобы они попали в одну плоскость, на плоскости кратчайший путь — прямая).

Теперь будем пускать лучи от исходной точки во все стороны с небольшим шагом угла и вести их через пересечение ребер по этому правилу. Как только луч начинает удаляться (в 3D смысле) от второй точки, прекращаем его вести. Как только два соседних луча возьмут вторую точку в "вилку" (пройдут около нее с двух сторон), начинаем применять метод деления пополам — пускаем луч посередине между этими двумя и смотрим, с каким из двух первых он образует "вилку" и т.д. Так мы можем получить луч, проходящий сколь угодно близко от второй точки, чего и достаточно для решения задачи.

Осталось выяснить два вопроса:

1. Как выбирать шаг угла?
Можно начать, допустим, с 10 градусов, если "вилка" не нашлась, уменьшать это в два раза и повторять, пока не найдется.

2. Как формализовать понятие "два луча прошли около точки с двух сторон"?
Если лучи проходят по подной грани, то все более менее просто — это "угол между перпендикулярами на эти лучи больше 90 градусов".
Проблема, однако, в том, что точка может быть очень близко к ребру, в это случае ее сложно так зацепить — надо рассматривать и соседнюю грань. Можно спроцецировать соседнюю грань в одну плоскость с нашей и проделать ту же процедуру. Будет неплохо работать за исключением тех случаев, когда эта грань очень маленькая (по сравнению с остальными). Если таких граней заведомо нет, то все в порядке, иначе надо делать развертку на одну плоскость сразу нескольких граней.

S>Теперь будем пускать лучи от исходной точки во все стороны с небольшим шагом угла и вести их через пересечение ребер по этому правилу. Как только луч начинает удаляться (в 3D смысле) от второй точки, прекращаем его вести.

Сейчас подумал, и понял, что так делать не корректно. Могут быть, например, ситуации типа "острый угол между гранями". В этом случае кратчайший путь может сначала удаляться от второй точки. Тут нужен какой-то другой критерий. Например, ограничение по пройденному расстоянию, вроде подойдет сумма трех разных ребер параллелепипеда, описывающего многогранник.

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

В общем, задача довольно сложная.

S>В общем, задача довольно сложная.
Да в принципе идея про разворачивание в плоскость всего многогранника имеет смысл.
1) Разбиваем все грани на треугольники (триангулируем).
2) Находим треуг-ки, в которых лежат заданные точки p1 и p2
3) Разворачиваем все остальные треуг-ки многогранника в плоскость. См. формулу Родригеса — думаю понятно как это сделать.
Для примера рассмотрим два смежных треугольника.
Общее ребро — ось вращения, находим матрицу Родригеса, которая задает оператор перехода от системы коорд-т второго треуг-ка в систему коорд-т первого. p = R * p`
Таким приемом "разворачиваем" все остальные треуг-ки, двигаясь через общие ребра, и применяя соответствующие операторы R всех предыдущих треуг-ов.
4) После "разворота", у нас будет одна плоскость и две точки, p1 и R1*R2*...*Rn*p2, где p2 — вторая заданная точка в системе коорд-т того второго треуг-ка, где и лежит p2.
Расстояние, соответственно d = p1 — R1*R2*...*Rn*p2

Здравствуйте, Аноним, Вы писали:

А>Таким приемом "разворачиваем" все остальные треуг-ки, двигаясь через общие ребра, и применяя соответствующие операторы R всех предыдущих треуг-ов.

А в каком порядке-то двигаемся? Их может быть много разных. Каждому соответствует своя цепочка операторов перехода. Перебирать все возможные порядки переходов довольно тяжело алгоритмически (экспоненциальная сложность).

S>А в каком порядке-то двигаемся? Их может быть много разных. Каждому соответствует своя цепочка операторов перехода. Перебирать все возможные порядки переходов довольно тяжело алгоритмически (экспоненциальная сложность).
Если введем флаг, помечающий треуг-к как уже "развернутый", то обход делается совершенно произвольным образом. Главное, чтобы не пропускать треуг-ки, построить бинарное дерево от root до листьев, тогда не пропустим.

Здравствуйте, Аноним, Вы писали:

А>Если введем флаг, помечающий треуг-к как уже "развернутый", то обход делается совершенно произвольным образом. Главное, чтобы не пропускать треуг-ки, построить бинарное дерево от root до листьев, тогда не пропустим.
И что же это, результат будет не зависеть от порядка обхода? Это почему еще?

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

S>И что же это, результат будет не зависеть от порядка обхода? Это почему еще?
Не зависит, тк в конце получаем плоскость, какой бы последовательности ни придерживались.
S>В общем-то это самое сложное в задаче — понять, в каком порядке проходить через грани.
По-моему, взяв треугольник, и его три направления через ребра, двигаясь так дальше, получим однозначное покрытие всего многогранника (придется конечно ввести флаг к каждому треуг-ку).

Здравствуйте, Аноним, Вы писали:

S>>В общем-то это самое сложное в задаче — понять, в каком порядке проходить через грани.
А>По-моему, взяв треугольник, и его три направления через ребра, двигаясь так дальше, получим однозначное покрытие всего многогранника (придется конечно ввести флаг к каждому треуг-ку).
"Три направления через ребра" — это начало ветвления. Дальше оно будет происходить в каждой грани (через одно ребро вошли, через несколько можем выйти). Как ты предлагаешь делать этот выбор? Перебором всех вариантов? Так можно, но это экспоненциальная сложность.

Здравствуйте, Аноним, Вы писали:

S>>И что же это, результат будет не зависеть от порядка обхода? Это почему еще?
А>Не зависит, тк в конце получаем плоскость, какой бы последовательности ни придерживались.
Чтобы лучше понять, что однозначного решения тут нет, возьми куб и две точки в центрах противоположных гранях. Очевидно, что есть целых четыре кратчайших пути, ведущих из одной в другую. Ну и как они получатся в твоем решении?

Здравствуйте, Аноним, Вы писали:

А>Здравствуйте, коллеги.
А>Подскажите, пожалуйста, как мне рассчитать кратчайший путь по поверхности выпуклого многогранника между двумя заданными точками. Многогранник задан координатами своих вершин.

1. На каждой грани участок кратчайшего расстояния будет прямой
2. кратчайших путей может быть больше 1-го

Один из вариантов:
введи функцию потенциала для рёбер. fi(t) это мин растояние от точкий A до точки на этой грани. (t вдоль грани 0..1)
для каждого ребра надо построить такую функцию. после чего идём из точки B в сторону минимального потненциала грани.

* сами функции fi(t) будут ломаными (куски прямых).

Так что выглядеть это будет так задаём грани и связи между гранями (для треугольников по 3 связи)
Для каждого ребра (оно же связь между гранями) задаём неопределённый потенциал (или просто дохрена)
Потом для грани на которой лежит точка A для её ребер строим им потенциал.
Затеме рекурсивно строим для связанных граней. Если такое воздействие не уменьшило потенциал на ребре.
То для него рекурсивно пересчитывать ничего не надо.
В принципе мы так получим потенциал для всех ребер, хотя не обязательно он нужен для всех.
Т.е. можно смотреть из точки B на его смежные ребра и наблюдать за потенциалом. И пользоваться минимальным
значением на 3х смежных гранях для ограничения алгоритма заполнения граней. Ибо если растояние уже больше
этого минимального то дальнейшие шаги его не уменьшат

Надеюсь идея ясна

ps: варианты обхода при построение потенциалов граней тоже могут влиять на кол-во итераций, так что тут
можно какой нить эвристический принцип пользовать (хотя это на усмотрение)

Здравствуйте, Аноним, Вы писали:

А>Подскажите, пожалуйста, как мне рассчитать кратчайший путь по поверхности выпуклого многогранника между двумя заданными точками. Многогранник задан координатами своих вершин.
А если попробовать динамическое программирование и адаптировать волновой алгоритм?

Делаем так — строим в начальном многоугольнике перпендикуляры до сторон (для этого все грани должны быть выпуклыми многоугольниками, может быть придётся триангулировать их). В точках на сторонах запоминаем расстояния от начальной точки. Затем каждая точка, в свою очередь, становится источником "волн" — перпендикуляров до других сторон. И так до тех пор, пока не придём в целевой многоугольник в котором нужно будет выбрать линию с минимальной суммой.

Интуитивно кажется, что полученый путь будет оптимальным — так как на кажом шаге мы всегда выбираем минимальное расстояние (перпендикуляр) до другой грани.

Возможно будет проблема с числовой стабильностью.

Здравствуйте, Cyberax, Вы писали:

C>Здравствуйте, Аноним, Вы писали:

А>>Подскажите, пожалуйста, как мне рассчитать кратчайший путь по поверхности выпуклого многогранника между двумя заданными точками. Многогранник задан координатами своих вершин.
C>А если попробовать динамическое программирование и адаптировать волновой алгоритм?

C>Делаем так — строим в начальном многоугольнике перпендикуляры до сторон (для этого все грани должны быть выпуклыми многоугольниками, может быть придётся триангулировать их). В точках на сторонах запоминаем расстояния от начальной точки. Затем каждая точка, в свою очередь, становится источником "волн" — перпендикуляров до других сторон. И так до тех пор, пока не придём в целевой многоугольник в котором нужно будет выбрать линию с минимальной суммой.

C>Интуитивно кажется, что полученый путь будет оптимальным — так как на кажом шаге мы всегда выбираем минимальное расстояние (перпендикуляр) до другой грани.

C>Возможно будет проблема с числовой стабильностью.

Я вобще-то предлагал то же самое. Тоже распространение только не одельных точек, всех сразу. Ломаная то задаётся просто набором точек (да и их не много будет). (Я не уверен что одним минимумом можно обойтись. Это надо доказать еще, а щас лень). А так потенциалы на рёбрах в виде набора точек позволят искать минимум не только на выпуклых многогранниках. И со стабильностью проблем не будет.

ps: и еще первый шаг это проверить частный случай когда обе точки на одной грани

Здравствуйте, Аноним, Вы писали:

А>Я вобще-то предлагал то же самое. Тоже распространение только не одельных точек, всех сразу. Ломаная то задаётся просто набором точек (да и их не много будет). (Я не уверен что одним минимумом можно обойтись. Это надо доказать еще, а щас лень). А так потенциалы на рёбрах в виде набора точек позволят искать минимум не только на выпуклых многогранниках. И со стабильностью проблем не будет.
Ага. Можно представить это как пятно краски, расширяющееся из начальной точки. Я попробовал обойтись дискретными путями, AFAIR, тут должно быть достаточно экстремумов.

А>ps: и еще первый шаг это проверить частный случай когда обе точки на одной грани
Ага, это частный случай двух точек в одном многоугольнике Надо проверять нулевым шагом.

Здравствуйте, Аноним, Вы писали:

А>Один из вариантов:
А>введи функцию потенциала для рёбер. fi(t) это мин растояние от точкий A до точки на этой грани. (t вдоль грани 0..1)
А>для каждого ребра надо построить такую функцию. после чего идём из точки B в сторону минимального потненциала грани.

А>* сами функции fi(t) будут ломаными (куски прямых).

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

Здравствуйте, Cyberax, Вы писали:

C>Интуитивно кажется, что полученый путь будет оптимальным — так как на кажом шаге мы всегда выбираем минимальное расстояние (перпендикуляр) до другой грани.

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

Здравствуйте, subdmitry, Вы писали:

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

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

Выгоднее даже не пересчитывать потенциалы друг из друга, а запоминать в каждой такой точке направление, из которого мы пришли, трансформируя эти направления при пересечении граней по описанному закону. Естественно, если брать точки с каким-то шагом, то направления точно попадать в точки не будут, тут нужно делать апроксимацию по ближайшим точкам. Ну а потом для точности осуществить метод деления пополам точными лучами. Это решает проблему с обнаружением вилки (которая была у метода лучей) — когда есть покрытие грани лучами (пусть и примерно вычисленными) ее найти нетрудно.

Здравствуйте, subdmitry, Вы писали:

S>Это решает проблему с обнаружением вилки (которая была у метода лучей) — когда есть покрытие грани лучами (пусть и примерно вычисленными) ее найти нетрудно.

Хотя почему примерно? Можно их и точно вычислить.

Здравствуйте, subdmitry, Вы писали:

S>Здравствуйте, subdmitry, Вы писали:

S>>Это решает проблему с обнаружением вилки (которая была у метода лучей) — когда есть покрытие грани лучами (пусть и примерно вычисленными) ее найти нетрудно.

S>Хотя почему примерно? Можно их и точно вычислить.

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

Вобще лучше попробывать реализовать

Здравствуйте, subdmitry, Вы писали:

C>>Интуитивно кажется, что полученый путь будет оптимальным — так как на кажом шаге мы всегда выбираем минимальное расстояние (перпендикуляр) до другой грани.
S>Уже говорилось — кратчайшая ломаная пересекает ребра по закону "угол падения равен углу отпадения", а вовсе не перпендикулярна.
А точно? Ну тогда заменить перпендикуляры на эти ломаные. Сам принцип должен работать.

Кстати появилось ещё одно подозрение — что ломаная может получится сечением многогранника плоскостью, проходящей через обе точки и барицентр многогранника. Чистое предположение.