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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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