Я второе предложение Groovingandi попробовать все полигоны; вам просто нужно проверить правильность многоугольника (без самопересечений и т. д.).
Теперь, если вы хотите работать с большим количеством точек ... Как указал MatlabDoug, выпуклая оболочка - хорошее место для старта. Обратите внимание, что выпуклая оболочка дает многоугольник, площадь которого максимально возможна. Проблема, конечно, в том, что внутри корпуса могут быть точки, которые не являются частью многоугольника. Я предлагаю следующий жадный алгоритм, но я не уверен, гарантирует ли он полигон максимальной площади.
Основная идея состоит в том, чтобы начать с выпуклой оболочки в качестве конечного многоугольника-кандидата и вырезать треугольники, соответствующие неиспользованным точкам, до тех пор, пока все точки не будут принадлежать конечному многоугольнику. На каждом этапе удаляется наименьший возможный треугольник.
Given: Points P = {p1, ... pN}, convex hull H = {h1, ..., hM}
where each h is a point that lies on the convex hull.
H is a subset of P, and it is also ordered such that adjacent
points in the list of H are edges of the convex hull, and the
first and last points form an edge.
Let Q = H
while(Q.size < P.size)
% For each point, compute minimum area triangle
T = empty heap of triangles with value of their area
For each P not in Q
For each edge E of Q
If triangle formed by P and E does not contain any other point
Add triangle(P,E) with value area(triangle(P,E))
% Modify the current polygon Q to carve out the triangle
Let t=(P,E) be the element of T with minimum area
Find the ordered pair of points that form the edge E within Q
(denote them Pa and Pb)
Replace the pair (Pa,Pb) with (Pa,E,Pb)
Теперь на практике вам не нужна куча для T, просто добавьте данные в четыре списка: один для P, один для Pa, один для Pb и один для области. Чтобы проверить, лежит ли точка внутри треугольника, вам нужно только проверить каждую точку на соответствие линиям, образующим стороны треугольника, и вам нужно только проверить точки, которых еще нет в Q. Наконец, чтобы вычислить площадь конечного многоугольника, вы можете триангулировать его (как с помощью функции delaunay, и суммировать площади каждого треугольника в триангуляции), или вы можете найти площадь выпуклой оболочки и вычесть области треугольников по мере их вырезания .
Опять же, я не знаю, гарантированно ли этот жадный алгоритм для нахождения многоугольника максимальной площади, но я думаю, что он должен работать большую часть времени, и, тем не менее, интересен.