Class MinimumClearance

1	/*
2	* Copyright (c) 2016 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.precision;
13
14	import org.locationtech.jts.algorithm.Distance;
15	import org.locationtech.jts.geom.Coordinate;
16	import org.locationtech.jts.geom.Geometry;
17	import org.locationtech.jts.geom.LineSegment;
18	import org.locationtech.jts.geom.LineString;
19	import org.locationtech.jts.geom.Lineal;
20	import org.locationtech.jts.geom.MultiPoint;
21	import org.locationtech.jts.geom.Point;
22	import org.locationtech.jts.geom.Puntal;
23	import org.locationtech.jts.index.strtree.ItemBoundable;
24	import org.locationtech.jts.index.strtree.ItemDistance;
25	import org.locationtech.jts.index.strtree.STRtree;
26	import org.locationtech.jts.operation.distance.FacetSequence;
27	import org.locationtech.jts.operation.distance.FacetSequenceTreeBuilder;
28
29	/**
30	* Computes the Minimum Clearance of a {@link Geometry}.
31	* <p>
32	* The <b>Minimum Clearance</b> is a measure of
33	* what magnitude of perturbation of
34	* the vertices of a geometry can be tolerated
35	* before the geometry becomes topologically invalid.
36	* The smaller the Minimum Clearance distance,
37	* the less vertex perturbation the geometry can tolerate
38	* before becoming invalid.
39	* <p>
40	* The concept was introduced by Thompson and Van Oosterom
41	* [TV06], based on earlier work by Milenkovic [Mi88].
42	* <p>
43	* The Minimum Clearance of a geometry G
44	* is defined to be the value <i>r</i>
45	* such that "the movement of all points by a distance
46	* of <i>r</i> in any direction will
47	* guarantee to leave the geometry valid" [TV06].
48	* An equivalent constructive definition [Mi88] is that
49	* <i>r</i> is the largest value such:
50	* <ol>
51	* <li>No two distinct vertices of G are closer than <i>r</i>
52	* <li>No vertex of G is closer than <i>r</i> to an edge of G
53	* of which the vertex is not an endpoint
54	* </ol>
55	* The following image shows an example of the Minimum Clearance
56	* of a simple polygon.
57	* <p>
58	* <center><img src='doc-files/minClearance.png'></center>
59	* <p>
60	* If G has only a single vertex (i.e. is a
61	* {@link Point}), the value of the minimum clearance
62	* is {@link Double#MAX_VALUE}.
63	* <p>
64	* If G is a {@link Puntal} or {@link Lineal} geometry,
65	* then in fact no amount of perturbation
66	* will render the geometry invalid.
67	* In this case a Minimum Clearance is still computed
68	* based on the vertex and segment distances
69	* according to the constructive definition.
70	* <p>
71	* It is possible for no Minimum Clearance to exist.
72	* For instance, a {@link MultiPoint} with all members identical
73	* has no Minimum Clearance
74	* (i.e. no amount of perturbation will cause
75	* the member points to become non-identical).
76	* Empty geometries also have no such distance.
77	* The lack of a meaningful MinimumClearance distance is detected
78	* and suitable values are returned by
79	* {@link #getDistance()} and {@link #getLine()}.
80	* <p>
81	* The computation of Minimum Clearance utilizes
82	* the {@link STRtree#nearestNeighbour(ItemDistance)}
83	* method to provide good performance even for
84	* large inputs.
85	* <p>
86	* An interesting note is that for the case of {@link MultiPoint}s,
87	* the computed Minimum Clearance line
88	* effectively determines the Nearest Neighbours in the collection.
89	*
90	* <h3>References</h3>
91	* <ul>
92	* <li>[Mi88] Milenkovic, V. J.,
93	* <i>Verifiable implementations of geometric algorithms
94	* using finite precision arithmetic</i>.
95	* in Artificial Intelligence, 377-401. 1988
96	* <li>[TV06] Thompson, Rod and van Oosterom, Peter,
97	* <i>Interchange of Spatial Data-Inhibiting Factors</i>,
98	* Agile 2006, Visegrad, Hungary. 2006
99	* </ul>
100	*
101	* @author Martin Davis
102	*
103	*/
104	public class MinimumClearance
105	{
106	/**
107	* Computes the Minimum Clearance distance for
108	* the given Geometry.
109	*
110	* @param g the input geometry
111	* @return the Minimum Clearance distance
112	*/
113	public static double getDistance(Geometry g)
114	{
115	MinimumClearance rp = new MinimumClearance(g);
116	return rp.getDistance();
117	}
118
119	/**
120	* Gets a LineString containing two points
121	* which are at the Minimum Clearance distance
122	* for the given Geometry.
123	*
124	* @param g the input geometry
125	* @return the value of the minimum clearance distance
126	* or <tt>LINESTRING EMPTY</tt> if no Minimum Clearance distance exists
127	*/
128	public static Geometry getLine(Geometry g)
129	{
130	MinimumClearance rp = new MinimumClearance(g);
131	return rp.getLine();
132	}
133
134	private Geometry inputGeom;
135	private double minClearance;
136	private Coordinate[] minClearancePts;
137
138	/**
139	* Creates an object to compute the Minimum Clearance
140	* for the given Geometry
141	*
142	* @param geom the input geometry
143	*/
144	public MinimumClearance(Geometry geom)
145	{
146	inputGeom = geom;
147	}
148
149	/**
150	* Gets the Minimum Clearance distance.
151	* <p>
152	* If no distance exists
153	* (e.g. in the case of two identical points)
154	* <tt>Double.MAX_VALUE</tt> is returned.
155	*
156	* @return the value of the minimum clearance distance
157	* or <tt>Double.MAX_VALUE</tt> if no Minimum Clearance distance exists
158	*/
159	public double getDistance()
160	{
161	compute();
162	return minClearance;
163	}
164
165	/**
166	* Gets a LineString containing two points
167	* which are at the Minimum Clearance distance.
168	* <p>
169	* If no distance could be found
170	* (e.g. in the case of two identical points)
171	* <tt>LINESTRING EMPTY</tt> is returned.
172	*
173	* @return the value of the minimum clearance distance
174	* or <tt>LINESTRING EMPTY</tt> if no Minimum Clearance distance exists
175	*/
176	public LineString getLine()
177	{
178	compute();
179	// return empty line string if no min pts where found
180	if (minClearancePts == null \|\| minClearancePts[0] == null)
181	return inputGeom.getFactory().createLineString();
182	return inputGeom.getFactory().createLineString(minClearancePts);
183	}
184
185	private void compute()
186	{
187	// already computed
188	if (minClearancePts != null) return;
189
190	// initialize to "No Distance Exists" state
191	minClearancePts = new Coordinate[2];
192	minClearance = Double.MAX_VALUE;
193
194	// handle empty geometries
195	if (inputGeom.isEmpty()) {
196	return;
197	}
198
199	STRtree geomTree = FacetSequenceTreeBuilder.build(inputGeom);
200
201	Object[] nearest = geomTree.nearestNeighbour(new MinClearanceDistance());
202	MinClearanceDistance mcd = new MinClearanceDistance();
203	minClearance = mcd.distance(
204	(FacetSequence) nearest[0],
205	(FacetSequence) nearest[1]);
206	minClearancePts = mcd.getCoordinates();
207	}
208
209	/**
210	* Implements the MinimumClearance distance function:
211	* <ul>
212	* <li>dist(p1, p2) =
213	* <ul>
214	* <li>p1 != p2 : p1.distance(p2)
215	* <li>p1 == p2 : Double.MAX
216	* </ul>
217	* <li>dist(p, seg) =
218	* <ul>
219	* <li>p != seq.p1 && p != seg.p2 : seg.distance(p)
220	* <li>ELSE : Double.MAX
221	* </ul>
222	* </ul>
223	* Also computes the values of the nearest points, if any.
224	*
225	* @author Martin Davis
226	*
227	*/
228	private static class MinClearanceDistance
229	implements ItemDistance
230	{
231	private double minDist = Double.MAX_VALUE;
232	private Coordinate[] minPts = new Coordinate[2];
233
234	public Coordinate[] getCoordinates()
235	{
236	return minPts;
237	}
238
239	public double distance(ItemBoundable b1, ItemBoundable b2) {
240	FacetSequence fs1 = (FacetSequence) b1.getItem();
241	FacetSequence fs2 = (FacetSequence) b2.getItem();
242	minDist = Double.MAX_VALUE;
243	return distance(fs1, fs2);
244	}
245
246	public double distance(FacetSequence fs1, FacetSequence fs2) {
247
248	// compute MinClearance distance metric
249
250	vertexDistance(fs1, fs2);
251	if (fs1.size() == 1 && fs2.size() == 1) return minDist;
252	if (minDist <= 0.0) return minDist;
253	segmentDistance(fs1, fs2);
254	if (minDist <= 0.0) return minDist;
255	segmentDistance(fs2, fs1);
256	return minDist;
257	}
258
259	private double vertexDistance(FacetSequence fs1, FacetSequence fs2) {
260	for (int i1 = 0; i1 < fs1.size(); i1++) {
261	for (int i2 = 0; i2 < fs2.size(); i2++) {
262	Coordinate p1 = fs1.getCoordinate(i1);
263	Coordinate p2 = fs2.getCoordinate(i2);
264	if (! p1.equals2D(p2)) {
265	double d = p1.distance(p2);
266	if (d < minDist) {
267	minDist = d;
268	minPts[0] = p1;
269	minPts[1] = p2;
270	if (d == 0.0)
271	return d;
272	}
273	}
274	}
275	}
276	return minDist;
277	}
278
279	private double segmentDistance(FacetSequence fs1, FacetSequence fs2) {
280	for (int i1 = 0; i1 < fs1.size(); i1++) {
281	for (int i2 = 1; i2 < fs2.size(); i2++) {
282
283	Coordinate p = fs1.getCoordinate(i1);
284
285	Coordinate seg0 = fs2.getCoordinate(i2-1);
286	Coordinate seg1 = fs2.getCoordinate(i2);
287
288	if (! (p.equals2D(seg0) \|\| p.equals2D(seg1))) {
289	double d = Distance.pointToSegment(p, seg0, seg1);
290	if (d < minDist) {
291	minDist = d;
292	updatePts(p, seg0, seg1);
293	if (d == 0.0)
294	return d;
295	}
296	}
297	}
298	}
299	return minDist;
300	}
301
302	private void updatePts(Coordinate p, Coordinate seg0, Coordinate seg1)
303	{
304	minPts[0] = p;
305	LineSegment seg = new LineSegment(seg0, seg1);
306	minPts[1] = new Coordinate(seg.closestPoint(p));
307	}
308
309
310	}
311
312
313	}
314
315
316