LargestEmptyCircle class

Constructs the Largest Empty Circle for a set of obstacle geometries, up to a given accuracy distance tolerance. The obstacles may be any combination of point, linear and polygonal geometries.

The Largest Empty Circle (LEC) is the largest circle whose interior does not intersect with any obstacle and whose center lies within a polygonal boundary. The circle center is the point in the interior of the boundary which has the farthest distance from the obstacles (up to the accuracy of the distance tolerance). The circle itself is determined by the center point and a point lying on an obstacle determining the circle radius.

The polygonal boundary may be supplied explicitly. If it is not specified the convex hull of the obstacles is used as the boundary.

To compute an LEC which lies wholly within a polygonal boundary, include the boundary of the polygon(s) as a linear obstacle.

The implementation uses a successive-approximation technique over a grid of square cells covering the obstacles and boundary. The grid is refined using a branch-and-bound algorithm. Point containment and distance are computed in a performant way by using spatial indexes.

@author Martin Davis

@see MaximumInscribedCircle @see InteriorPoint @see Centroid

Constructors

LargestEmptyCircle(Geometry obstacles, Geometry boundary, double tolerance)

Creates a new instance of a Largest Empty Circle construction, interior-disjoint to a set of obstacle geometries and having its center within a polygonal boundary. The obstacles may be any collection of points, lines and polygons. If the boundary is null or empty the convex hull of the obstacles is used as the boundary.

Properties

boundary ↔ Geometry

getter/setter pair

boundaryDistance ↔ IndexedFacetDistance

getter/setter pair

boundaryPtLocater ↔ IndexedPointInAreaLocator

getter/setter pair

bounds ↔ Geometry

getter/setter pair

centerCell ↔ CellLEC

getter/setter pair

centerPoint ↔ Point

getter/setter pair

centerPt ↔ Coordinate

getter/setter pair

factory ↔ GeometryFactory

getter/setter pair

farthestCell ↔ CellLEC

getter/setter pair

gridEnv ↔ Envelope

getter/setter pair

hashCode → int

The hash code for this object.

no setter, inherited

obstacleDistance ↔ IndexedDistanceToPoint

getter/setter pair

obstacles ↔ Geometry

getter/setter pair

radiusPoint ↔ Point

getter/setter pair

radiusPt ↔ Coordinate

getter/setter pair

runtimeType → Type

A representation of the runtime type of the object.

no setter, inherited

tolerance ↔ double

getter/setter pair

Methods

compute() → void

createCell(double x, double y, double h) → CellLEC

createCentroidCell(Geometry geom) → CellLEC

createInitialGrid(Envelope env, PriorityQueue cellQueue) → void

Initializes the queue with a cell covering the extent of the area.

distanceToConstraintsPoint(Point p) → double

Computes the signed distance from a point to the constraints (obstacles and boundary). Points outside the boundary polygon are assigned a negative distance. Their containing cells will be last in the priority queue (but will still end up being tested since they may be refined).

distanceToConstraintsXY(double x, double y) → double

getCenterPoint() → Point

Gets the center point of the Largest Empty Circle (up to the tolerance distance).

getRadiusLineString() → LineString

Gets a line representing a radius of the Largest Empty Circle.

getRadiusPoint() → Point

Gets a point defining the radius of the Largest Empty Circle. This is a point on the obstacles which is nearest to the computed center of the Largest Empty Circle. The line segment from the center to this point is a radius of the constructed circle, and this point lies on the boundary of the circle.

initBoundary() → void

mayContainCircleCenter(CellLEC cell) → bool

Tests whether a cell may contain the circle center, and thus should be refined (split into subcells to be investigated further.)

noSuchMethod(Invocation invocation) → dynamic

Invoked when a nonexistent method or property is accessed.

inherited

toString() → String

A string representation of this object.

inherited

Operators

operator ==(Object other) → bool

The equality operator.

inherited

Static Methods

getCenter(Geometry obstacles, double tolerance) → Point

Computes the center point of the Largest Empty Circle interior-disjoint to a set of obstacles, with accuracy to a given tolerance distance. The obstacles may be any collection of points, lines and polygons. The center of the LEC lies within the convex hull of the obstacles.

getCenterBoundary(Geometry obstacles, Geometry? boundary, double tolerance) → Point

Computes the center point of the Largest Empty Circle interior-disjoint to a set of obstacles and within a polygonal boundary, with accuracy to a given tolerance distance. The obstacles may be any collection of points, lines and polygons. The center of the LEC lies within the given boundary.

getRadiusLine(Geometry obstacles, double tolerance) → LineString

Computes a radius line of the Largest Empty Circle interior-disjoint to a set of obstacles, with accuracy to a given tolerance distance. The obstacles may be any collection of points, lines and polygons. The center of the LEC lies within the convex hull of the obstacles.

getRadiusLineBoundary(Geometry obstacles, Geometry? boundary, double tolerance) → LineString

Computes a radius line of the Largest Empty Circle interior-disjoint to a set of obstacles and within a polygonal boundary, with accuracy to a given tolerance distance. The obstacles may be any collection of points, lines and polygons. The center of the LEC lies within the given boundary.