GEOS 3.14.0dev
|
#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) |
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
|
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).
geom | the input geometry |
toleranceDist | the tolerance distance |
std::unique_ptr< geom::Point > geos::algorithm::construct::MaximumInscribedCircle::getCenter | ( | ) |
Gets the center point of the maximum inscribed circle (up to the tolerance distance).
|
static |
Computes the center point of the Maximum Inscribed Circle of a polygonal geometry, up to a given tolerance distance.
polygonal | a polygonal geometry |
tolerance | the distance tolerance for computing the center point |
std::unique_ptr< geom::LineString > geos::algorithm::construct::MaximumInscribedCircle::getRadiusLine | ( | ) |
Gets a line representing a radius of the Largest Empty Circle.
|
static |
Computes a radius line of the Maximum Inscribed Circle of a polygonal geometry, up to a given tolerance distance.
polygonal | a polygonal geometry |
tolerance | the distance tolerance for computing the center point |
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.
|
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.
polygonal | a polygonal geometry |
maxRadius | the radius value to test |
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.
maxRadius | the (non-negative) radius value to test |