Как найти видимость многоугольника из вершины v вогнутого многоугольника

Question

Я работаю над заданием 2d art gallery, чтобы найти минимальное количество охранников вершин. В рамках решения проблемы с использованием генетических алгоритмов мне необходимо выяснить область многоугольника, видимую для охранника, помещенного в вершину.

На входе используется многоугольник с известным 2d (x, y) координаты. Не могли бы вы помочь мне узнать, как рассчитать видимость охранника (то есть, какую часть многоугольника он мог видеть), расположенного на вершине многоугольника?

Answer 1

Это решение для поиска видимой области из произвольной точки внутри многоугольника. Вы можете изменить его, чтобы ограничить точку вершинами многоугольника:

Шаг 1: Нарисуйте лучи от ограждения к каждой вершине и найдите точки пересечения со всеми ребрамиполигон.

Шаг 2: Проверьте, пересекает ли луч многоугольник (желтый) или просто касается его (фиолетовый).

Шаг 3: Сортировка пересеченийна луче по их расстояниям от охранника и найти точку пересечения шкафа. Назовите все дальнейшие точки невидимыми (красные) и более близкие видимые (зеленые).

Шаг 4: Теперь каждое ребро многоугольника эквивалентно одному или нескольким сегментам, каждый сегмент которого является его концом. точки помечены как видимые, будут видимыми. Суммируйте длину таких сегментов.

Вот более сложный пример:

И имейте в виду, что это только началои вы можете оптимизировать его. Подумайте о комментарии Нико для первого улучшения.