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

Question

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

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

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

Предположим, что существует пересечение между сегментами (P_i, P_i + 1) и (P_j, P_j + 1) в точке Q с j> i.

Случай 1: Я разбил многоугольник на 2 многоугольника, [Q, P_i + 1, ..., P_j, Q] и [Q, P_j + 1, ..., P_i, Q ].

Случай 2: Я вставляю вершину V в многоугольник, и в результате получается многоугольник [P1, ..., P_i, V, P_i + 1, ..., P_j, Q, P_j +1, ..., P1]

Таким образом, недостающий фрагмент информации, который мне нужен, - это выяснить, является ли цикл, образованный [Q, P_i + 1, ..., P_j], «внешним» циклом (случай 1) или «внутренним» циклом ( дело 2).

Я читал материал о подписанной области многоугольника, образованного циклом, но не все понял. Я не ищу самый эффективный алгоритм, просто тот, который будет работать. Спасибо!

Answer 1

Сначала построим плоский линейный график (PSLG) многоугольника. Другими словами, рассматривайте полигон как группу сегментов и разделенных сегментов на каждом пересечении. Существует крайний случай, когда два или более сегмента могут перекрываться в нетривиальном сегменте, а не в точке. В PSLG сегмент пересечения должен быть единым, отдельным сегментом, но нам также нужно знать, сколько сегментов линии перекрывают сегмент. Следовательно, этот вырожденный многоугольник (A-B-C-D-E-F-G-A)

A-C-B-D
|    /
|   /
G--E---F

превращается в

   3
*-*-*-*
|    /
|   /
*--*---* ,
     2

опуская все метки, на которых написано 1.

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

Теперь у нас есть такая структура данных.

   3
t-u-v-w
|    /
|   /
x--y---z ,
     2

t: t-u, t-x, t-y
u: u-v (3), u-t
v: v-w, v-u (3)
w: w-v, w-y
x: x-y, x-t
y: y-z (2), y-w, y-x
z: z-y (2)

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

t-u -> t-x
t-x -> t-u
u-v (3) -> u-t
u-t -> u-v (3)
v-w -> v-u (3)
v-u (3) -> v-w
w-v -> w-y
w-y -> w-v
x-y -> x-t
x-t -> x-y
y-z (2) -> y-w
y-w -> y-x
y-x -> y-z (2)
z-y (2) -> z-y (2)

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

t-u -> x-t
x-t -> y-x
y-x -> z-y (2)
z-y (2) -> y-z (2)
y-z (2) -> w-y
w-y -> v-w
v-w -> u-v (3)
u-v (3) -> t-u

t-x -> u-t
u-t -> v-u (3)
v-u (3) -> w-v
w-v -> y-w
y-w -> x-y
x-y -> t-x

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

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

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

Answer 2

Если вы разбиваете сложные многоугольники на простые многоугольники на пересечениях; то:

• вариант 1: простые многоугольники не перекрываются

• вариант 2: простые многоугольники перекрываются, и один из простых многоугольников фактически является "обратным многоугольником" (описывающим, что исключать, и не описывающим, что включать).

Эта разница может быть определена с помощью теста «все ли вершины одного многоугольника внутри другого многоугольника или касаются другого многоугольника».

Обратите внимание, что для случая 2 вы можете вставить один многоугольник обратно в другой, чтобы в итоге получился один простой многоугольник (например, для вашей диаграммы вы должны получить "P1, пересечение, P3, P2, пересечение, P4, P5, P6 ").

Однако есть и другие случаи, которые вы пропустили. Например, начиная со своей второй диаграммы (для случая 2) перетащите P3 вверх, чтобы она находилась выше линии от P6 до P1 (в результате чего с обеих сторон части двух ребер, включающих P3, не будет многоугольника). В качестве другого примера рассмотрим «рисунок 8» с шестью вершинами, где в середине есть два одинаковых ребра (которые можно преобразовать в простой прямоугольник, удалив оба средних ребра).

Для еще большего удовольствия рассмотрим что-то вроде этого (но без внешнего круга):

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