18. Отсечение многоугольников невыпуклыми областями. Алгоритм Вейлера Азертона.

Контуры многоугольников должны задаваться определенным образом: внешняя граница КАЖДОГО многоугольника обходится по часовой стрелке, а внутренние границы – против часовой стрелки, чтобы внутренняя область всегда лежала по правую сторону от направления обхода.

В результате отсечения получаются многоугольники, ребра которых являются либо ребрами исходного многоугольника, либо ребрами отсекателя – никаких новых рёбер в результате отсечения не получается.

Точки пересечения делятся на входы и выходы с помощью векторного произведения вектора стороны отсекаемого на вектор стороны отсекателя. Положительное – вход, отрицательное – выход.

Для нахождения внутренних многоугольников движение начинаем с очередной точки входа, причём просмотр начинается со списка отсекаемого многоугольника. Просматриваемые вершины заносятся в список вершин результирующего многоугольника. Чтобы находить внешние многоугольники, движение надо начинать с очередной точки выхода. Списки границ отсекателя надо просматривать В ОБРАТНОМ направлении.

1. Ввод количества вершин внешней границы отсекаемого многоугольника и их координат.
2. Ввод количества отверстий в отсекаемом многоугольнике, по каждому отверстию - количества вершин и их координат.
3. Ввод количества вершин внешней границы отсекателя и их координат.
4. Ввод количества отверстий в отсекателе, по каждому отверстию - количества вершин и их координат.
5. Формирование кольцевых двунаправленных списков вершин по всем границам отсекаемого многоугольника.
6. Формирование кольцевых двунаправленных списков вершин по всем границам отсекателя.
7. Вычисление координат всех точек пересечения отсекаемого многоугольника и отсекателя.
8. Добавление всех найденных точек пересечения на соответствующие места в списки вершин многоугольников.
9. Определение типа каждой точки пересечения и формирование двух списков - точек входа и точек выхода.
10. Определение границ многоугольников, не имеющих пересечений. Границы отсекаемого многоугольника, лежащие вне отсекателя, поместить в список внешней принадлежности, границы, попавшие внутрь отсекателя - в список внутренней принадлежности. Поместить границы отсекателя, попавшие внутрь отсекаемого многоугольника, в оба списка принадлежности. (Границы отсекателя, лежащие за пределами отсекаемого многоугольника, проигнорировать).
11. Проведение собственно отсечения. Организация для этого цикла по всем точкам входа.
12. Нахождение в списке вершин отсекаемого многоугольника очередной точки входа.
13. Просмотр списка вершин отсекаемого многоугольника до нахождения точки пересечения. Копирование просмотренных вершин в список внутренней принадлежности.
14. Переход к списку вершин отсекателя и поиск в нем одноименной точки пересечения.
15. Просмотр списка вершин отсекателя до нахождения точки пересечения. Копирование просмотренных вкршин в список внутренней принадлежности.
16. Сравнение найденной точки пересечения с первой точкой: если эти точки не совпадают, то преход к п. 13, иначе к п. 17.
17. Определение необходимости формирования второй границы отсеченного многоугольника: если не все границы отсекаемого многоугольника имеют пересечение с границами отсекателя, то необходим поиск другой границы, иначе перход к п.19.
18. Получение второй границы результирующего многоугольника. В этом случае можно использовать правило:

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

19. Конец цикла (выбор следующей точки входа из списка, если он не пуст и переход к п. 12, иначе выход из цикла).
20. Конец.