У меня есть множество S точек (2D: определяется x и y), и я хочу найти P, наименьшее (значение: с наименьшим числом точек) многоугольник, охватывающий все точки множества, P - упорядоченное подмножество S.
Существуют ли какие-либо известные алгоритмы для вычисления этого? (моя нехватка культуры в этой области поражает...)
Спасибо за помощь
Существует много алгоритмов для этой проблемы. Он называется " минимальный ограничивающий прямоугольник". Вы найдете решения, которые также ищут " выпуклый корпус", особенно здесь.
Один из способов - найти самую левую точку, а затем повторить для поиска точки, где все остальные точки находятся справа от строки p (n-1) p (n).
Вот простое решение...
Начните с любых трех точек, чтобы сформировать треугольник. Добавьте каждую дополнительную точку в многоугольник со следующей операцией:
Разделите ребра на два непрерывных пути, где по одному пути линия каждого ребра разделяет точку, которую нужно добавить из остальной части многоугольника (назовем это "разделительным путем" ), а на другом пути линия каждого ребра имеет точку на той же стороне, что и многоугольник.
(Примечание: до тех пор, пока ваша форма остается выпуклой, что должно быть, эти два пути будут непрерывными и образуют всю форму)
Если разделительный путь не имеет ребер, точка находится внутри многоугольника и должна игнорироваться, в противном случае удалить путь выделения из многоугольника. Замените его двумя сегментами, соединяющими каждую конечную точку разделительного пути с новой точкой.
Та-да!:)
Вероятно, вы хотите, чтобы вы имели наименьшую площадь, которая является выпуклой оболочкой.
Если вам действительно нужны наименьшие точки, вы можете просто создать треугольник с очень большими вершинами, чтобы все ваши точки были заключены.
Здесь хороший ресурс по алгоритмам выпуклых оболочек: Выпуклая оболочка двумерного точечного набора или многоугольника (Дэном Воскресенье)