5
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.