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

Многоугольник может быть невыпуклым и может содержать произвольное кол-во отверстий (как у многоугольника, так и у отсекателя). Реализация алгоритма будет сводится к работе с двунаправленными кольцевыми списками.

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

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

На этапе ввода исходных данных необходимо сформировать двунаправленные кольцевые списки для каждой границы каждого многоугольника (кол-во границ - 2 внешние + все внутренние отверстия)

Прежде чем перейти к непосредственно отсечению, требуется найти все точки пересечения многоугольника и отсекателя. Найденные точки пересечения необходимо добавить на соответствующие места в ранее сформированные списки границ (Точка пересечения попадает в 2 списка). Целесообразно установить двунаправленную связь между элементами списков, содержащих информацию об одноименных точках пересечения (то есть 3 указателя в элементе списка: предыдущий, следующий и, если точка пересечения, соответсвующий элемент в другом списке)

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

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

Пример с лекции:

Количество точек отсечения должно быть четным!

Точки пересечения:

• Точки входа: I1 I3 I5 I8
• Точки выхода: I2 I4 I6 I7

Сформируем списки для каждой границы (эти списки уже с учетом точек пересечения):

• Информация о внешней границе отсекаемого многоугольника: A1 A2 I1 A3 I2 A4 I3 A5 I4 I5 I6 A1
• Информация о внутренней границе отсекаемого многоугольника: А6 I7 A7 I8 A8 A6
• Информация о внешней границе отсекателя: C1 I6 I1 C2 I2 I8 C3 I7 I3 C4 C5 C1
• Информация о внутренней границе отсекателя: C6 I4 C7 C8 I5 C6

Приступаем к отсечению. Надо найти первый внутренний многоугольник, просмотр начинаем с первой точки входа - I1. Эту точку пересечения мы должны найти в списке границ отсекаемого многоугольника. С этой точки мы начнем движение вдоль рёбер многоугольника и просмотр списка. Движение выполняем двигаясь от начала списка в сторону его конца. Все просмотренные вершины мы копируем в список вершин результирующего многоугольника:

I1 A3 I2 -> (В точке пересечения переходим от списка границ одного многоугольника к списку границ второго многоугольника) -> I8 -> (В этой точке мы поворачиваем направо. Возвращаемся к списку границ отсекаемого многоугольника и видим, что I8 соответствует пересечению ребра, относящегося к внутренней границе.) -> A8 A6 I7 -> (опять точка пересечения) -> I3 -> (опять точка пересечения) -> A5 I4 -> (опять точка пересечения) -> C7 C8 I5 I6 I1

Мы достигли начальной точки - точки пересечения, с которой мы начали движения. Контур замкнулся. Процесс просмотра списка прекращен. У нас получился один внутренний многоугольник. Других нет.

Чтобы получить внешний многоугольник, надо начинать просмотр списка с точки пересечения, являющейся точкой выхода. Отличие процедуры получения внешних многоугольников от внутренних - просмотр границ отсекателя (списка, хранящего информацию о вершинах отсекателя) надо просматривать, двигаясь от конца к началу (то есть в обратных направлениях).

Внешние многоугольники:

• I2 A4 I3 I7 A7 I8 I2
• I4 I5 C8 C7 I4
• I6 A1 A2 I1 I6

Есть еще I7, но он входит в первый внешний многоугольник.

Список пересечений, являющихся точками выхода исчерпан, нашли все внешние многоугольники.

Распознавание точек входа и точек выхода

Правило:

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

Рассмотрим на простом примере:

• Для распознавания первой точки пересечения найдем векторное произведение вектор ребра отсекаемого многоугольника AjAj+1 и вектора, с которым пересекается CiCi+1. В данной ситуации это произведение AjAj+1 * CiCi+1 > 0, следовательно это точка входа.
• Второе векторное произведение AjAj+1 * Ci+2Ci+3 < 0, следовательно это точка выхода.

Частные случаи

1. Вершины многоугольника расположены на ребрах отсекателя.

Вершины будут являться не просто вершинами, а точками пересечения.

Искали точки пересечения, обнаружили, что их нечетное количество. Значит, одна из точек - точка касания. Точка I1 не является точкой пересечения, она является точкой касания. Мы её должны исключить из рассмотрения.

Как распознать, какая из точек I1 I2 является точкой пересечения, а какая - точкой касания?

После вопроса на консультации: Коротко: если точка пересечения совпадает с началом ребра, то это пересечение, если с концом - то это касание.

Мудрёно: если взять соседнюю точку по направлению вектора ребра и она будет принадлежать ребру - то это пересечение, иначе касание

Точка I2 является точкой пересечения

2. Случай, когда границы отсекаемого многоугольника и отсекателя не пересекаются.

Здесь стоит отметить, что предыдущий алгоритм, менее мощный, работающий с выпуклым отсекателем, справляется без дополнительных усилий с решением подробной задачи. Здесь, если нет пересечений, задачу просто так не решить.

Чтобы справиться с такой ситуацией, надо определить, как многоугольники расположены относительно друг друга. Геометрически задача сводится к определению принадлежности пикселей заданной области. Надо луч испускать из точки одного многоугольника и подсчитывать количество пересечений с рёбрами другого многоугольника.

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

Количество точек пересечения луча, направленного из вершины отсекателя с ребрами отсекаемого многоугольника равно двум (четное), а количество пересечений луча, испущенного из вершины отсекаемого многоугольника равно одному (нечетное). Можно сделать вывод, что отсекатель является объемлющим многоугольником для отсекаемого.

Отсекатель находится внутри отсекаемого многоугольника.

Количество пересечений луча, испущенного из вершины отсекателя равно единице (нечетное количество), у второго луча ноль (четное количество). Таким образом, отсекаемый многоугольник является объемлющим по отношению к отсекателю.

3. Совсем неприятный случай. Вершина отсекаемого многоугольника расположена на ребре отсекателя.

Описание: Задача является задачей тысячелетия, 100 куровых из 10
Применение: Задушить студента на экзамене и отправить на пересдачу
Решение: "Дед, а тебе не кажется, что решить задачу тысячелетия за час звучит нереально?"

Ну а если серьезно то проблема тут примерно та же, что и в 1 случае: непонятно, какая точка - точка пересечения, какая - точка касания. Придется обрабатывать кучу случаев при нахождении пересечений. Самое ужасно - пересечение с углом отсекателя угла многоугольника, потому что формально там будет аж 4 пересечения!

Следующий вопрос: 19. Модели трехмерных объектов. Требования, предъявляемые к моделям.

Предыдущий вопрос: 17. Отсечение многоугольников. Алгоритм Сазерленда Ходжмена.