Minimum area quadrilateral algorithm
algorithm, geometry, graphics, language-agnostic, math
Solution
The Monte Carlo approach
Thanks for the clarifying comments on the problem. I've taken away that what's required is not a mathematically correct result but a "fit" that's better than any comparable fits for other shapes.
Rather than pouring a lot of algorithmic brain power at the problem, I'd let the computer worry about it. Generate groups of 4 random points; check that the quad formed by convexly joining those 4 points does not intersect the polygon, and compute the quad's area. Repeat 1 million times, retrieve the quad with the smallest area.
You can apply some constraints to make your points not completely random; this can dramatically improve convergence.
Monte Carlo, improved
I've been convinced that throwing 4 points randomly on the plane is a highly inefficient start even for a brute-force solution. Thus, the following refinement:
- For each trial, randomly select p distinct vertices and q distinct sides of the polygon such that p + q = 4.
- For each of the q sides, construct a line passing through that side's endpoints.
- For each of the p vertices, construct a line passing through that vertex and with a randomly assigned slope.
- Verify that the 4 lines indeed form a quadrilateral, and that this quadrilateral contains (and does not intersect!) the polygon. If these tests fail, don't pursue this iteration any further.
- If this quadrilateral's area is the minimum of all areas seen so far, remember the area and the coordinates of the quadrilateral's vertices.
- Repeat an arbitrary number of times, and return the "best" quadrilateral found.
As opposed to always requiring 8 random numbers (x and y coordinates for each of 4 points), this solution requires only (4 + p) random numbers. Also, the lines produced are not blindly floundering in the plane but are each touching the polygon. This ensures that the quadrilaterals are from the outset at least very close to the polygon.
Problem
There are a few algorithms around for finding the minimal bounding rectangle containing a given (convex) polygon. Does anybody know about an algorithm for finding the minimal-area bounding quadrilateral (any quadrilateral, not just rectangles)? I've searched the internet for several hours now, but while I found a few theoretical papers on the matter, I did not find a single implementation... EDIT: People at Mathoverflow pointed me to an article with a mathematical solution (my post there), but for which I did not find an actual implementation. I decided to go with the Monte Carlo Method from Carl, but will dive into the paper and report here, when I have the time... Thanks all!