geometry - Finding minimum-area-rectangle for given points?

As you see in the figure, 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 Finding center of geometry of object?)


• [S] 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)
  
  
  
  


• 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.

---

Answer

Yes, there is an analytical solution for this problem. The algorithm you are looking for is known in polygon generalisation as "smallest surrounding rectangle".

The algorithm you describe is fine but in order to solve the problems you have listed, you can use the fact that the orientation of the MAR is the same as the one of one of the edges of the point cloud convex hull. So you just need to test the orientations of the convex hull edges. You should:

• Compute the convex hull of the cloud.


• For each edge of the convex hull:
  
  
  
  • compute the edge orientation (with arctan),
  
  
  • rotate the convex hull using this orientation in order to compute easily the bounding rectangle area with min/max of x/y of the rotated convex hull,
  
  
  • Store the orientation corresponding to the minimum area found,
  
  
  
  


• Return the rectangle corresponding to the minimum area found.

An example of implementation in java is available there.

In 3D, the same applies, except:

• The convex hull will be a volume,


• The orientations tested will be the orientations (in 3D) of the convex hull faces.

Good luck!