Удалить дыры в многоугольнике

Question

У меня есть многоугольник, определенный массивом точек.

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

Мои вопросы: как я могу пропустить эти отверстия и просто получить внешние точки многоугольника?

Или что будет таким же и, вероятно, более простым: какой алгоритм проверки, находится ли точка внутри многоугольника, следует использовать для обнаружения точек в отверстиях многоугольника как внутренних точек?

Заранее спасибо,

/ * роджер 1011 *

Answer 1

Сначала найдите все пересечения ребер, добавьте эти пересечения в список вершин и разбейте ребра в этих пересечениях. Затем начните с одной вершины, которая, очевидно, является внешней (например, «самой правой») и проследите контур, добавив ребра и вершины в наборы результатов. Отслеживание контура происходит просто по краю с минимальным углом к ​​последнему краю.

Answer 2

Возможно, вы захотите найти выпуклую оболочку всех точек в вашем многоугольнике.

Один алгоритм для этого - Грэм-Скан со сложностью O (nlgn). Из Кормена:

Let Q be the set of all points in your polygon
Graham-Scan(Q)

1  let p0 be the point in q with the minimum y-coordinate or the leftmost in case of tie
2  let (p1, p2,...,pm) be the remaining points in Q, sorted by polar angle around p0
       if more than one point shares the same polar angle, keep the farthest point

3  let S be an empty stack
4  PUSH(p0, S)
5  PUSH(p1, S)
6  PUSH(p2, S)
7  for i = 3 to m
8    while the angle formed by points NEXT_TO_TOP(S), TOP(S), and pi makes a non-left turn
9        POP(S)
10   PUSH(pi, S)
11 return S

S теперь содержит все внешние точки вашего многоугольника. Тебе придется заняться полярной математикой, но это довольно просто. Сортировка по полярному порядку сортирует все точки их котангенса с самой нижней точкой. Я забыл код для проверки правильного поворота, но он есть в Интернете, если вы просто ищете в Graham-Scan. Надеюсь, это поможет!