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:
It looks to me promising, however the following problems exist:
أكثر...
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)
Fit a simple fitted rectangle i.e., parallel to the axes X and Y
- you may use minmax function for X and Y of the given points (e.g., polygon's vertices)
[*]Rotate the polygon about the centroid by e.g., 1 degree
[*]Repeat fromuntil a full rotation done
[*]Report the angle of the minimum area as the result
- choose of a good resolution for the angle change could be challenging,
- the computation cost is high,
- the solution is not analytical but experimental.
أكثر...