Алгоритм отсечения Вейлера – Атертона

Алгоритм Вейлера -Атертона полигонов отсечения представляет собой алгоритм . Он используется в таких областях, как компьютерная графика и разработка игр, где необходимо отсечение полигонов. Он позволяет обрезать объект или многоугольник-кандидат произвольной формы с помощью обрезающего многоугольника/области/региона .

Обычно это применимо только в 2D . Однако его можно использовать в 3D за счет определения видимой поверхности и с повышенной эффективностью за счет Z-упорядочения .

Предварительные условия

Подразделение с помощью алгоритма Вейлера-Атертона

Перед применением к многоугольнику алгоритм требует выполнения нескольких предварительных условий:

• Полигоны-кандидаты должны быть ориентированы по часовой стрелке.
• Полигоны-кандидаты не должны быть самопересекающимися (т.е. повторно входящими).
• Алгоритм может поддерживать дыры (как многоугольники против часовой стрелки, полностью внутри родительского многоугольника), но требует дополнительных алгоритмов, чтобы решить, какие многоугольники являются дырами, после чего объединение многоугольников может быть выполнено с использованием варианта алгоритма.

Алгоритм

Учитывая полигон A в качестве области отсечения и полигон B в качестве многоугольника, подлежащего отсечению, алгоритм состоит из следующих шагов:

1. Перечислите вершины многоугольника A области отсечения и вершины рассматриваемого многоугольника B.
2. Пометьте перечисленные вершины предметного многоугольника B как внутри, так и снаружи области отсечения A.
3. Найдите все пересечения полигонов и вставьте их в оба списка, связывая списки на пересечениях.
4. Сгенерируйте список «входящих» пересечений – пересечений, в которых вектор от пересечения до следующей вершины рассматриваемого многоугольника B начинается внутри области отсечения.
5. Следуйте за каждым пересечением по часовой стрелке вокруг связанных списков, пока не будет найдена начальная позиция.

Если пересечений нет, то должно выполняться одно из трех условий:

1. A находится внутри B — возврат A для отсечения, B для слияния.
2. B находится внутри A — верните B для отсечения, A для слияния.
3. A и B не перекрываются — верните None для отсечения или A и B для слияния.

Заключение

Один или несколько вогнутых многоугольников могут создавать более одного пересекающегося многоугольника. Выпуклые многоугольники будут иметь только один пересекающийся многоугольник.

Тот же алгоритм можно использовать для объединения двух многоугольников, начиная с исходящих пересечений, а не с входящих. Однако это может привести к образованию отверстий против часовой стрелки.

Некоторые комбинации полигонов могут быть трудно разрешить, особенно если разрешены отверстия.

Точки, расположенные очень близко к краю другого многоугольника, могут рассматриваться как внутри, так и снаружи до тех пор, пока их статус не будет подтвержден после того, как все пересечения будут найдены и проверены; однако это увеличивает сложность.

Чтобы повысить скорость маркировки и избежать необходимости продолжать дальнейшие действия, можно использовать различные стратегии. Потребуется осторожность там, где полигоны имеют общие края.

См. также

• Алгоритм отсечения Сазерленда – Ходжмана
• Алгоритм отсечения Ватти
• Алгоритм отсечения Грейнера – Хормана

Ссылки

• Вейлер, Кевин и Атертон, Питер. «Удаление скрытых поверхностей с использованием сортировки областей полигонов» , Компьютерная графика, 11 (2): 214-222, 1977.