Алгоритм поиска, если множество точек описывает выпуклую оболочку

Question

Я хотел бы проверить, описывает ли набор из N точек выпуклый многоугольник или нет

Мне было интересно, есть ли хороший алгоритм для этого?

Вот некоторые подходы, которые я подумализ:

---

1. Алгоритм выпуклой оболочки:

Если набор равен его выпуклой оболочке, то он выпуклый.Сложность такого алгоритма составляет O (n * LN (N)).Но у меня было ощущение, что это было похоже на разбивание бабочки на колесе.

---

3. Взгляд на углы:

Тогда я подумал проверить, неуглы двух последовательных векторов никогда не превышают 180 °.Но так как мои очки не упорядочены, мне нужно проверить все комбинации из 3 последовательных очков, что усложняет задачу O (n3). (Должен быть способ сделать это лучше)

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

Например, в этом случае я нахожу выпуклую форму, если взять слева направо:

Так что для этого решения мне может понадобиться хороший алгоритм для выбора точек.

---

3.глядя на барицентр:

Я думаю, что проверка того, находится ли барицентр всех трех последовательных точек внутри фигуры, покажет мне, является ли фигура выпуклой или нет.

Вот чтоЯ имею в виду (G - барицентр каждого треугольника):

для этого решения я могу без проблем выбрать точки слева направо.если сложность проверки, находится ли G в форме, равна O (N), то общая сложность будет примерно равна O (N2).

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

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

Answer 1

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

http://cgm.cs.mcgill.ca/~athens/cs601/

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

http://softsurfer.com/Archive/algorithm_0203/algorithm_0203.htm#Melkman%20Algorithm

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

Answer 2

Я думал, начиная с Википедии о сканировании Грахамса :

Делайте все до и включая «сортировку точек по полярному углу с точками [1]».

тогда:

for i = 3 to N:
    if ccw(points[i-2], points[i-1], points[i]) < 0: # Note this inequality might need checking
        return NotConvex
return Convex

Как сортировка, так и проверка выпуклости хорошо подходят для распараллеливания и могут быть объединены для еще большего ускорения при необходимости.