public class LargestEmptyCircle extends Object
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.
MaximumInscribedCircle
,
InteriorPoint
,
Centroid
Constructor and Description |
---|
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.
|
Modifier and Type | Method and Description |
---|---|
Point |
getCenter()
Gets the center point of the Largest Empty Circle
(up to the tolerance distance).
|
static Point |
getCenter(Geometry obstacles,
double tolerance)
Computes the center point of the Largest Empty Circle
interior-disjoint to a set of obstacles,
with accuracy to a given tolerance distance.
|
static Point |
getCenter(Geometry obstacles,
Geometry boundary,
double tolerance)
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.
|
LineString |
getRadiusLine()
Gets a line representing a radius of the Largest Empty Circle.
|
static LineString |
getRadiusLine(Geometry obstacles,
double tolerance)
Computes a radius line of the Largest Empty Circle
interior-disjoint to a set of obstacles,
with accuracy to a given tolerance distance.
|
static LineString |
getRadiusLine(Geometry obstacles,
Geometry boundary,
double tolerance)
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.
|
Point |
getRadiusPoint()
Gets a point defining the radius of the Largest Empty Circle.
|
public LargestEmptyCircle(Geometry obstacles, Geometry boundary, double tolerance)
obstacles
- a non-empty geometry representing the obstaclesboundary
- a polygonal geometry (may be null or empty)tolerance
- a distance tolerance for computing the circle center point (a positive value)public static Point getCenter(Geometry obstacles, double tolerance)
obstacles
- a geometry representing the obstaclestolerance
- the distance tolerance for computing the center pointpublic static Point getCenter(Geometry obstacles, Geometry boundary, double tolerance)
obstacles
- a geometry representing the obstaclesboundary
- a polygonal geometry to contain the LEC centertolerance
- the distance tolerance for computing the center pointpublic static LineString getRadiusLine(Geometry obstacles, double tolerance)
obstacles
- a geometry representing the obstaclestolerance
- the distance tolerance for computing the center pointpublic static LineString getRadiusLine(Geometry obstacles, Geometry boundary, double tolerance)
obstacles
- a geometry representing the obstaclesboundary
- a polygonal geometry to contain the LEC centertolerance
- the distance tolerance for computing the center pointpublic Point getCenter()
public Point getRadiusPoint()
public LineString getRadiusLine()
Copyright © 2024. All rights reserved.