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 Summary

    Constructors
    Constructor
    Description
    MaximumInscribedCircle(Geometry polygonal, double tolerance)
    Creates a new instance of a Maximum Inscribed Circle computation.
  • Method Summary

    Modifier and Type
    Method
    Description
    Gets the center point of the maximum inscribed circle (up to the tolerance distance).
    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.
    Gets a line representing a radius of the Largest Empty Circle.
    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.
    Gets a point defining the radius of the Maximum Inscribed Circle.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
  • 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