Кратко и по сути — разбор задачи и сравнение подходов.
Постановка. Даны точки $A,B$ и гладкая выпуклая кривая препятствия $\Gamma$ (замкнутая или дуга) между ними. Требуется кратчайший путь из $A$ в $B$, не пересекающий внутренность препятствия, допускаются: прямые отрезки, касательные переходы (касание $\Gamma$ в точке без входа внутрь), обход по дуге $\Gamma$, и/или одно- или многоразовые отражения по закону зеркала (если отражения разрешены).
1) Структура оптимального решения (геометрические факты)
- Если отрезок $AB$ не пересекает внутренность препятствия $\Rightarrow$ оптимум — прямая $AB$.
- Для выпуклой гладкой $\Gamma$ оптимальный путь без отражений имеет вид либо прямой $AB$, либо цепочки: отрезок $A{T}_1$ (касательный в $T_1$), обход по дуге $\Gamma$ от $T_1$ до $T_2$, отрезок $T_{2}B$ (касательный в $T_2$). Доказательство: локальная оптимальность требует, чтобы прямые, входящие в точку соприкосновения с границей, были касательны (иначе можно сократить путь), см. принцип зеркала для геодезических на выпуклой границе.
- Условие касательности: для точек касания $T$ вектор $(T-A)$ ортогонален нормали $n(T)$ кривой, т.е. $(T-A)\cdot n(T)=0$ (и аналогично для $T_2$ и $B$).
- Функциональная длина пути при заданных касательных точках $(T_1,T_2)$:
$$L(T_1,T_2)=|A-T_1|+s_{\Gamma }(T_1,T_2)+|T_2-B|,$$ где $s_{\Gamma }$ — длина дуги по $\Gamma$ между $T_1$ и $T_2$. Минимизируется по параметрам точек на $\Gamma$ (и по направлению обхода дуги — по двум направлениям).
- Отражения (спекулярное): при одном отражении в точке $R$ выполняется закон равных углов относительно касательной в $R$. Эквивалентный способ: отразить $B$ относительно касательной в $R$ в точку $B^{\prime }$; тогда $R$ лежит на отрезке $A{B}^{\prime }$. Условие на $R$ даётся системой
$$(A-R)\cdot t(R)=(B-R)\cdot t(R),(A-R)\cdot n(R)=-(B-R)\cdot n(R),$$ где $t(R)$ — касательный, $n(R)$ — нормальный векторы.
2) Чисто геометрические (аналитико-геометрические) методы
- Подход: вывести необходимые условия (касательность, зеркальный закон), свести задачу к поиску корней уравнений для параметров точек на $\Gamma$. Часто параметризуют $\Gamma$ углом или дуговой координатой $\theta$ и минимизируют $L({\theta }_1,{\theta }_2)$.
- Плюсы: даёт точные (аналитические или полуаналитические) условия; быстро (решение сводится к маломерной задаче оптимизации по 1–2 переменным); обеспечивает доказательства оптимальности и явные необходимые условия.
- Минусы: требует гладкого аналитического задания кривой; уравнения касательных/отражений могут быть транцендентными или полиномиальными высокой степени (требуют численного решения); сложнее для многих препятствий или негладких границ.
3) Методы вычислительной оптимизации / численные алгоритмы
- Дискретизация границы: аппроксимировать $\Gamma$ полигонами, построить visibility-graph (вершины: $A,B$ и узлы вдоль границы), затем Dijkstra/A* — путь через вершины и ребра; для гладкой $\Gamma$ можно взять высокую плотность узлов для точности.
- Параметрическая минимизация: параметризовать точки касания ${\theta }_1,{\theta }_2$ и использовать градиентные методы или глобальную оптимизацию (в 1–2D это быстро и точно). Можно вычислять производные аналитически (с учётом производной длины дуги).
- Вариационные/контроль: представить путь как ломанная с фиксированным числом узлов и минимизировать суммарную длину с ограничением невхождения в внутренность; решать NLP (e.g. SQP).
- Level-set / eikonal численные: вычислять расстояние (Fast Marching) во всём поле; даёт аппроксимацию геодезических для произвольных областей.
- Sampling-based (PRM/RRT): для многопрепятственных сред; не гарантирующие оптимальность, но практичны.
- Отражения: могут ввести как дискретные события/условия в оптимизационную модель или решать уравнение отражения численно.
Плюсы численных методов: универсальность (сложные/негладкие формы, множество препятствий, дополнительные ограничения), простота реализации, устойчивость при численного представления кривой. Минусы: аппроксимация, погрешности, возможные локальные минимумы (особенно при параметризации пути с большим числом степеней свободы), зависимость от сетки/сэмплинга.
4) Практические рекомендации
- Одна гладкая выпуклая кривая, цель — точный ответ: используйте геометрический подход — найти касательные из $A$ и $B$, минимизировать $L({\theta }_1,{\theta }_2)$ по двум параметрам; при отражениях примените метод зеркала (отразить $B$ по касательной, решить простое условие).
- Сложные/несколько препятствий или негладкая граница: численные методы (visibility graph, Fast Marching, оптимизация по параметризованной ломаной) — чаще всего практичнее.
- Компромисс: параметризовать $\Gamma$ и решать низкоразмерную задачу оптимизации (градиенты аналитически) — сочетает точность геометрии и универсальность численных методов.
5) Краткие алгоритмические схемы
- Геометрический (без отражений):
1. Проверить пересечение отрезка $AB$ с внутренностью препятствия.
2. Если нет — вернуть $AB$.
3. Иначе: найти все касательные точки $T_A(\theta )$ из $A$ и $T_B(\varphi )$ из $B$.
4. Минимизировать по $(\theta ,\varphi )$ функцию $L(\theta ,\varphi )=|A-T_A|+s_{\Gamma }(T_A,T_B)+|T_B-B|$ (учесть оба направления обхода).
- Численный (visibility/graph):
1. Аппроксимировать $\Gamma$ набором вершин.
2. Построить граф видимости между вершинами, $A,B$.
3. Найти кратчайший путь графа (Dijkstra/A*).
4. При необходимости уточнить локально (локальная оптимизация параметров касательных).
Вывод: для одной гладкой выпуклой кривой геометрические методы дают компактные, интерпретируемые и часто точные решения (касательность/отражение через зеркало). Для общей практической задачи (несколько/сложные препятствия, негладкость, дополнительные условия) численные методы более гибки, хотя требуют аккуратной дискретизации и могут давать приближённые ответы.