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

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

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

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

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

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

3. Глядя на углы:

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

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

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

введите здесь описание изображения

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

<сильный>3. глядя на барицентр :

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

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

введите здесь описание изображения

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

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

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


algorithm convex-polygon
person Ricky Bobby    schedule 04.07.2011    source источник
comment
Краткое предложение для метода 1: вместо того, чтобы фактически строить выпуклую оболочку, просто запустите алгоритм и завершите работу, как только/если он отбросит какие-либо точки.   -  person user786653    schedule 04.07.2011
comment
Я посмотрю на это. Спасибо.   -  person Ricky Bobby    schedule 04.07.2011
comment
Пропустил окно редактирования моего комментария. 'алгоритм' = Grahams Scan (он делает более или менее то, что предлагает ваш метод 2) . Кроме того, я знаю, что это не улучшит асимптотическое время выполнения, но упрощает распараллеливание задачи.   -  person user786653    schedule 04.07.2011
comment
У меня сложилось впечатление, что если у вас нет информации о ваших N баллах (они заказаны?), то вы не можете получить ничего лучше, чем N*log(N). Если я смогу найти доказательство, я буду рад поделиться им с вами, но сейчас это скорее ощущение, чем доказательство.   -  person B. Decoster    schedule 04.07.2011
comment
@ user786653: Для этого вам все равно придется сортировать элементы, поэтому в конечном итоге вы выполняете тот же объем работы (асимптотически говоря). Тем не менее, это все равно было бы хорошей оптимизацией для выполнения на практике, даже если вы лучше всего избавляетесь от меньшего, чем постоянный коэффициент.   -  person Mikola    schedule 05.07.2011

Ответы (2)


arrow_upward
3
arrow_downward

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

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

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

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

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

person Mikola    schedule 04.07.2011
comment
Большое спасибо, я внимательно изучу этот алгоритм. - person Ricky Bobby; 05.07.2011

arrow_upward
1
arrow_downward

Я думал, начиная с Википедии на Grahams Scan:

Делайте все вплоть до "сортировать точки по полярному углу с точками [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

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

person user786653    schedule 04.07.2011