222
правки
Изменения
м
Нет описания правки
{{Лемма
|statement=
Если из вершины <tex> D </tex> видны вершины <tex> A, B, C </tex>, а из вершины <tex> B </tex> видны <tex> A, C </tex> одного препятствия и поворот <tex> DBA </tex> не совпадает с поворотом <tex> DBC </tex>, то ребро <tex> DB </tex> можно удалить. (См. поясняющую картинку справа)
|proof=
[[Файл:edgeToDelete.jpg|150px|thumb|right|Удаляем <tex> BD </tex>]]
Теперь рассмотрим случай, когда мы можем вращать полигон. Для начала построим [[Трапецоидная карта|трапецоидную карту]], как будто мы не можем вращать полигон. Теперь будем вращать полигон на малый угол, пока он не сделает полный оборот вокруг своей оси, и для каждого угла сделаем трапецоидную карту. Теперь разместим(мысленно) все карты друг над другом. Таким образом получится, что поворот на малый угол {{---}} это движение вверх/вниз между слоями. Осталось [[Пересечение многоугольников (PSLG overlaying)|попересекать]] соседние слои и добавить между ними ребра (помним что первый и последний слои одинаковы) и уже в этом графе найти путь.
При такой реализации в некоторых случаях у нас может возникнуть ошибка в повороте, так как в одной плоскости мы все можем делать точно: положения на соседних слоях могут допускаться, а повернуть мы не сможем. Это лечится в основном двумя способами: измельчением угла поворота и изначальным сглаживанием углов полигона {{---}} повращать полигон на <tex> +\epsilon </tex> и <tex> -\epsilon </tex> и построить выпуклую оболочкуобъединить с исходным, получив новый полигон.
Так как эта задача достаточно ресурсоемка, мы рассматриваем только наличие пути, а не нахождение кратчайшего.
