Отсечение Вейлера- Азертона

Этот процесс продолжается до тех пор, пока не встретиться начальная вершина. Внутренние границы обрабатываемого многоугольника обходятся против часовой стрелки (смотри рисунок).

Более формальная запись этого алгоритма имеет следующий вид:

1) вычислить все пересечения обрабатываемого и отсекающего многоугольников;

2) добавить все эти пересечения к спискам вершин обрабатываемого и отсекающего многоугольников. Поместить все точки пересечения и установить двусторонние связи между списками вершин обрабатываемого и отсекающего многоугольников для каждой такой точки;

3) обработать непересекающиеся границы многоугольников;

4) установить два списка принадлежности, один - для границ, лежащих внутри отсекающего многоугольника, и другой- для границ, лежащих вне отсекателя. Проигнорировать такие границы отсекателя, которые лежат вне обрабатывающего многоугольника. Границы отсекателя, попавшие внутрь обрабатывающего многоугольника, образуют в нем дыры. Следовательно, копии границ отсекающего многоугольника должны попасть в оба писка принадлежности: внутренний и внешний. Занести эти границы в соответствующие списки принадлежности;

5) создать два списка вершин, являющихся точками пересечения;

6) один- список входов – содержит только пресечения, образованные ребрами обрабатываемого многоугольника, которые входят внутрь отсекателя. Другой- список выходов – содержит только пересечения, образованные ребрами обрабатываемого многоугольника, которые выходят изнутри отсекателя. Типы точек пересечения будут чередоваться при обходе границы. Поэтому достаточно определить тип только у одной из каждой пары точек пересечения;

7) реализовать отсечение;

8) поиск многоугольников, лежащих внутри отсекателя, ведется с помощью следующей процедуры. Взять точку пересечения из списка входов. Если этот список пуст, то поиск завершен. Просматривать список вершин обрабатываемого многоугольника до тех пор, покане обнаружиться пересечение. Скопировать вершины из списка вершин обрабатываемого многоугольника вплоть до этого пересечения в список внутренней принадлежности. Используя двустороннюю связь, перейти к списку вершин отсекающего многоугольника. Просматривать список вершин отсекателя до тех пор, пока не обнаружиться пересечение. Скопировать вершины из списка вершин отсекателя вплоть до этого пересечения в список внутренней принадлежности. Вернуться назад в список вершин обрабатываемого многоугольника. Повторять эти действия до тех пор, пока не будет достигнута начальная вершина. В этот момент новый внутренний многоугольник замыкается;

9) поиск многоугольников, лежащих вне отсекателя, ведется с помощью такой же процедуры, за исключением того что начальная точка пересечения берется из списка выходов, а вершины из списка вершин отсекателя просматриваются в обратом порядке. Списки вершин многоугольников при этом копируются в список внешней принадлежности. Связать все отверстия, т.е. внутренние границы, с соответствующими им внешними границами. Поскольку внешние границы ориентированы по часовой стрелке, а внутренние границы - против часовой стрелки, эту операцию удобно выполнить путем проверки ориентации границ;

10) процесс завершен.

Дата добавления: 2014-01-13