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

Question

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

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

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

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

Спасибо заранее,

/роджер

Answer 1

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

Answer 2

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

Один алгоритм для этого - Graham-Scan со сложностью 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. Надеюсь это поможет!