GEOS  3.11.0beta3
Public Member Functions | Static Public Member Functions | List of all members
geos::algorithm::construct::LargestEmptyCircle Class Reference

#include <LargestEmptyCircle.h>

Public Member Functions

 LargestEmptyCircle (const geom::Geometry *p_obstacles, double p_tolerance)
 
 LargestEmptyCircle (const geom::Geometry *p_obstacles, const geom::Geometry *p_boundary, double p_tolerance)
 
std::unique_ptr< geom::PointgetCenter ()
 
std::unique_ptr< geom::PointgetRadiusPoint ()
 
std::unique_ptr< geom::LineStringgetRadiusLine ()
 

Static Public Member Functions

static std::unique_ptr< geom::PointgetCenter (const geom::Geometry *p_obstacles, double p_tolerance)
 
static std::unique_ptr< geom::LineStringgetRadiusLine (const geom::Geometry *p_obstacles, double p_tolerance)
 

Detailed Description

Constructs the Largest Empty Circle for a set of obstacle geometries, up to a specified tolerance. The obstacles are point and line geometries.

The Largest Empty Circle is the largest circle which has its center in the convex hull of the obstacles (the boundary), and whose interior does not intersect with any obstacle. The circle center is the point in the interior of the boundary which has the farthest distance from the obstacles (up to tolerance). The circle is determined by the center point and a point lying on an obstacle indicating the circle radius.

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

Constructor & Destructor Documentation

◆ LargestEmptyCircle()

geos::algorithm::construct::LargestEmptyCircle::LargestEmptyCircle ( const geom::Geometry p_obstacles,
double  p_tolerance 
)

Creates a new instance of a Largest Empty Circle construction.

Parameters
p_obstaclesa geometry representing the obstacles (points and lines)
p_tolerancethe distance tolerance for computing the circle center point

Member Function Documentation

◆ getCenter()

static std::unique_ptr<geom::Point> geos::algorithm::construct::LargestEmptyCircle::getCenter ( const geom::Geometry p_obstacles,
double  p_tolerance 
)
static

Computes the center point of the Largest Empty Circle within a set of obstacles, up to a given tolerance distance.

Parameters
p_obstaclesa geometry representing the obstacles (points and lines)
p_tolerancethe distance tolerance for computing the center point
Returns
the center point of the Largest Empty Circle

◆ getRadiusLine()

static std::unique_ptr<geom::LineString> geos::algorithm::construct::LargestEmptyCircle::getRadiusLine ( const geom::Geometry p_obstacles,
double  p_tolerance 
)
static

Computes a radius line of the Largest Empty Circle within a set of obstacles, up to a given distance tolerance.

Parameters
p_obstaclesa geometry representing the obstacles (points and lines)
p_tolerancethe distance tolerance for computing the center point
Returns
a line from the center of the circle to a point on the edge

The documentation for this class was generated from the following file: