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::Point > | getCenter ()
std::unique_ptr< geom::Point > | getRadiusPoint ()
std::unique_ptr< geom::LineString > | getRadiusLine ()

## Static Public Member Functions

static std::unique_ptr< geom::Point > | getCenter (const geom::Geometry *p_obstacles, double p_tolerance)
static std::unique_ptr< geom::LineString > | getRadiusLine (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 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 an 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

## Constructor & Destructor Documentation

## LargestEmptyCircle() [1/2]

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

Creates a new instance of a Largest Empty Circle construction. The obstacles may be any collection of points, lines and polygons. The constructed circle center lies within the convex hull of the obstacles.

Parameters

  p_obstacles | a geometry representing the obstacles
  p_tolerance | the distance tolerance for computing the circle center point

Referenced by LargestEmptyCircle().

## LargestEmptyCircle() [2/2]

geos::algorithm::construct::LargestEmptyCircle::LargestEmptyCircle | ( | const geom::Geometry * | p_obstacles,
|  | const geom::Geometry * | p_boundary,
|  | double | p_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.

Parameters

  p_obstacles | a geometry representing the obstacles
  p_boundary | a polygonal geometry to contain the LEC center
  p_tolerance | the distance tolerance for computing the circle center point

References LargestEmptyCircle().

## Member Function Documentation

## getCenter()

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. The obstacles may be any collection of points, lines and polygons.

Parameters

  p_obstacles | a geometry representing the obstacles
  p_tolerance | the distance tolerance for computing the center point

Returns
  the center point of the Largest Empty Circle

Referenced by getRadiusLine().

## getRadiusLine()

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. The obstacles may be any collection of points, lines and polygons.

Parameters

  p_obstacles | a geometry representing the obstacles
  p_tolerance | the distance tolerance for computing the center point

Returns
  a line from the center of the circle to a point on the edge

References getCenter(), and getRadiusLine().

Referenced by getRadiusLine().

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

- LargestEmptyCircle.h