Add ST_MinimumRectangle

[mwtoews]

Other GIS systems have a ST_MinimumRectangle function, for example ​H2GIS. A similar function for PostGIS would be desirable.

See ​https://trac.osgeo.org/geos/ticket/729 to port the getMinimumRectangle() JTS method to GEOS.

[nw]

I think the following works. I think but haven't proved that a side of a minimum rectangle must contain one of the sides of the convex hull of the point geometries. So this algorithm iterates through those sides and rotates the hull to be parallel to the y axis, calculates a bounding box, and counter rotates it. This gives a number of candidate rectangles, from which I choose the smallest, then the "first" based on the sides counting out from the first point in the case of ties.

This is just to make the algorithm stable. There isn't in general a unique minimum rectangle (think of a hexagon). There could be other choice mechanisms, since the rectangle chosen (potentially) depends on the ordering of the points. The rectangle could alternatively be chosen based on the angle of the major side of the rectangle to the X axis, which I think is then independent of the point ordering.

This also doesn't handle degenerate rectangles. If the approach seem sound, once a rectangle choice method is chosen, I will implement that and take care of the degenerate cases.

create or replace function ST_MinimumRectangle(g geometry) returns geometry
language 'plpgsql' as $$
declare
        hull geometry;
begin
        hull = ST_ExteriorRing(ST_ConvexHull(g));
        -- one side must lie along the rectangle.
        -- so, for each side, rotate, bbox, counter-rotate bbox
        with sides as (
                select ST_PointN(hull, n) as a, ST_PointN(hull, n+1) as b,
                        n as side
                        from generate_series(1,ST_NPoints(hull)-1) n
                ),
        angles as (
                select side, a, b, st_azimuth(a, b) as angle from sides
        ),
        boxes as (
                select ST_Rotate(ST_Envelope(ST_Rotate(hull, -angle)),angle) as rect, side, angle from angles
        )
        select rect into hull from boxes order by ST_Area(rect), side limit 1
        ;
        return hull;
end;
$$ immutable strict;

[dbaston]

Any updates on this? MinimumRectangle is now available in GEOS and could be called directly.

[robe]

Milestone renamed

[komzpa]

In trunk since r16369