geos::algorithm::construct::MaximumInscribedCircle Class Reference

`#include <MaximumInscribedCircle.h>`

## Public Member Functions

| MaximumInscribedCircle (const geom::Geometry *polygonal, double tolerance)
std::unique_ptr< geom::Point > | getCenter ()
std::unique_ptr< geom::Point > | getRadiusPoint ()
std::unique_ptr< geom::LineString > | getRadiusLine ()
bool | isRadiusWithin (double maxRadius)

## Static Public Member Functions

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

- Support a polygonal constraint on placement of center point, for example to produce circle-packing constructions, or support multiple labels.

Author
  Martin Davis

## Member Function Documentation

## computeMaximumIterations()

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

  geom | the input geometry
  toleranceDist | the 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]

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

  polygonal | a polygonal geometry
  tolerance | the 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]

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

  polygonal | a polygonal geometry
  tolerance | the 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]

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

  polygonal | a polygonal geometry
  maxRadius | the 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

  maxRadius | the (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:

- MaximumInscribedCircle.h