Class LargestEmptyCircle


  • public class LargestEmptyCircle
    extends java.lang.Object
    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
    Author:
    Martin Davis
    • Constructor Summary

      Constructors 
      Constructor Description
      LargestEmptyCircle​(Geometry obstacles, double tolerance)
      Creates a new instance of a Largest Empty Circle construction.
    • Method Summary

      All Methods Static Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      Point getCenter()
      Gets the center point of the Largest Empty Circle (up to the tolerance distance).
      static Point getCenter​(Geometry obstacles, double tolerance)
      Computes the center point of the Largest Empty Circle within a set of obstacles, up to a given tolerance distance.
      LineString getRadiusLine()
      Gets a line representing a radius of the Largest Empty Circle.
      static LineString getRadiusLine​(Geometry obstacles, double tolerance)
      Computes a radius line of the Largest Empty Circle within a set of obstacles, up to a given distance tolerance.
      Point getRadiusPoint()
      Gets a point defining the radius of the Largest Empty Circle.
      • Methods inherited from class java.lang.Object

        equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
    • Constructor Detail

      • LargestEmptyCircle

        public LargestEmptyCircle​(Geometry obstacles,
                                  double tolerance)
        Creates a new instance of a Largest Empty Circle construction.
        Parameters:
        obstacles - a geometry representing the obstacles (points and lines)
        tolerance - the distance tolerance for computing the circle center point
    • Method Detail

      • getCenter

        public static Point getCenter​(Geometry obstacles,
                                      double tolerance)
        Computes the center point of the Largest Empty Circle within a set of obstacles, up to a given tolerance distance.
        Parameters:
        obstacles - a geometry representing the obstacles (points and lines)
        tolerance - the distance tolerance for computing the center point
        Returns:
        the center point of the Largest Empty Circle
      • getRadiusLine

        public static LineString getRadiusLine​(Geometry obstacles,
                                               double tolerance)
        Computes a radius line of the Largest Empty Circle within a set of obstacles, up to a given distance tolerance.
        Parameters:
        obstacles - a geometry representing the obstacles (points and lines)
        tolerance - the distance tolerance for computing the center point
        Returns:
        a line from the center of the circle to a point on the edge
      • getCenter

        public Point getCenter()
        Gets the center point of the Largest Empty Circle (up to the tolerance distance).
        Returns:
        the center point of the Largest Empty Circle
      • getRadiusPoint

        public Point getRadiusPoint()
        Gets a point defining the radius of the Largest Empty Circle. This is a point on the obstacles which is nearest to the computed center of the Largest Empty 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 Largest Empty 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