Class IndexedFacetDistance

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
13	package org.locationtech.jts.operation.distance;
14
15	import org.locationtech.jts.geom.Coordinate;
16	import org.locationtech.jts.geom.Geometry;
17	import org.locationtech.jts.geom.Lineal;
18	import org.locationtech.jts.geom.Polygonal;
19	import org.locationtech.jts.geom.Puntal;
20	import org.locationtech.jts.index.strtree.ItemBoundable;
21	import org.locationtech.jts.index.strtree.ItemDistance;
22	import org.locationtech.jts.index.strtree.STRtree;
23
24	/**
25	* Computes the distance between the facets (segments and vertices)
26	* of two {@link Geometry}s
27	* using a Branch-and-Bound algorithm.
28	* The Branch-and-Bound algorithm operates over a
29	* traversal of R-trees built
30	* on the target and the query geometries.
31	* <p>
32	* This approach provides the following benefits:
33	* <ul>
34	* <li>Performance is dramatically improved due to the use of the
35	* R-tree index
36	* and the pruning due to the Branch-and-Bound approach
37	* <li>The spatial index on the target geometry is cached
38	* which allow reuse in an repeated query situation.
39	* </ul>
40	* Using this technique is usually much more performant
41	* than using the brute-force {@link Geometry#distance(Geometry)}
42	* when one or both input geometries are large,
43	* or when evaluating many distance computations against
44	* a single geometry.
45	* <p>
46	* This class is thread-safe.
47	*
48	* @author Martin Davis
49	*
50	*/
51	public class IndexedFacetDistance
52	{
53	private static final FacetSequenceDistance FACET_SEQ_DIST = new FacetSequenceDistance();
54
55	/**
56	* Computes the distance between facets of two geometries.
57	* <p>
58	* For geometries with many segments or points,
59	* this can be faster than using a simple distance
60	* algorithm.
61	*
62	* @param g1 a geometry
63	* @param g2 a geometry
64	* @return the distance between facets of the geometries
65	*/
66	public static double distance(Geometry g1, Geometry g2)
67	{
68	IndexedFacetDistance dist = new IndexedFacetDistance(g1);
69	return dist.distance(g2);
70	}
71
72	/**
73	* Tests whether the facets of two geometries lie within a given distance.
74	*
75	* @param g1 a geometry
76	* @param g2 a geometry
77	* @param distance the distance limit
78	* @return true if two facets lie with the given distance
79	*/
80	public static boolean isWithinDistance(Geometry g1, Geometry g2, double distance) {
81	IndexedFacetDistance dist = new IndexedFacetDistance(g1);
82	return dist.isWithinDistance(g2, distance);
83	}
84
85	/**
86	* Computes the nearest points of the facets of two geometries.
87	*
88	* @param g1 a geometry
89	* @param g2 a geometry
90	* @return the nearest points on the facets of the geometries
91	*/
92	public static Coordinate[] nearestPoints(Geometry g1, Geometry g2) {
93	IndexedFacetDistance dist = new IndexedFacetDistance(g1);
94	return dist.nearestPoints(g2);
95	}
96
97	private STRtree cachedTree;
98	private Geometry baseGeometry;
99
100	/**
101	* Creates a new distance-finding instance for a given target {@link Geometry}.
102	* <p>
103	* Distances will be computed to all facets of the input geometry.
104	* The facets of the geometry are the discrete segments and points
105	* contained in its components.
106	* In the case of {@link Lineal} and {@link Puntal} inputs,
107	* this is equivalent to computing the conventional distance.
108	* In the case of {@link Polygonal} inputs, this is equivalent
109	* to computing the distance to the polygon boundaries.
110	*
111	* @param geom a Geometry, which may be of any type.
112	*/
113	public IndexedFacetDistance(Geometry geom) {
114	this.baseGeometry = geom;
115	cachedTree = FacetSequenceTreeBuilder.build(geom);
116	}
117
118	/**
119	* Computes the distance from the base geometry to
120	* the given geometry.
121	*
122	* @param g the geometry to compute the distance to
123	*
124	* @return the computed distance
125	*/
126	public double distance(Geometry g)
127	{
128	STRtree tree2 = FacetSequenceTreeBuilder.build(g);
129	Object[] obj = cachedTree.nearestNeighbour(tree2,
130	FACET_SEQ_DIST);
131	FacetSequence fs1 = (FacetSequence) obj[0];
132	FacetSequence fs2 = (FacetSequence) obj[1];
133	return fs1.distance(fs2);
134	}
135
136	/**
137	* Computes the nearest locations on the base geometry
138	* and the given geometry.
139	*
140	* @param g the geometry to compute the nearest location to
141	* @return the nearest locations
142	*/
143	public GeometryLocation[] nearestLocations(Geometry g)
144	{
145	STRtree tree2 = FacetSequenceTreeBuilder.build(g);
146	Object[] obj = cachedTree.nearestNeighbour(tree2,
147	FACET_SEQ_DIST);
148	FacetSequence fs1 = (FacetSequence) obj[0];
149	FacetSequence fs2 = (FacetSequence) obj[1];
150	return fs1.nearestLocations(fs2);
151	}
152
153	/**
154	* Compute the nearest locations on the target geometry
155	* and the given geometry.
156	*
157	* @param g the geometry to compute the nearest point to
158	* @return the nearest points
159	*/
160	public Coordinate[] nearestPoints(Geometry g) {
161	GeometryLocation[] minDistanceLocation = nearestLocations(g);
162	Coordinate[] nearestPts = toPoints(minDistanceLocation);
163	return nearestPts;
164	}
165
166	private static Coordinate[] toPoints(GeometryLocation[] locations) {
167	if (locations == null)
168	return null;
169	Coordinate[] nearestPts = new Coordinate[] {
170	locations[0].getCoordinate(),
171	locations[1].getCoordinate() };
172	return nearestPts;
173	}
174
175	/**
176	* Tests whether the base geometry lies within
177	* a specified distance of the given geometry.
178	*
179	* @param g the geometry to test
180	* @param maxDistance the maximum distance to test
181	* @return true if the geometry lies with the specified distance
182	*/
183	public boolean isWithinDistance(Geometry g, double maxDistance) {
184	// short-ciruit check
185	double envDist = baseGeometry.getEnvelopeInternal().distance(g.getEnvelopeInternal());
186	if (envDist > maxDistance)
187	return false;
188
189	STRtree tree2 = FacetSequenceTreeBuilder.build(g);
190	return cachedTree.isWithinDistance(tree2,
191	FACET_SEQ_DIST, maxDistance);
192	}
193
194	private static class FacetSequenceDistance
195	implements ItemDistance
196	{
197	public double distance(ItemBoundable item1, ItemBoundable item2) {
198	FacetSequence fs1 = (FacetSequence) item1.getItem();
199	FacetSequence fs2 = (FacetSequence) item2.getItem();
200	return fs1.distance(fs2);
201	}
202	}
203
204
205
206	}
207
208
209