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

Алгоритм отсечения Ватти ^[1] используется в компьютерной графике . Он позволяет обрезать любое количество предметных полигонов произвольной формы любым количеством обрезающих полигонов произвольной формы . В отличие от алгоритмов обрезки полигонов Сазерленда-Ходжмана и Вейлера-Атертона , алгоритм Ватти не ограничивает типы полигонов, которые можно использовать в качестве объектов или клипов. даже сложные (самопересекающиеся) многоугольники и многоугольники с отверстиями Можно обрабатывать . Алгоритм вообще применим только в 2D пространстве .

Описание

Отсечение определяется как взаимодействие полигонов объекта и обрезки. Хотя отсечение обычно включает в себя поиск пересечений (областей перекрытия) полигонов объекта и обрезки, алгоритмы отсечения также могут применяться с другими логическими операциями отсечения: разность , когда отсечения полигонов удаляют перекрывающиеся области из объекта; Union , где отсечение возвращает области, покрытые либо объектом, либо обрезанием полигонов, и; xor , где обрезка возвращает области, покрытые полигонами субъекта или обрезки, за исключением случаев, когда они покрыты как субъектом, так и полигонами обрезки.

Алгоритм Ватти включает в себя упорядоченную обработку как субъектных, так и обтравочных краев многоугольника, начиная с самых нижних краев и продвигаясь к верху; концептуально это похоже на алгоритм Бентли-Оттмана . Этот подход с помощью линий развертки делит проблемное пространство линиями сканирования , воображаемыми горизонтальными линиями, которые проходят через каждую вершину участвующих многоугольников. Эти строки сканирования очерчивают лучи сканирования – промежутки между соседними строками сканирования. Эти лучи сканирования обрабатываются по очереди, начиная с самого нижнего луча сканирования, при этом алгоритм добавляет точки пересечения этих лучей сканирования в полигоны решения.

См. также

Ссылки

^ Бала Р. Ватти. «Общее решение проблемы отсечения полигонов» , Communications of the ACM, том 35, выпуск 7 (июль 1992 г.), стр. 56–63.

Внешние ссылки

Clipper — бесплатная реализация алгоритма Ватти с открытым исходным кодом.

Эта компьютерной графике статья, посвященная , незавершена . Вы можете помочь Википедии, расширив ее .

[1] Бала Р. Ватти. «Общее решение проблемы отсечения полигонов» , Communications of the ACM, том 35, выпуск 7 (июль 1992 г.), стр. 56–63.

[1]