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

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 Detail

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]