Recently, while extracting point cloud boundaries, I encountered a problem: given a set of discrete points, how do we find the rectangle of minimum area that encloses them? I browsed through mature implementations available online and summarized the methods. Those interested can take it as a reference.

What is the minimum area bounding rectangle

The minimum area bounding rectangle, often called the Minimum Area Rectangle or Minimum Bounding Rectangle, abbreviated as MAR or MBR. Unlike the common axis-aligned minimum bounding rectangle, it allows the rectangle to be rotated at any angle while requiring the smallest possible area. As shown below:

Algorithm principle

The most intuitive approach is to first compute the convex hull, then rotate the polygon around its centroid by 1 degree each step, calculate the axis-aligned bounding rectangle area at each step, and after a full 360° rotation take the minimum value. This method works, but it is computationally expensive, and the final accuracy depends on the step size.

In the field of polygon generalization, this problem is known as the "smallest surrounding rectangle". A key property is: the orientation of the minimum area bounding rectangle must align with the direction of one of the convex hull edges. Therefore, instead of brute-force searching with a fixed angular step, we only need to iterate over each edge of the convex hull, treat that edge as one of the rectangle's directions, compute the bounding rectangle area in that orientation, and take the minimum.

The specific steps are as follows.

  1. Compute the convex hull of the point set.
  2. Iterate over each edge of the convex hull, computing the edge's direction angle or unit direction vector.
  3. Using that edge direction as a reference, project all convex hull vertices onto two axes: "along the edge" and "perpendicular to the edge". Take the min and max on each axis to obtain the minimum area bounding rectangle for that orientation.
  4. Compare the results from all edges and keep the one with the smallest area.

The number of convex hull vertices is usually much smaller than the original point count, and the number of edges is O(h), where h is the number of hull vertices. The overall efficiency is much higher than the "rotate 1° each time" method. The 3D case follows a similar idea, but one must test the orientations of the hull faces, which is more complex than the 2D case.

Python implementation

Following this idea, I wrote a Python version using NumPy and SciPy. It returns the coordinates of the four corner points of the rectangle:

import numpy as np
from scipy.spatial import ConvexHull

def minimum_bounding_rectangle(points):
    """Compute the minimum area bounding rectangle for a set of points, returning 4x2 corner coordinates."""
    pts = np.asarray(points, dtype=float)
    hull = ConvexHull(pts)
    vertices = pts[hull.vertices]
    n = len(vertices)

    min_area = np.inf
    best_corners = None

    for i in range(n):
        p1 = vertices[i]
        p2 = vertices[(i + 1) % n]
        edge = p2 - p1
        length = np.linalg.norm(edge)
        if length == 0:
            continue

        v = edge / length
        w = np.array([-v[1], v[0]])

        proj_v = vertices @ v
        proj_w = vertices @ w
        min_v, max_v = proj_v.min(), proj_v.max()
        min_w, max_w = proj_w.min(), proj_w.max()
        area = (max_v - min_v) * (max_w - min_w)

        if area < min_area:
            min_area = area
            local = np.array([
                [max_v, min_w],
                [min_v, min_w],
                [min_v, max_w],
                [max_v, max_w],
            ])
            best_corners = local @ np.vstack([v, w])

    return best_corners

Note that if the x- and y-axis scales are not equal when plotting, the rectangle might look like a parallelogram on the screen – that is a display aspect ratio issue.

Other implementation approaches

If you prefer not to write the code yourself, there are some ready-made tools available, such as:

  1. OpenCV provides minAreaRect, which accepts a set of 2D points and returns a rotated rectangle.
  2. PostGIS, starting from version 2.5.0, offers ST_OrientedEnvelope, which internally calls GEOS GEOSMinimumRotatedRectangle; Shapely provides the corresponding oriented_envelope(), with the alias minimum_rotated_rectangle(). In GeoPandas you can also write geometry.minimum_rotated_rectangle.

Summary

Although I understood the principle and even built a basic version, I ended up using GeoPandas to implement the business functionality. Principles are principles, and implementation is implementation – after all, code written by a large open-source project is surely better than my own.

References

  1. Finding minimum-area-rectangle for given points?: https://gis.stackexchange.com/questions/22895/finding-minimum-area-rectangle-for-given-points
  2. Whitebox GAT: https://www.whiteboxgeo.com/
  3. OpenCV minAreaRect tutorial: https://docs.opencv.org/4.x/de/d62/tutorial_bounding_rotated_ellipses.html