Namespace NetTopologySuite.Algorithm.Construct

Provides classes that implement various kinds of geometric constructions.

Classes

LargestEmptyCircle

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.

Future Enhancements

• Support polygons as obstacles
• Support a client-defined boundary polygon

MaximumInscribedCircle

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 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