I posted the below on StackOverflow but was directed here as this may be more mathematical problem but I was looking to implement an algorithm….
I have a discrete set of points.
From this set of point I need to find the 4 points that make up a Quadrilateral with the largest area.
To begin I have already used a Gift Wrapping algorithm to establish the points that make up the convex hull as the 4 points of the Quad will be on the hull.
I am now looking at what would be the best way to establish if the convex hull consists of more than 4 points how to narrow this down to only 4 points that make up that Quad.
I can only think of a brute force method of checking the area or perimeter of each combination of 4 points to then pick up the set with the largest but as the number of points on the convex hull is not predetermined I want to hopefully find a more efficient method.
I don't mind using brute force but was hoping someone could think up something a little more elegant to implement.
Found this entry:
algorithm-to-find-all-convex-quadrilaterals-from-the-given-list-of-2d-points
to produce list of all quadrilaterals that I can use to test the area.
Best Answer
Suppose you have $n$ points on the convex hull. Suppose there was a point $P_0$ which you knew to be part of the largest quad. Moving along the hull to other points will mean cutting off parts of the convex hull. A step to the next hull vertex cuts away nothing, skipping one vertex and using the one after taht will cut away a triangle, and so on. You can conceive this cut-away area as a kind of cost. So your task is one of finding a path consisting of four steps and going from $P_0$ to $P_n$ (which is identical to $P_0$ in its position). You could use dynamic programming for this. With a bit of tweaking, it should be possible to not rely on the starting point, but compute minimal cost cycles of length 4 for any pair. In general I'd worry about going around the hull more than once, but since that would lead to a smaller area, I doubt it's going to cause trouble in your case.