Minimum bounding rectangle

Find the minimum-area-rectangle for a given set of points.

mbr(p)

MBR(p)

Arguments

p	input points (matrix of 2 columns)

Value

matrix of rectangle coordinates (5 points)

Details

Input is an array of point coordinates. Output (the value of mbr) is an array of the vertices of the minimum bounding rectangle (with the first one repeated to close it). Note the complete absence of any trigonometric calculations.

Timing is limited by the speed of the convex hull algorithm, because the number of vertices in the hull is almost always much less than the total. Most convex hull algorithms are asymptotically O(n*log(n)) for n points: you can compute almost as fast as you can read the coordinates.

MBR() is an alias of mbr().

For an sf wrapper see https://github.com/mdsumner/mbr/issues/1

References

https://gis.stackexchange.com/questions/22895/finding-minimum-area-rectangle-for-given-points/22934?stw=2#22934

Author

Bill Huber

Examples

xy <- quakes[, 1:2]
plot(mb0 <- mbr(xy)); lines(mb0)
points(xy)