Отсечение многоугольников невыпуклыми областями. Алгоритм Вейлера Азертона
Контуры многоугольников должны задаваться определенным образом: внешняя граница КАЖДОГО многоугольника обходится по часовой стрелке, а внутренние границы – против часовой стрелки, чтобы внутренняя область всегда лежала по правую сторону от направления обхода.
В результате отсечения получаются многоугольники, ребра которых являются либо ребрами исходного многоугольника, либо ребрами отсекателя – никаких новых рёбер в результате отсечения не получается.
Точки пересечения делятся на входы и выходы с помощью векторного произведения вектора стороны отсекаемого на вектор стороны отсекателя. Положительное – вход, отрицательное – выход.
Для нахождения внутренних многоугольников движение начинаем с очередной точки входа, причём просмотр начинается со списка отсекаемого многоугольника. Просматриваемые вершины заносятся в список вершин результирующего многоугольника. Чтобы находить внешние многоугольники, движение надо начинать с очередной точки выхода. Списки границ отсекателя надо просматривать В ОБРАТНОМ направлении.
Дата добавления: 2019-01-14; просмотров: 293; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!