Лучший алгоритм нахождения ребер (многоугольника) вершин
У меня есть большой массив вершин, некоторые из них являются ребрами, некоторые являются избыточными (внутри фигуры), и я хочу их удалить.
Самый простой алгоритм, который я мог придумать, это проверять одну за другой, попадают ли они в форму, сформированную другими. Но это должен быть очень медленный алгоритм.
Я думал о том, чтобы выбрать один из края (самый дальний от начала координат в примере) и рассчитать самый длинный путь из этого начала... должен получить путь края, верно?
Любое предложение?
3 ответа
Хитрость с многогранными алгоритмами состоит в том, чтобы выбрать тот, который соответствует вашему вводу и желаемому выводу, поскольку существует более одного способа представления многогранника, и преобразование между представлениями может быть дорогостоящим. В этом случае вы начинаете с точек и хотите закончить вершинами, поэтому алгоритм сканирования Грэма для вычисления вершин выпуклой оболочки должен сработать, хотя может потребоваться некоторое усилие, чтобы расширить его после двумерного случая. Это O (n log n) в количестве входных вершин.
Я не знаю, каков наилучший алгоритм для нахождения этого многоугольника, но нужный многоугольник называется "Выпуклая оболочка".
Ища это, вы должны найти соответствующий алгоритм.
Выпуклая оболочка является одной из наиболее исследованных проблем вычислительной геометрии. Сканирование Грэма - один из более простых алгоритмов выпуклой оболочки, но, конечно, не единственный. Алгоритм упаковки подарков, также называемый маршем Джарвиса, является самым простым из известных мне. Репозиторий алгоритма Stony Brook имеет несколько реализаций алгоритмов выпуклой оболочки в C и C++. Геометрия в действии показывает в основном применение выпуклых оболочек. Вот коллекция низкоразмерных и произвольно-размерных программ вычисления выпуклой оболочки.