Модель
- Цилиндр радиуса $R$ описываем угловой координатой $\theta \in [0,2\pi )$ и осевой $z\in \mathbb{R}$. Точки: $P_1=({\theta }_1,z_1)$, $P_2=({\theta }_2,z_2)$.
- Полоса‑препятствие задаётся как набор точек цилиндра с $\theta$ в некотором интервале $[\alpha ,\beta ]$ (вертикальная полоса вдоль образующих) или как набор с $z\in [h_1,h_2]$ (горизонтальная полоса). Дальше опишем для вертикальной полосы; для горизонтальной всё аналогично после поворота координат.
Развёртка цилиндра в плоскость
- Развёртка цилиндра в плоскость даётся отображением $(\theta ,z)\mapsto (x,z)$ с $x=R\theta$. При этом однажды получаем полосу $x\in [0,2\pi R)$, границы по $x$ идентифицируются по смещению на $2\pi R$.
- На развёртке точки: $P_i\mapsto (x_i,z_i)$, $x_i=R{\theta }_i$. Запрещённая вертикальная полоса становится прямоугольником $x\in [R\alpha ,R\beta ]$ (с периодичностью по $x$).
Кратчайший путь без препятствий
- На развёртке геодезическая — прямая. В общем случае путь может обвиваться вокруг цилиндра $k$ раз; расстояние для фиксированного целого $k$ равно
$$d_k=\sqrt{(R({\theta }_2-{\theta }_1)+2\pi Rk{)}^2+(z_2-z_1{)}^2}.$$ Минимум по $k\in \mathbb{Z}$ даёт кратчайший путь без учёта препятствия.
Учет полосы (сведение к планарной задаче)
1. Развернуть цилиндр в полосу $x$-периодичной плоскости и рассмотреть бесконечную цепочку копий интервала по оси $x$ (то есть величины $x+2\pi Rn$, $n\in \mathbb{Z}$).
2. Запрещённый прямоугольник (полоса) тоже периодично копируется.
3. В таком развёрнутом (планарном) представлении задача становится классической: найти кратчайший кусочно‑линейный путь между двух точек, который не пересекает запрещённые прямоугольники, с учётом периодичности по $x$.
Метод решения (принципиально два приёма)
A. Поиск по классам обвиваний (winding numbers). Для каждого целого сдвига $n$ (соответствует оборачиванию цилиндра на $n$ полных оборотов) берем образ $P_2^{(n)}=(x_2+2\pi Rn,z_2)$ и проверяем прямую от $P_1$ до $P_2^{(n)}$. Если прямая не пересекает запрещённую полосу — это допустимый геодезический на цилиндре; длина — обычная евклидова длина прямой. Берём минимум по всем $n$.
B. Отражение по границам полосы (если прямая пересекает полосу). Если кратчайший путь должен касаться границы запрещённой полосы, то точку $P_2$ отражают в прямой (границе прямоугольника) и ищут прямую до отраженной точки: точка пересечения прямой и границы даёт точку касания на границе. Это эквивалентно закону равенства углов (угол падения = угол отражения) и даёт конструктивный способ найти путь, состоящий из двух прямых сегментов, касающихся границы в одной точке. Аналогично можно отражать через сочетание границ, если путь проходит по углу полосы.
Итог и алгоритм
- Развёрните цилиндр в плоскость: $x=R\theta$.
- Постройте копии $P_2^{(n)}=(x_2+2\pi Rn,z_2)$ для нескольких $n$ (обычно достаточно рассмотреть несколько соседних $n$, пока длина не возрастёт).
- Для каждого $n$ проверьте: прямая $P_1-P_2^{(n)}$ пересекает ли запрещённую область. Если нет — вычислите длину и сохраните как кандидат.
- Если прямает пересекает, примените отражение по ближайшей границе полосы (или последовательность отражений), найдите точку касания и длину пути, состоящего из двух отрезков; это кандидат.
- Ответ — минимальная длина среди всех кандидатов. Обратное отображение в координаты $(\theta ,z)$ возвращает геодезию на цилиндре.
Замечания
- Для горизонтальной полосы (з‑интервал) развёртка даёт горизонтальную запрещённую полосу, и всё прежнее применяется с ролями осей поменянными.
- В основе лежит то, что цилиндр — разворачиваемая поверхность: геодезии соответствуют прямым на развёртке, а запрещённые области — плоские препятствия; потому задача сводится к планарной задаче с периодическими копиями и решается прямой/отражательной техникой.