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

Увертюра

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

Многоугольник может быть невыпуклым и может содержать произвольное количество отверстий. Это касается и произвольного многоугольника, который мы отсекаем, и отсекателя!

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

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

Направление обхода границ многоугольника: внешние границы обходим в направлении по часовой стрелке, внутренние границы - против часовой стрелки. Это сделано для того, чтобы при обходе границ многоугольника, внутренняя часть всегда бы находилась по правую сторону от направления обхода.

С позиции программирования задача решается довольно просто: реализация алгоритма будет сводиться к работе с двунаправленными кольцевыми списками.

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

    Комментарий Курова:

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

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

    Мой комментарий + комментарий Курова:

    Параметрическая формула задания отрезка: P(t) = P1 + (P2 - P1)t, где 0 <= t <= 1

    Мы пытаемся найти точку пересечения, после чего проверяем принадлежность её параметра t заданному интервалу от 0 до 1 что для одного ребра, что для другого. Если найденные значения параметров принадлежат этому интервалу, значит это действительно точка пересечения рёбер, если нет, то это пересечения не рёбер, а прямых, проходящих через эти рёбра.

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

    Комментарий Курова:

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

  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

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

Чтобы найти следующий внутренний многоугольник, надо начать обход со следующей точки входа.Но надо посмотреть, если эта точка уже есть в ранее найденом списке, то нового многоугольника мы не получим.

Вершины I3, I5, I8 уже присутствуют в ранее найденом списке. У нас получился один внутренний многоугольник. Других нет.

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

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

  • 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 является точкой пересечения

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

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

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

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

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

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

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

Есть такое правило. Границы отсекателя, попавшие внутрь отсекаемого многоугольника проделывают в нем отверстия. То есть в данном случае внешний многоугольник будет содержать от-верс-ти-е.

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