ST_LargestEmptyCircle — Computes the largest circle not overlapping a geometry.
(geometry, geometry, double precision) ST_LargestEmptyCircle(geometry geom, double precision tolerance=0.0, geometry boundary=POINT EMPTY);
Finds the largest circle which does not overlap a set of point and line obstacles. (Polygonal geometries may be included as obstacles, but only their boundary lines are used.) The center of the circle is constrained to lie inside a polygonal boundary, which by default is the convex hull of the input geometry. The circle center is the point in the interior of the boundary which has the farthest distance from the obstacles. The circle itself is provided by the center point and a nearest point lying on an obstacle determining the circle radius.
The circle center is determined to a given accuracy specified by a distance tolerance, using an iterative algorithm. If the accuracy distance is not specified a reasonable default is used.
Returns a record with fields:
center - center point of the circle
nearest - a point on the geometry nearest to the center
radius - radius of the circle
To find the largest empty circle in the interior of a polygon, see ST_MaximumInscribedCircle.
Availability: 3.4.0.
Requires GEOS >= 3.9.0.
Largest empty circle within a set of lines.
WITH obstacles(geom) AS (VALUES ('MULTILINESTRING (
(10 100,60 180,130 150,190 160),
(20 50,70 70,90 20,110 40),
(160 30,100 100,180 100))'::geometry)),
circle AS (
SELECT result.*
FROM obstacles
CROSS JOIN LATERAL ST_LargestEmptyCircle(obstacles.geom) AS result
)
SELECT round(radius::numeric, 6) AS radius,
ST_SnapToGrid(center, 1) AS center,
ST_SnapToGrid(nearest, 1) AS nearest,
ST_SnapToGrid(ST_MakeLine(center, nearest), 1) AS radius_line,
ST_SnapToGrid(ST_Buffer(center, radius), 1) AS circle
FROM circle;
-[ RECORD 1 ]----- radius | 39.260545 center | POINT(62 108) nearest | POINT(70 70) radius_line | LINESTRING(62 108,70 70) circle | POLYGON((101 108,100 101,98 93,94 87,89 81,83 76,77 72,69 70,62 69,54 70,47 72,40 76,34 81,29 87,25 93,23 101,22 108,23 116,25 123,29 130,34 136,40 141,47 145,54 147,62 148,69 147,77 145,83 141,89 136,94 130,98 123,100 116,101 108))
Largest empty circle within a set of points, constrained to lie in a polygon. The constraint polygon boundary is included both as an obstacle and as the constraint for the circle center.
WITH inputs(points, boundary) AS (VALUES (
'MULTIPOINT ((70 50),(60 130),(130 150),(80 90))'::geometry,
'POLYGON ((90 190,10 100,60 10,190 40,120 100,190 180,90 190))'::geometry
)),
circle AS (
SELECT result.*
FROM inputs
CROSS JOIN LATERAL ST_LargestEmptyCircle(
ST_Collect(points, boundary), 0, boundary
) AS result
)
SELECT round(radius::numeric, 6) AS radius,
ST_SnapToGrid(center, 1) AS center,
ST_SnapToGrid(nearest, 1) AS nearest,
ST_SnapToGrid(ST_MakeLine(center, nearest), 1) AS radius_line,
ST_SnapToGrid(ST_Buffer(center, radius), 1) AS circle
FROM circle;
-[ RECORD 1 ]----- radius | 19.903876 center | POINT(97 100) nearest | POINT(80 90) radius_line | LINESTRING(97 100,80 90) circle | POLYGON((117 100,117 96,116 92,114 89,111 86,108 83,105 82,101 80,97 80,93 80,90 82,86 83,83 86,81 89,79 92,78 96,77 100,78 104,79 108,81 111,83 114,86 116,90 118,93 119,97 120,101 119,105 118,108 116,111 114,114 111,116 108,117 104,117 100))