Кратчайший путь между двумя точками на кубоиде на его поверхности

Question

Я не могу найти универсальное решение для «Проблемы паука и мухи» (кратчайший путь между двумя точками на кубоиде на его поверхности)Каждый решает один конкретный случай, но что, когда две точки могут быть где угодно?

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

Answer 1

Свести структуру куба к 2d следующим образом ...

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

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

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

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

Answer 2

Я думаю, что это хороший вопрос, ответ на который совсем не очевиден.В гладкой сфере это чрезвычайно сложная проблема.Геодезические (кратчайшие пути) на сфере (которая является гладким аналогом куба) легко найти.Геодезические на двухосном эллипсоиде (эллипсоид вращения; одно поперечное сечение - круг) найти гораздо сложнее.Нахождение геодезических на трехосном эллипсоиде (гладкий аналог общего кубоида) было сложной нерешенной проблемой в первой половине 19-го века. См. Страницу Википедии .

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

Вы можете найти литературу по этому вопросу, если будете искать термин «нетто».Многогранник, разрезанный вдоль некоторых краев, чтобы его можно было сплющить, часто называют «сеткой».Мне удалось быстро найти сайт, который утверждает (без доказательств), что есть только 11 различных сетей для детеныша (oid).Но я согласен с вами, что жесткое кодирование всех вариантов - не лучший способ.

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

Что яЯ думаю, что может сработать это решение для динамического программирования, где вы смотрите на различные грани, через которые ваш путь может пройти между начальной и конечной точками.Существует иерархия ребер (те, которые находятся на начальной грани; те, которые содержат вершину на начальной грани; те, что на гранях, смежных с начальной гранью; и т. Д.).Для каждой точки на каждом из этих ребер вы можете найти минимальное расстояние до начальной точки, кульминацией которого является минимальное расстояние от конечной точки до начальной точки.

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