Недавно пришла в голову задача, но никак не могу придумать решения.
Постановка задачи: Дано множество из N точек(декартовая система). Нужно построить многоугольник минимальной площади.Многоугольник должен быть без самопересечений и содержать все точки как вершины многоугольника. Нужен самый оптимальный алгоритм :)
Будет очень круто, если Вы прикрепите код. Заранее спасибо!
Приветствуются всевозможные решения!
Это задача на построение выпуклой оболочки (Даны N точек на плоскости. Построить их выпуклую оболочку, т.е. наименьший выпуклый многоугольник, содержащий все эти точки.).
Построение выпуклой оболочки алгоритмом Грэхэма-Эндрю за O(N log N)
Выпуклая оболочка просто содержит точки в себе, но не гарантируется, что они вершины, так что она здесь не подходит.
Нет, надо же все точки использовать. В оболочке далеко не все.
Тогда извиняюсь, не прав. Но я не представляю как решить эту задачу даже для самых простых примеров, если мы имеем > 2 точек на одной прямой.
Казалось бы, задача совсем другая "Многоугольник должен быть без самопересечений и содержать все точки как вершины многоугольника." И у меня всегда было ощущение, что выпуклая оболочка совсем не обязана содержать все точки, плюс, возможность использовать все точки иногда помогает уменьшить ответ. Например, для множества {( - 1, - 1), (1, - 1), ( - 1, 1), (1, 1), (0, 0)}. Площадь выпуклой оболочки — 4, а ответ, очевидно, равен 3.
Только не минусуйте сразу — просто мысль — ситуация напоминает k-opt эвристику для TSP. Она поможет избавиться от самопересечений. С другой стороны это просто эвристика и в оригинале она нацелена на уменьшение длины пути, а не уменьшение площади им описываемой — это скорее противоположное требование.
Задача известна как Minimum Area Polygon и является NP-Complete (см. http://e-archive.informatik.uni-koeln.de/256/ ).
The problem statement is not very clear to me. Is the following what you want?
You are given N points on the Euclidean plane. Among the simple N-gons whose vertices are the given points, find the one with the minimum area.
If this is the problem you are asking about, I have a bad news: it is known to be NP-hard. For a proof, see:
Sándor P. Fekete. On simple polygonalizations with optimal area. Discrete and Computational Geometry, 23(1):73–110, Jan. 2000. DOI: 10.1007/PL00009492. Author copy: http://www.ibr.cs.tu-bs.de/users/fekete/hp/publications/papers/f-spoa-00.pdf.