Кратко: метод отражения (развёртки) сводит задачу о кратчайшем пути с касанием/отражением от прямой (или последовательности прямых) к задаче о прямой линии в «зеркально» отражённой конфигурации. Геометрическое обоснование — равенство длин за счёт симметрии и условия минимума (угол падения = угол отражения). Ниже — пояснение, ограничения и примеры.
ОСНОВА (однократное касание прямой)
- Задача: найти точку $X$ на прямой $l$ (или на её отрезке $S$), такую что путь $A\to X\to B$ минимален.
- Постройте отражение точки $B$ относительно прямой $l$, обозначим $B^{\prime }$. Тогда для любой точки $X\in l$ выполнено $XB=X{B}^{\prime }$ (расстояния равны). Следовательно длина пути
$$AX+XB=AX+X{B}^{\prime }\ge A{B}^{\prime },$$ причём равенство достигается тогда и только тогда, когда точки $A,X,B^{\prime }$ коллинеарны, то есть прямая $A{B}^{\prime }$ пересекает $l$ в нужной точке $X$. Это и даёт минимальный путь. Условие «угол падения = угол отражения» вытекает из симметрии при отражении: при равенстве соответствующих углов треугольники зеркальны.
ОГРАНИЧЕНИЯ и детали корректности
- Рефлексия даёт кандидат на оптимум только если точка пересечения прямой $A{B}^{\prime }$ с осью $l$ лежит в допустимой части $S$ (на отрезке, на краю и т.д.). Если пересечение лежит вне, то оптимум среди точек $S$ достигается на одном из концов $S$.
- Метод применим к совершенно плоским (евклидовым) расстояниям и «зеркальному» закону отражения. Он не применим, если:
- скорость движения разная в разных областях (требуется закон преломления — Снеллиус);
- граница изогнута: простое отражение точки через касательную не даёт глобального решения (вместо этого требуется вариационный расчёт и условие равенства углов в точке касания);
- участок препятствия не является прямой или путь не должен пересекать запрещённую область — тогда нужно проверять, не пересекает ли полученный прямой отрезок запрещённые части;
- несколько отражений/касаний: требуется последовательное отражение (развёртка); при неправильном порядке отражений результат может быть неверен.
- Для задач с несколькими отражениями/прыжками: отражаем цель последовательно в обратном порядке отражений. Но дополнительно нужно проверить, что прямая от A к многократно отражённой точке даёт пересечения с каждой исходной прямой в нужном порядке и в допустимых частях отрезков.
ИЛЛЮСТРАТИВНЫЕ ПРИМЕРЫ
1) Одна прямая, пересечение внутри отрезка
- Дано $A=(0,1)$, $B=(4,1)$, отрезок на оси $x$: $S=\{(x,0)\mid 1\le x\le 3\}$.
- Отразим $B$ относительно оси $x$: $B^{\prime }=(4,-1)$.
- Уравнение прямой $A{B}^{\prime }$: $y-1=-\frac{1}{2}(x-0)$, при пересечении с $y=0$ даёт $x=2$. Точка $X=(2,0)$ лежит на $S$.
- Длина минимального пути равна длине $A{B}^{\prime }$:
$$|A{B}^{\prime }|=\sqrt{(4-0{)}^2+(-1-1{)}^2}=\sqrt{16+4}=2\sqrt{5}.$$ Проверка: $AX+XB=|A{B}^{\prime }|.$
2) Одна прямая, пересечение вне отрезка — оптимум в конце отрезка
- Те же $A,B$, но теперь $S=\{(x,0)\mid 1\le x\le 1.5\}$. Прямая $A{B}^{\prime }$ пересекает ось в $x=2$, вне $S$. Значит минимальный путь, ограниченный $S$, достигается на одном из концов $X=(1,0)$ или $X=(1.5,0)$. Сравниваем длины:
$$L(1)=\sqrt{1^2+1^2}+\sqrt{3^2+1^2}=\sqrt{2}+\sqrt{10},L(1.5)=\sqrt{1.5^2+1^2}+\sqrt{2.5^2+1^2}.$$ Минимум — меньшая из этих двух величин (в данном случае $L(1)$).
3) Два последовательных отражения (порядок важен)
- Пусть требуется путь $A\to X_1\in l_1\to X_2\in l_2\to B$ с заданным порядком касаний $l_1$ затем $l_2$. Отразим $B$ сначала относительно $l_2$ в $B_1$, затем $B_1$ относительно $l_1$ в $B_2$. Тогда прямая $A{B}_2$ пересекает $l_1$ и $l_2$ в точках, которые дают кандидат на оптимум. Необходимо проверить, что пересечения идут в нужном порядке и лежат на допустимых участках; иначе оптимум на границах или порядок отражений другой.
- Примечание: при нескольких возможных порядках касаний нужно сравнить все допустимые последовательности (конечно, если их число невелико).
4) Обход препятствия (развёртка полигона)
- При поиске кратчайшего пути вокруг выпуклого многоугольного препятствия можно «разворачивать» плоскость вдоль рёбер: отражать цель через последовательность рёбер, которые путь должен «обойти», сведя задачу к прямой линии в развёртке. Метод даёт кратчайший ламанный путь, касающийся только вершин/ребер, но требует проверки на пересечение внутренних частей препятствия после «свёртки».
Короткое резюме / чек-лист применения метода:
- Отразьте цель по прямой(м) в обратном порядке отражений.
- Проведите прямую от начальной точки к полученной отражённой точке.
- Проверьте, что точки пересечения лежат на допустимых участках и в нужном порядке.
- Если пересечение вне участка — оптимум на соответствующем конце участка.
- Если границы кривые или веса скорости различаются — метод нужно модифицировать (вариации, Снеллиус для преломления, численные методы для кривых).
Если нужно, могу показать дополнительные численные примеры (несколько наборов координат) или иллюстрировать многократную развёртку шаг за шагом.