Class MaximumInscribedCircle

java.lang.Object
org.locationtech.jts.algorithm.construct.MaximumInscribedCircle
public class MaximumInscribedCircle extends Object
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
Author:
Martin Davis
See Also:

  • Constructor Details

    • MaximumInscribedCircle

      public MaximumInscribedCircle(Geometry polygonal, double tolerance)
      Creates a new instance of a Maximum Inscribed Circle computation.
      Parameters:
      polygonal - an areal geometry
      tolerance - the distance tolerance for computing the centre point (must be positive)
      Throws:
      IllegalArgumentException - if the tolerance is non-positive, or the input geometry is non-polygonal or empty.

  • Method Details

    • getCenter

      public static Point getCenter(Geometry polygonal, double tolerance)
      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

      public static LineString getRadiusLine(Geometry polygonal, double tolerance)
      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

    • getCenter

      public Point getCenter()
      Gets the center point of the maximum inscribed circle (up to the tolerance distance).
      Returns:
      the center point of the maximum inscribed circle

    • getRadiusPoint

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

    • getRadiusLine

      public LineString getRadiusLine()
      Gets a line representing a radius of the Largest Empty Circle.
      Returns:
      a line from the center of the circle to a point on the edge