Френсис Хилл

Рис 4.56. Приложение метода Вейлера-Азертона Пример более сложных полигонов, содержащих отверстия, показан на рис. 4.57. Те вершины, которые описывают отверстия, также вносятся в список в таком порядке, чтобы внутренняя часть полигона располагалась справа от ребра. (В случае отверстий это можно назвать порядком «против часовой стрелки».) Применяется то же правило, что и раньше: поворот и обход другого полигона в его прямом направлении. Если начать с регистрации точки пересечения 1, то образуется полигон (1, 2, 3,4, 5, i, 6, Я). Затем, начиная с регистрации точки пересечения 7, создаем полигон (7,8,9, с, 10, F). Какое входное пересечение нужно использовать для создания третьего полигона? Это хорошее упражнение для построения списков SUBJLIST и CLIPLIST и для прослеживания операций алгоритма отсечения Вейлера-Азертона.

Как и во многих других алгоритмах, в основе которых лежат пересечения, нам требуется проверить, как данный алгоритм работает в случаях, когда ребра полигонов CLIP и SUBJ параллельны и совпадают на некотором конечном отрезке. Для того чтобы выполнить такую проверку, создадим такие полигоны CLIP и SUBJ - в файлах или разрешив пользователю задавать их с помощью мыши. В этой реализации мы тщательно рассмотрим, как будет вести себя алгоритм в следующих ситуациях: О Некоторые ребра SUBJ и CLIP параллельны и совпадают на некотором конечном отрезке.

О SUBJ или CLIP или они оба являются полигонами с особенностями.

О Некоторые ребра SUBJ и CLIP совпадают только в своих концевых точках.

О CLIP и SUBJ не пересекаются.

О SUBJ целиком лежит внутри отверстия CLIP.

Глава 4. Векторные инструменты для графики

Френсис Хилл

Рис 4.57. Отсечение Вейлера-Азертона: полигоны с отверстиями Тематическое задание 4.8. Булевы операции с полигонами Уровень сложности III.

Если рассмотреть полигон как множество точек (множество всех точек на границе или во внутренней части полигона), то результатом операции отсечения Вейлера-Азертона будет пересечение (intersection) двух полигонов - множество всех точек, принадлежащих обоим полигонам: CLIP и SUBJ. Полигоны на выходе алгоритма Вейлера-Азертона состоят из точек, лежащих одновременно внутри CLIP и исходного полигона SUBJ. В этом тематическом задании мы перейдем от пересечений к более общим теоретико-множественным операциям с полигонами, которые часто называют «булевыми» («Boolean») операциями. Потребность в таких операциях часто возникает и при моделировании [Mortenson, 85], и в графике (см. главу 14). В общем случае для двух множеств точек А и В определены следующие три теоретико-множественные операции:


⇐ Предыдущая| |Следующая ⇒