Class LargestEmptyCircle

1	/*
2	* Copyright (c) 2020 Martin Davis.
3	*
4	* All rights reserved. This program and the accompanying materials
5	* are made available under the terms of the Eclipse Public License 2.0
6	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
7	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
8	* and the Eclipse Distribution License is available at
9	*
10	* http://www.eclipse.org/org/documents/edl-v10.php.
11	*/
12	package org.locationtech.jts.algorithm.construct;
13
14	import java.util.PriorityQueue;
15
16	import org.locationtech.jts.algorithm.locate.IndexedPointInAreaLocator;
17	import org.locationtech.jts.geom.Coordinate;
18	import org.locationtech.jts.geom.Envelope;
19	import org.locationtech.jts.geom.Geometry;
20	import org.locationtech.jts.geom.GeometryFactory;
21	import org.locationtech.jts.geom.LineString;
22	import org.locationtech.jts.geom.Location;
23	import org.locationtech.jts.geom.Point;
24	import org.locationtech.jts.operation.distance.IndexedFacetDistance;
25
26	/**
27	* Constructs the Largest Empty Circle for a set
28	* of obstacle geometries, up to a specified tolerance.
29	* The obstacles are point and line geometries.
30	* <p>
31	* The Largest Empty Circle is the largest circle which
32	* has its center in the convex hull of the obstacles (the <i>boundary</i>),
33	* and whose interior does not intersect with any obstacle.
34	* The circle center is the point in the interior of the boundary
35	* which has the farthest distance from the obstacles (up to tolerance).
36	* The circle is determined by the center point
37	* and a point lying on an obstacle indicating the circle radius.
38	* <p>
39	* The implementation uses a successive-approximation technique
40	* over a grid of square cells covering the obstacles and boundary.
41	* The grid is refined using a branch-and-bound algorithm.
42	* Point containment and distance are computed in a performant
43	* way by using spatial indexes.
44	* <p>
45	* <h3>Future Enhancements</h3>
46	* <ul>
47	* <li>Support polygons as obstacles
48	* <li>Support a client-defined boundary polygon
49	* </ul>
50	*
51	* @author Martin Davis
52	*/
53	public class LargestEmptyCircle {
54
55	/**
56	* Computes the center point of the Largest Empty Circle
57	* within a set of obstacles, up to a given tolerance distance.
58	*
59	* @param obstacles a geometry representing the obstacles (points and lines)
60	* @param tolerance the distance tolerance for computing the center point
61	* @return the center point of the Largest Empty Circle
62	*/
63	public static Point getCenter(Geometry obstacles, double tolerance) {
64	LargestEmptyCircle lec = new LargestEmptyCircle(obstacles, tolerance);
65	return lec.getCenter();
66	}
67
68	/**
69	* Computes a radius line of the Largest Empty Circle
70	* within a set of obstacles, up to a given distance tolerance.
71	*
72	* @param obstacles a geometry representing the obstacles (points and lines)
73	* @param tolerance the distance tolerance for computing the center point
74	* @return a line from the center of the circle to a point on the edge
75	*/
76	public static LineString getRadiusLine(Geometry obstacles, double tolerance) {
77	LargestEmptyCircle lec = new LargestEmptyCircle(obstacles, tolerance);
78	return lec.getRadiusLine();
79	}
80
81	private Geometry obstacles;
82	private double tolerance;
83
84	private GeometryFactory factory;
85	private Geometry boundary;
86	private IndexedPointInAreaLocator ptLocater;
87	private IndexedFacetDistance obstacleDistance;
88	private IndexedFacetDistance boundaryDistance;
89	private Cell farthestCell;
90
91	private Cell centerCell = null;
92	private Coordinate centerPt;
93	private Point centerPoint = null;
94	private Coordinate radiusPt;
95	private Point radiusPoint = null;
96
97	/**
98	* Creates a new instance of a Largest Empty Circle construction.
99	*
100	* @param obstacles a geometry representing the obstacles (points and lines)
101	* @param tolerance the distance tolerance for computing the circle center point
102	*/
103	public LargestEmptyCircle(Geometry obstacles, double tolerance) {
104	if (obstacles.isEmpty()) {
105	throw new IllegalArgumentException("Empty obstacles geometry is not supported");
106	}
107
108	this.obstacles = obstacles;
109	this.factory = obstacles.getFactory();
110	this.tolerance = tolerance;
111	obstacleDistance = new IndexedFacetDistance( obstacles );
112	setBoundary(obstacles);
113	}
114
115	/**
116	* Sets the area boundary as the convex hull
117	* of the obstacles.
118	*
119	* @param obstacles
120	*/
121	private void setBoundary(Geometry obstacles) {
122	// TODO: allow this to be set by client as arbitrary polygon
123	this.boundary = obstacles.convexHull();
124	// if boundary does not enclose an area cannot create a ptLocater
125	if (boundary.getDimension() >= 2) {
126	ptLocater = new IndexedPointInAreaLocator(boundary);
127	boundaryDistance = new IndexedFacetDistance( boundary );
128	}
129	}
130
131	/**
132	* Gets the center point of the Largest Empty Circle
133	* (up to the tolerance distance).
134	*
135	* @return the center point of the Largest Empty Circle
136	*/
137	public Point getCenter() {
138	compute();
139	return centerPoint;
140	}
141
142	/**
143	* Gets a point defining the radius of the Largest Empty Circle.
144	* This is a point on the obstacles which is
145	* nearest to the computed center of the Largest Empty Circle.
146	* The line segment from the center to this point
147	* is a radius of the constructed circle, and this point
148	* lies on the boundary of the circle.
149	*
150	* @return a point defining the radius of the Largest Empty Circle
151	*/
152	public Point getRadiusPoint() {
153	compute();
154	return radiusPoint;
155	}
156
157	/**
158	* Gets a line representing a radius of the Largest Empty Circle.
159	*
160	* @return a line from the center of the circle to a point on the edge
161	*/
162	public LineString getRadiusLine() {
163	compute();
164	LineString radiusLine = factory.createLineString(
165	new Coordinate[] { centerPt.copy(), radiusPt.copy() });
166	return radiusLine;
167	}
168
169	/**
170	* Computes the signed distance from a point to the constraints
171	* (obstacles and boundary).
172	* Points outside the boundary polygon are assigned a negative distance.
173	* Their containing cells will be last in the priority queue
174	* (but will still end up being tested since they may be refined).
175	*
176	* @param p the point to compute the distance for
177	* @return the signed distance to the constraints (negative indicates outside the boundary)
178	*/
179	private double distanceToConstraints(Point p) {
180	boolean isOutide = Location.EXTERIOR == ptLocater.locate(p.getCoordinate());
181	if (isOutide) {
182	double boundaryDist = boundaryDistance.distance(p);
183	return -boundaryDist;
184	}
185	double dist = obstacleDistance.distance(p);
186	return dist;
187	}
188
189	private double distanceToConstraints(double x, double y) {
190	Coordinate coord = new Coordinate(x, y);
191	Point pt = factory.createPoint(coord);
192	return distanceToConstraints(pt);
193	}
194
195	private void compute() {
196	// check if already computed
197	if (centerCell != null) return;
198
199	// if ptLocater is not present then result is degenerate (represented as zero-radius circle)
200	if (ptLocater == null) {
201	Coordinate pt = obstacles.getCoordinate();
202	centerPt = pt.copy();
203	centerPoint = factory.createPoint(pt);
204	radiusPt = pt.copy();
205	radiusPoint = factory.createPoint(pt);
206	return;
207	}
208
209	// Priority queue of cells, ordered by decreasing distance from constraints
210	PriorityQueue<Cell> cellQueue = new PriorityQueue<>();
211
212	createInitialGrid(obstacles.getEnvelopeInternal(), cellQueue);
213
214	// use the area centroid as the initial candidate center point
215	farthestCell = createCentroidCell(obstacles);
216	//int totalCells = cellQueue.size();
217
218	/**
219	* Carry out the branch-and-bound search
220	* of the cell space
221	*/
222	while (! cellQueue.isEmpty()) {
223	// pick the cell with greatest distance from the queue
224	Cell cell = cellQueue.remove();
225
226	// update the center cell if the candidate is further from the constraints
227	if (cell.getDistance() > farthestCell.getDistance()) {
228	farthestCell = cell;
229	}
230
231	/**
232	* If this cell may contain a better approximation to the center
233	* of the empty circle, then refine it (partition into subcells
234	* which are added into the queue for further processing).
235	* Otherwise the cell is pruned (not investigated further),
236	* since no point in it can be further than the current farthest distance.
237	*/
238	if (mayContainCircleCenter(cell)) {
239	// split the cell into four sub-cells
240	double h2 = cell.getHSide() / 2;
241	cellQueue.add( createCell( cell.getX() - h2, cell.getY() - h2, h2));
242	cellQueue.add( createCell( cell.getX() + h2, cell.getY() - h2, h2));
243	cellQueue.add( createCell( cell.getX() - h2, cell.getY() + h2, h2));
244	cellQueue.add( createCell( cell.getX() + h2, cell.getY() + h2, h2));
245	//totalCells += 4;
246	}
247	}
248	// the farthest cell is the best approximation to the LEC center
249	centerCell = farthestCell;
250	// compute center point
251	centerPt = new Coordinate(centerCell.getX(), centerCell.getY());
252	centerPoint = factory.createPoint(centerPt);
253	// compute radius point
254	Coordinate[] nearestPts = obstacleDistance.nearestPoints(centerPoint);
255	radiusPt = nearestPts[0].copy();
256	radiusPoint = factory.createPoint(radiusPt);
257	}
258
259	/**
260	* Tests whether a cell may contain the circle center,
261	* and thus should be refined (split into subcells
262	* to be investigated further.)
263	*
264	* @param cell the cell to test
265	* @return true if the cell might contain the circle center
266	*/
267	private boolean mayContainCircleCenter(Cell cell) {
268	/**
269	* Every point in the cell lies outside the boundary,
270	* so they cannot be the center point
271	*/
272	if (cell.isFullyOutside())
273	return false;
274
275	/**
276	* The cell is outside, but overlaps the boundary
277	* so it may contain a point which should be checked.
278	* This is only the case if the potential overlap distance
279	* is larger than the tolerance.
280	*/
281	if (cell.isOutside()) {
282	boolean isOverlapSignificant = cell.getMaxDistance() > tolerance;
283	return isOverlapSignificant;
284	}
285
286	/**
287	* Cell is inside the boundary. It may contain the center
288	* if the maximum possible distance is greater than the current distance
289	* (up to tolerance).
290	*/
291	double potentialIncrease = cell.getMaxDistance() - farthestCell.getDistance();
292	return potentialIncrease > tolerance;
293	}
294
295	/**
296	* Initializes the queue with a grid of cells covering
297	* the extent of the area.
298	*
299	* @param env the area extent to cover
300	* @param cellQueue the queue to initialize
301	*/
302	private void createInitialGrid(Envelope env, PriorityQueue<Cell> cellQueue) {
303	double minX = env.getMinX();
304	double maxX = env.getMaxX();
305	double minY = env.getMinY();
306	double maxY = env.getMaxY();
307	double width = env.getWidth();
308	double height = env.getHeight();
309	double cellSize = Math.min(width, height);
310	double hSize = cellSize / 2.0;
311
312	// compute initial grid of cells to cover area
313	for (double x = minX; x < maxX; x += cellSize) {
314	for (double y = minY; y < maxY; y += cellSize) {
315	cellQueue.add(createCell(x + hSize, y + hSize, hSize));
316	}
317	}
318	}
319
320	private Cell createCell(double x, double y, double h) {
321	return new Cell(x, y, h, distanceToConstraints(x, y));
322	}
323
324	// create a cell centered on area centroid
325	private Cell createCentroidCell(Geometry geom) {
326	Point p = geom.getCentroid();
327	return new Cell(p.getX(), p.getY(), 0, distanceToConstraints(p));
328	}
329
330	/**
331	* A square grid cell centered on a given point
332	* with a given side half-length,
333	* and having a given distance from the center point to the constraints.
334	* The maximum possible distance from any point in the cell to the
335	* constraints can be computed.
336	* This is used as the ordering and upper-bound function in
337	* the branch-and-bound algorithm.
338	*/
339	private static class Cell implements Comparable<Cell> {
340
341	private static final double SQRT2 = 1.4142135623730951;
342
343	private double x;
344	private double y;
345	private double hSide;
346	private double distance;
347	private double maxDist;
348
349	Cell(double x, double y, double hSide, double distanceToConstraints) {
350	this.x = x; // cell center x
351	this.y = y; // cell center y
352	this.hSide = hSide; // half the cell size
353
354	// the distance from cell center to constraints
355	distance = distanceToConstraints;
356
357	/**
358	* The maximum possible distance to the constraints for points in this cell
359	* is the center distance plus the radius (half the diagonal length).
360	*/
361	this.maxDist = distance + hSide * SQRT2;
362	}
363
364	public boolean isFullyOutside() {
365	return getMaxDistance() < 0;
366	}
367
368	public boolean isOutside() {
369	return distance < 0;
370	}
371
372	public double getMaxDistance() {
373	return maxDist;
374	}
375
376	public double getDistance() {
377	return distance;
378	}
379
380	public double getHSide() {
381	return hSide;
382	}
383
384	public double getX() {
385	return x;
386	}
387
388	public double getY() {
389	return y;
390	}
391
392	/**
393	* A cell is greater iff its maximum distance is larger.
394	*/
395	public int compareTo(Cell o) {
396	return (int) (o.maxDist - this.maxDist);
397	}
398	}
399
400	}
401