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

Алгоритм Грейнера-Хормана используется в компьютерной графике для отсечения полигонов . ^{[ 1 ]} Он работает лучше, чем алгоритм отсечения Ватти , но не может справиться с вырождениями . ^{[ 2 ]} Он может обрабатывать как самопересекающиеся, так и невыпуклые многоугольники. Его можно тривиально обобщить для вычисления других логических операций над многоугольниками , таких как объединение и разность.

Алгоритм основан на определении «внутренности» многоугольника по числу витков . Он считает, что области с нечетным числом витков находятся внутри многоугольника; это известно как правило чет-нечет . В качестве входных данных он принимает два списка полигонов.

В своей исходной форме алгоритм разделен на три этапа:

На первом этапе вычисляются попарные пересечения ребер многоугольников. В оба полигона в точках пересечения вставляются дополнительные вершины; вершина пересечения содержит указатель на свою копию в другом многоугольнике.
На втором этапе каждый перекресток помечается либо как въездной, либо как выездной перекресток . Это достигается путем оценки правила четности-нечета для первой вершины, которое позволяет узнать, находится ли первая вершина внутри или снаружи другого многоугольника. Затем, следуя границам многоугольника, пересечения отмечаются чередующимися флажками (следующее пересечение после входного пересечения должно быть выходным).
На третьем этапе формируется результат. Алгоритм начинается с необработанного перекрестка и выбирает направление обхода на основе флага входа/выхода: для входного пересечения он движется вперед, а для выходного пересечения он движется в обратном направлении. Вершины добавляются к результату до тех пор, пока не будет найдено следующее пересечение; затем алгоритм переключается на соответствующую вершину пересечения в другом многоугольнике и снова выбирает направление обхода, используя то же правило. Если следующее пересечение уже обработано, алгоритм завершает текущий компонент вывода и начинает снова с необработанного пересечения. Вывод считается завершенным, когда необработанных пересечений больше нет.

Алгоритм не ограничивается полигонами и может обрабатывать произвольные параметрические кривые как сегменты, если существует подходящая процедура попарного пересечения.

Основным недостатком оригинального алгоритма Грейнера-Хормана является тот факт, что он не может обрабатывать вырождения, такие как общие ребра или пересечения точно в вершине. В оригинальной статье предлагается возмущать вершины, чтобы удалить их.

См. также

Ссылки

^ Грейнер, Гюнтер; Кай Хорманн (1998). «Эффективное отсечение произвольных полигонов» . Транзакции ACM с графикой . 17 (2): 71–83. дои : 10.1145/274363.274364 .
^ Ионел Дэниел Строу. «Эффективное отсечение произвольных многоугольников» . Проверено 17 мая 2014 г.

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

Географическое отсечение Описывает алгоритмы отсечения D3.js. в
https://github.com/helderco/univ-polyclip Реализация на Python и Java.
https://github.com/w8r/GreinerHormann Реализация на JavaScript.
JTS Topological Suite Топологический пакет с реализацией Java.

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

[1] Грейнер, Гюнтер; Кай Хорманн (1998). «Эффективное отсечение произвольных полигонов» . Транзакции ACM с графикой . 17 (2): 71–83. дои : 10.1145/274363.274364 .

[2] Ионел Дэниел Строу. «Эффективное отсечение произвольных многоугольников» . Проверено 17 мая 2014 г.

[ 1 ]

[ 2 ]