ST_MinimumBoundingCircle doesn't always contain all points

[captainigloo]

For example when given the polygon:

POLYGON((26426 65078,26531 65242,26075 65136,26096 65427,26426 65078))

ST_MinimumBoundingCircle() returns a circle with centre POINT(26290 65280) and radius 243.56. This is incorrect, one of the points (POINT(26075 65136)) does not fall within this circle. This can be demonstrated by selecting the radius of the MBC:

# select st_xmax(ST_MinimumBoundingCircle(st_geomfromtext('POLYGON((26426 65078,26531 65242,26075 65136,26096 65427,26426 65078))'))) - st_x(st_centroid(ST_MinimumBoundingCircle(st_geomfromtext('POLYGON((26426 65078,26531 65242,26075 65136,26096 65427,26426 65078))'))));
     ?column?     
------------------
 243.560244342832
(1 row)

Then selecting the distance from POINT(26075 65136) to the centre of the circle:

# select st_distance(st_geomfromtext('POINT(26075 65136)'), st_centroid(ST_MinimumBoundingCircle(st_geomfromtext('POLYGON((26426 65078,26531 65242,26075 65136,26096 65427,26426 65078))'))));
   st_distance   
-----------------
 259.37884274511
(1 row)

It looks like the function makes an incorrect assumption that the two points in the input geometry that are furthest away from each other fall on the minimum bounding circle, but this isn't always the case.

[mwtoews]

Looking at the PL/pgSQL source, it does not correctly determine the diameter from a brute force distance approach (​in the top half), and in general the algorithm is different than in JTS' ​MinimumBoundingCircle class, which returns a polygon that mostly contains all the input points. (Note that a buffered point does not always contain the boundary of a circle, so the topic of this bug report will generally be true.)

Further note the reported ticket has an invalid geometry, but a similar valid geometry has the same result:

• blue POLYGON ((26426 65078, 26531 65242, 26096 65427, 26075 65136, 26426 65078))
• red SELECT ST_MinimumBoundingCircle(blue, 8);
• yellow is JTS' MinimumBoundingCircle result with blue.

See also a GEOS enhancement to port the ​functionality from JTS: ​https://trac.osgeo.org/geos/ticket/735

[dbaston]

Good info, Mike. As an alternative to the GEOS route, I've been looking at ​Welzl's algorithm, which seems like it hits a good balance of speed/complexity. I'd take a crack at adding this to liblwgeom if there is interest/support. (Alternatively, this algorithm is available through CGAL, I think)

[robe]

​https://github.com/postgis/postgis/pull/67

[dbaston]

Committed new code to resolve this issue in trunk at r14448 and r14449.