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

Question

Я знаю, что есть алгоритм O (n log n) в худшем случае для нахождения выпуклой оболочки сложного многоугольника и алгоритм O (n) в худшем случае для нахождения выпуклой оболочки простого многоугольника.Существует ли алгоритм O (n) в худшем случае для нахождения выпуклой оболочки сложного многоугольника?

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

Answer 1

Если ваши наборы точек таковы, что некоторый механизм сортировки, не основанный на сравнении (например, сортировка по основанию), будет быстрее, чем методы, основанные на сравнении, то, похоже, вы можете использовать алгоритм сканирования Грэма (http://www.math.ucsd.edu/~ronspubs/72_10_convex_hull.pdf) для его вычисления).Во временной сложности сканирования Грэма доминирует шаг сортировки. Остальное линейно.

Answer 2

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

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

Answer 3

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

Answer 4

В общем, нет, не существует решения O (n).Существует пиксельная версия, которая лучше, чем O (n log n).Это, однако, настолько затруднено другими способами, что вы с ума сошли бы, чтобы использовать это на практике.

Вы визуализируете первый многоугольник (используя вершины 0, 1, 2) в пространство экрана, а затем заново визуализируете сами вершины, используя различный идентификатор, чтобы их можно было идентифицировать позже.Например, вы можете очистить буфер кадра для RGBA ffffffff и использовать fffffffe для пространства, которое покрыто выпуклой оболочкой.Каждая вершина будет отображаться с использованием своего идентификатора в качестве RGBA;00000000, 00000001 и т. Д.

16-битный пример:

fffffffffffffff
fffffff0fffffff
ffffffeeeffffff
fffffeeeeefffff
ffffeeeeeeeffff
fffeeeeeeeeefff
ff2eeeeeeeee1ff
fffffffffffffff

Проверка новой точки - это простой поиск в текущем буфере кадров.Если занимаемый им пиксель «заштрихован» многоугольником или идентификатором вершины, новая вершина отклоняется.

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

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

Хотя сложность алгоритма равна O (n) с количеством вершин, его недостатки очевидны. Никто в здравом уме не использовал бы его, если бы у них не было смешного, безумного, ошеломляющего числа точек для обработки так, чтобы почти каждая вершина была немедленно отклонена, и если они не могли принять ограничение псевдонима.

Друзья не позволяют друзьям реализовывать этот алгоритм.