Лучший алгоритм нахождения ребер (многоугольника) вершин

Question

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

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

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

Есть предложения?

Answer 1

Хитрость с многогранными алгоритмами заключается в выборе того, который подходит вашему входу и вашему желаемому результату, поскольку существует более одного способа представления многогранника, и преобразование между представлениями может быть дорогостоящим. В этом случае вы начинаете с точек и хотите закончить вершинами, поэтому алгоритм сканирования Грэма для вычисления вершин выпуклой оболочки должен сработать, хотя это может занять некоторые усилия, чтобы продлить его за 2-й случай. Это O ( n log n ) в количестве входных вершин.

Answer 2

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

При поиске вы должны найти соответствующий алгоритм.

Answer 3

Выпуклая оболочка является одной из наиболее исследованных проблем вычислительной геометрии. Сканирование Грэма - один из более простых алгоритмов выпуклой оболочки , но, конечно, не единственный. Алгоритм упаковки подарков , также называемый маршем Джарвиса, является самым простым из известных мне. Репозиторий алгоритма Stony Brook имеет несколько реализаций алгоритмов выпуклой оболочки на C и C ++. Геометрия в действии показывает в основном применение выпуклых оболочек. Вот коллекция низкоразмерных и произвольно-размерных программ вычисления выпуклой оболочки.