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

Question

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

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

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

Есть какие-нибудь предложения?

Answer 1

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

Answer 2

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

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

Answer 3

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