The following is another problem that I am working on it these days. As you see in the figure, (BTW, I tried to make it self-presenter) the question is:
How to find the minimum-area-rectangle (MAR) fitted on the given points?
and a supporting question is:
Is there any analytical solution for the problem?
(A development of the question will be to fit a box (3D) to a cluster of points in a 3D point cloud.)
As a first stage I propose to find the convex-hull for the points which reforms the problem (by removing those points are not involved in the solution) to: fitting a MAR to a polygon. The required method will provide X (center of rectangle), D (two dimensions) and A (angle).
My proposal for solution:
- Find the centroid of the polygon (see this post)
- [S] Fit a simple fitted rectangle i.e., parallel to the axes X and Y
- you may use
minmaxfunction for X and Y of the given points (e.g., polygon's vertices)
- you may use
- Store the area of the fitted rectangle
- Rotate the polygon about the centroid by e.g., 1 degree
- Repeat from [S] until a full rotation done
- Report the angle of the minimum area as the result
It looks to me promising, however the following problems exist:
- choose of a good resolution for the angle change could be challenging,
- the computation cost is high,
- the solution is not analytical but experimental.