Package micycle.pgs.commons

Class LargestEmptyCircles

java.lang.Object
micycle.pgs.commons.LargestEmptyCircles
public class LargestEmptyCircles extends Object
Adapts LargestEmptyCircle, allowing for repeated calls to find the N largest empty circles in an optimised manner.

In this adaptation circle circumferences are constrained to lie within the boundary (originally only circle center points must lie within the boundary). This adaption also supports polygonal obstacles; if a boundary is provided, circles will not lie within the polygonal obstacles.

Author:
Martin Davis, Michael Carleton

  • Constructor Summary

    Constructors
    Constructor
    Description
    LargestEmptyCircles(org.locationtech.jts.geom.Geometry obstacles, org.locationtech.jts.geom.Geometry boundary, double tolerance)
    Constructs a new Largest Empty Circles (LEC) instance, ensuring that the circles are interior-disjoint to a set of obstacle geometries and (optional) contained within a polygonal boundary.

  • Method Summary

    Modifier and Type
    Method
    Description
    double[][]
    findLECs(int n)
    Computes the (next) N largest empty circles.
    double[]
    findNextLEC()
    Computes the next largest empty circle.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Constructor Details

    • LargestEmptyCircles

      public LargestEmptyCircles(org.locationtech.jts.geom.Geometry obstacles, org.locationtech.jts.geom.Geometry boundary, double tolerance)
      Constructs a new Largest Empty Circles (LEC) instance, ensuring that the circles are interior-disjoint to a set of obstacle geometries and (optional) contained within a polygonal boundary.

    • If the provided boundary is null and obstacles are linear/pointal, the convex hull of the obstacles is used as the boundary.
    • If the provided boundary is null and obstacles are polygonal, the obstacles themselves form the boundary (effectively function as a "Maximum Inscribed Circles" algorithm.).
      • Parameters:
      obstacles - geometry representing the obstacles; if null, the boundary is used instead
      boundary - a polygonal geometry (may be null)
      tolerance - a positive distance tolerance for computing the circle center point
      Throws:
      IllegalArgumentException - if the obstacles geometry or the tolerance is non-positive

  • Method Details

    • findLECs

      public double[][] findLECs(int n)
      Computes the (next) N largest empty circles.
      Parameters:
      n - number of circles
      Returns:
      array of circles; each circle is represented as: [x,y,r]

    • findNextLEC

      public double[] findNextLEC()
      Computes the next largest empty circle.
      Returns:
      an array representing the circle: [x,y,r]