Алгоритм Уайлера — Атертона
Алгоритм
Уайлера — Атертона (Вейлера —
Азертона, Weiler — Atherton) используется
в компьютерной графике для клиппинга (нахождения
области пересечения) отсекаемого
многоугольника по отсекающему
многоугольнику, также называемому окном.
Отсекаемый и отсекающий многоугольники
могут быть невыпуклыми. Алгоритм применим
только для плоских фигур.
Входные
многоугольники должны иметь фиксированное
направление обхода границы (допустим,
по часовой стрелке), и не иметь самопересечений.
Алгоритм может обрабатывать многоугольники
с дырками (дырки задаются как многоугольники
с противоположным направлением обхода),
но требует дополнительных алгоритмов
для определения, какие из многоугольников
являются дырками.
Алгоритм может
быть модифицирован для объединения
двух многоугольников.
Из координат
вершин многоугольников A и B составляются
два списка.
Вершины в каждом
из списков помечаются в соответствии
с тем, находятся ли они внутри другого
многоугольника или нет.
В оба списка
добавляются точки пересечения
многоугольников; между совпадающими
точками в разных списках устанавливаются
двусторонние связи.
Если ни одного
пересечений не найдено, возникает одна
из следующих ситуаций:
A внутри B —
вернуть A при отсечении, B при объединении.
B внутри A —
вернуть B при отсечении, A при объединении.
A и B не пересекаются
— вернуть пустое множество при
отсечении, A&B при объединении.
Составляется
список точек пересечения, в которых
граница многоугольника A при обходе
входит в многоугольник B. Следуя из
каждой такой точки по часовой стрелке
вдоль границ обоих многоугольников A
и B, можно найти множество областей
пересечения. В случае, когда A и B выпуклы,
многоугольник пересечения только один.
Таким же образом можно найти и объединение
многоугольников, в этом случае обход
нужно начинать с выходных точек.