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

Question

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

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

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

Любое предложение?

Answer 1

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

Answer 2

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

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

Answer 3

The Convex Hull является одной из наиболее изученных проблем вычислительной геометрии. Graham Scan является одним из простых convex hull algorithms, но, конечно, не единственным. The Gift-wrapping Algorithm, также называемый Марсом Джарвиса, является самым простым, о котором я знаю. The Stony Brook algorithm repository имеет несколько реализаций выпуклых алгоритмов корпуса в C и C++. Geometry in Action показывает в основном применения выпуклых оболочек. Вот коллекция из low-dimensional и arbitrary-dimensional программ расчета выпуклых корпусов.