GEOS 3.14.0dev
Public Member Functions | Static Public Member Functions | List of all members
geos::algorithm::construct::MaximumInscribedCircle Class Reference

#include <MaximumInscribedCircle.h>

Public Member Functions

 MaximumInscribedCircle (const geom::Geometry *polygonal, double tolerance)
 
std::unique_ptr< geom::PointgetCenter ()
 
std::unique_ptr< geom::PointgetRadiusPoint ()
 
std::unique_ptr< geom::LineStringgetRadiusLine ()
 
bool isRadiusWithin (double maxRadius)
 

Static Public Member Functions

static std::unique_ptr< geom::PointgetCenter (const geom::Geometry *polygonal, double tolerance)
 
static std::unique_ptr< geom::LineStringgetRadiusLine (const geom::Geometry *polygonal, double tolerance)
 
static bool isRadiusWithin (const geom::Geometry *polygonal, double maxRadius)
 
static std::size_t computeMaximumIterations (const geom::Geometry *geom, double toleranceDist)
 

Detailed Description

Constructs the Maximum Inscribed Circle for a polygonal Geometry, up to a specified tolerance. The Maximum Inscribed Circle is determined by a point in the interior of the area which has the farthest distance from the area boundary, along with a boundary point at that distance.

In the context of geography the center of the Maximum Inscribed Circle is known as the Pole of Inaccessibility. A cartographic use case is to determine a suitable point to place a map label within a polygon.

The radius length of the Maximum Inscribed Circle is a measure of how "narrow" a polygon is. It is the distance at which the negative buffer becomes empty.

The class supports testing whether a polygon is "narrower" than a specified distance via isRadiusWithin(Geometry, double) or isRadiusWithin(double). Testing for the maximum radius is generally much faster than computing the actual radius value, since short-circuiting is used to limit the approximation iterations.

The class supports polygons with holes and multipolygons.

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

Future Enhancements

Author
Martin Davis

Member Function Documentation

◆ computeMaximumIterations()

static std::size_t geos::algorithm::construct::MaximumInscribedCircle::computeMaximumIterations ( const geom::Geometry geom,
double  toleranceDist 
)
static

Computes the maximum number of iterations allowed. Uses a heuristic based on the area of the input geometry and the tolerance distance. The number of tolerance-sized cells that cover the input geometry area is computed, times a safety factor. This prevents massive numbers of iterations and created cells for casees where the input geometry has extremely small area (e.g. is very thin).

Parameters
geomthe input geometry
toleranceDistthe tolerance distance
Returns
the maximum number of iterations allowed

◆ getCenter() [1/2]

std::unique_ptr< geom::Point > geos::algorithm::construct::MaximumInscribedCircle::getCenter ( )

Gets the center point of the maximum inscribed circle (up to the tolerance distance).

Returns
the center point of the maximum inscribed circle

◆ getCenter() [2/2]

static std::unique_ptr< geom::Point > geos::algorithm::construct::MaximumInscribedCircle::getCenter ( const geom::Geometry polygonal,
double  tolerance 
)
static

Computes the center point of the Maximum Inscribed Circle of a polygonal geometry, up to a given tolerance distance.

Parameters
polygonala polygonal geometry
tolerancethe distance tolerance for computing the center point
Returns
the center point of the maximum inscribed circle

◆ getRadiusLine() [1/2]

std::unique_ptr< geom::LineString > geos::algorithm::construct::MaximumInscribedCircle::getRadiusLine ( )

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

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

◆ getRadiusLine() [2/2]

static std::unique_ptr< geom::LineString > geos::algorithm::construct::MaximumInscribedCircle::getRadiusLine ( const geom::Geometry polygonal,
double  tolerance 
)
static

Computes a radius line of the Maximum Inscribed Circle of a polygonal geometry, up to a given tolerance distance.

Parameters
polygonala polygonal geometry
tolerancethe distance tolerance for computing the center point
Returns
a line from the center to a point on the circle

◆ getRadiusPoint()

std::unique_ptr< geom::Point > geos::algorithm::construct::MaximumInscribedCircle::getRadiusPoint ( )

Gets a point defining the radius of the Maximum Inscribed Circle. This is a point on the boundary which is nearest to the computed center of the Maximum Inscribed 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.

Returns
a point defining the radius of the Maximum Inscribed Circle

◆ isRadiusWithin() [1/2]

static bool geos::algorithm::construct::MaximumInscribedCircle::isRadiusWithin ( const geom::Geometry polygonal,
double  maxRadius 
)
static

Tests if the radius of the maximum inscribed circle is no longer than the specified distance. This method determines the distance tolerance automatically as a fraction of the maxRadius value.

Parameters
polygonala polygonal geometry
maxRadiusthe radius value to test
Returns
true if the max in-circle radius is no longer than the max radius

◆ isRadiusWithin() [2/2]

bool geos::algorithm::construct::MaximumInscribedCircle::isRadiusWithin ( double  maxRadius)

Tests if the radius of the maximum inscribed circle is no longer than the specified distance. This method determines the distance tolerance automatically as a fraction of the maxRadius value. After this method is called the center and radius points provide locations demonstrating where the radius exceeds the specified maximum.

Parameters
maxRadiusthe (non-negative) radius value to test
Returns
true if the max in-circle radius is no longer than the max radius

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