Многоугольник, содержащий множество точек

Question

У меня есть набор S точек (2D: определяется с помощью x и y), и я хочу найти P, самый маленький (то есть: с наименьшим количеством точек) многоугольник, охватывающий все точки набора, P является упорядоченное подмножество S.

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

Спасибо за вашу помощь

Answer 1

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

Один из способов - найти крайнюю левую точку, а затем повторить поиск точки, где все остальные точки находятся справа от линии p (n-1) p (n).

Answer 2

Вот простое решение ...

Начните с любых трех точек, чтобы сформировать треугольник. Добавьте каждую дополнительную точку к многоугольнику с помощью следующей операции:

Разделите ребра на два непрерывных пути, где в одном пути линия каждого ребра отделяет точку, которая будет добавлена ​​от остальной части многоугольника (назовем это «разделяющим путем»), а в другом пути - линия каждого ребра имеет точку на той же стороне, что и многоугольник.

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

Если разделительный путь не имеет ребер, точка находится внутри многоугольника и должна игнорироваться, в противном случае удалите разделительный путь из многоугольника. Замените его двумя сегментами, соединяющими каждую конечную точку разделяющего пути с новой точкой.

Та-да! :)

Answer 3

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

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

Answer 4

Вот хороший ресурс по алгоритмам выпуклой оболочки: Выпуклая оболочка двумерного набора точек или многоугольника (автор Dan Sunday)