Алгоритм отсечения Грейнера – Хормана - Greiner–Hormann clipping algorithm

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

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

В первоначальном виде алгоритм разделен на три этапа:

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

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

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

Смотрите также

Рекомендации

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

внешняя ссылка