Определить, есть ли у полигона отверстие?

Question

После экспериментов с некоторыми работами по триангуляции я натолкнулся на вопрос о том, как определить, есть ли у полигона дыру?

Я знаю, как обращаться с известной дырой, но не уверен, как определить, существует ли она.

Пример:

Учитывая следующие вершины:

0 ( 0, 0)
1 ( 0,20)
2 (20,20)
3 ( 0,20)
4 ( 2, 2)
5 ( 6, 2)
6 ( 6, 6)
7 ( 2, 6)

Как узнать, является ли это простой многоугольник, такой как:

или непростой / сложный многоугольник, подобный:

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

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

Answer 1

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

В вашем примере, другой макет графика будет, например, 0-1-5-6-2-3-7-4-0, где в результирующем многоугольнике вообще нет отверстия.

Если у вас есть ребра, вы можете выровнять их так, чтобы они образовывали круги, то есть группировать их с общим вторым / первым элементом: (0, 1), (1, 2), (2, 3), (3 , 0) и (4, 5), (5, 6), (6, 7), (7, 4). Если есть дыра, будет две или более таких групп, которые не могут быть сгруппированы дальше. Затем вы можете узнать, чьи точки находятся в области, окруженной другими точками, чтобы узнать, где находится дыра.

Answer 2

Выясните , если два несмежных отрезка пересекаются , и вы найдете разрыв между отверстием и многоугольником. Да, этот алгоритм O (n ² ), но немного предвидения может помочь сократить количество тестов.

Answer 3

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

Answer 4

Вы можете выбрать точку из одного круга "B" и судить, находится ли выбранная точка внутри или вне другого круга "A". Если есть, то вы получите дыру. Если нет, то вы выбираете точку из круга A и судите, находится ли точка внутри круга B, если есть, вы получаете отверстия.