Тематическое задание 4.7. Отсечение одного полигона границами другого: отсечение Вейлера-Азертона Уровень сложности III.
Отсечение Вейлера-Азертона является наиболее общим механизмом отсечения из всех, которые мы изучали. Оно отсекает произвольный полигон границами любого (возможно, невыпуклого) отсекающего полигона. Эти полигоны могут даже содержать отверстия.
9 Ф. Хилл
Векторные инструменты для графики
Елгоритм Сазерленда-Ходгмана, который мы изучали в тематическом задании 4.6, использует выпуклость отсекающего полигона в том смысле, что применяются внутреннее и внешнее полупространства. Однако в некоторых приложениях, таких как удаление невидимых поверхностей или визуализация теней, приходится отсекать один невыпуклый полигон границами другого. В таких случаях отсечение становится более сложным. Метод Вейлера-Ефертона отсекает любой полигон границами любого другого, даже если в них содержатся отверстия. Он также позволяет применять теоретико-множественные понятия: объкдинкник (union), пкркскчкник (intersection) и ремносчь (difference) к двум полигонам, которые мы будем рассматривать в тематическом задании 4.8.
Рис. 4.55. Отсечение Вейлера-Афертона Начнем с простого примера, показанного на рис. 4.55. Мдесь два невыпуклых полигона, обозначенных SUBJ и CLIP, задаются списками вершин (a, b,c,d)n (А, В, С, D) соответственно. Примем соглашение располагать вершины в списке таким образом, чтобы внутренняя часть полигона находилась справа от каждого ребра, когда мы обходим полигон от вершины к вершине согласно этому списку. Например, внутренняя часть полигона SUBJ располагается справа от ребра, идущего от с к d, и справа от ребра, идущего от d к а. Это аналогично перечислению вершин «по часовой стрелке».
Все точки пересечения двух данных полигонов определяются и помещаются в специальный список (см. ниже). В данном примере таких пересечений шесть. Для отсечения полигона SUBJ границами полигона CLIP будем идти по SUBJ в прямом направлении (так, чтобы его внутренняя часть была справа) до тех пор, пока не будет обнаружено «входящее» пересечение, то есть точка, являющаяся границей перехода полигона SUBJ из внешней части полигона CLIP в его внутреннюю часть. Так мы находим точку 1, и она заносится в выходной список, где записываются данные отсеченного полигона(ов).