Class MonotoneChain

1
2
3	/*
4	* Copyright (c) 2016 Vivid Solutions.
5	*
6	* All rights reserved. This program and the accompanying materials
7	* are made available under the terms of the Eclipse Public License 2.0
8	* and Eclipse Distribution License v. 1.0 which accompanies this distribution.
9	* The Eclipse Public License is available at http://www.eclipse.org/legal/epl-v20.html
10	* and the Eclipse Distribution License is available at
11	*
12	* http://www.eclipse.org/org/documents/edl-v10.php.
13	*/
14	package org.locationtech.jts.index.chain;
15
16	import org.locationtech.jts.geom.Coordinate;
17	import org.locationtech.jts.geom.Envelope;
18	import org.locationtech.jts.geom.LineSegment;
19	import org.locationtech.jts.geomgraph.index.MonotoneChainEdge;
20
21
22	/**
23	* Monotone Chains are a way of partitioning the segments of a linestring to
24	* allow for fast searching of intersections.
25	* They have the following properties:
26	* <ol>
27	* <li>the segments within a monotone chain never intersect each other
28	* <li>the envelope of any contiguous subset of the segments in a monotone chain
29	* is equal to the envelope of the endpoints of the subset.
30	* </ol>
31	* Property 1 means that there is no need to test pairs of segments from within
32	* the same monotone chain for intersection.
33	* <p>
34	* Property 2 allows
35	* an efficient binary search to be used to find the intersection points of two monotone chains.
36	* For many types of real-world data, these properties eliminate a large number of
37	* segment comparisons, producing substantial speed gains.
38	* <p>
39	* One of the goals of this implementation of MonotoneChains is to be
40	* as space and time efficient as possible. One design choice that aids this
41	* is that a MonotoneChain is based on a subarray of a list of points.
42	* This means that new arrays of points (potentially very large) do not
43	* have to be allocated.
44	* <p>
45	*
46	* MonotoneChains support the following kinds of queries:
47	* <ul>
48	* <li>Envelope select: determine all the segments in the chain which
49	* intersect a given envelope
50	* <li>Overlap: determine all the pairs of segments in two chains whose
51	* envelopes overlap
52	* </ul>
53	*
54	* This implementation of MonotoneChains uses the concept of internal iterators
55	* ({@link MonotoneChainSelectAction} and {@link MonotoneChainOverlapAction})
56	* to return the results for queries.
57	* This has time and space advantages, since it
58	* is not necessary to build lists of instantiated objects to represent the segments
59	* returned by the query.
60	* Queries made in this manner are thread-safe.
61	*
62	* MonotoneChains support being assigned an integer id value
63	* to provide a total ordering for a set of chains.
64	* This can be used during some kinds of processing to
65	* avoid redundant comparisons
66	* (i.e. by comparing only chains where the first id is less than the second).
67	*
68	* @version 1.7
69	*/
70	public class MonotoneChain {
71
72	private Coordinate[] pts;
73	private int start, end;
74	private Envelope env = null;
75	private Object context = null;// user-defined information
76	private int id;// useful for optimizing chain comparisons
77
78	/**
79	* Creates a new MonotoneChain based on the given array of points.
80	* @param pts the points containing the chain
81	* @param start the index of the first coordinate in the chain
82	* @param end the index of the last coordinate in the chain
83	* @param context a user-defined data object
84	*/
85	public MonotoneChain(Coordinate[] pts, int start, int end, Object context)
86	{
87	this.pts = pts;
88	this.start = start;
89	this.end = end;
90	this.context = context;
91	}
92
93	/**
94	* Sets the id of this chain.
95	* Useful for assigning an ordering to a set of
96	* chains, which can be used to avoid redundant processing.
97	*
98	* @param id an id value
99	*/
100	public void setId(int id) { this.id = id; }
101
102	/**
103	* Gets the id of this chain.
104	*
105	* @return the id value
106	*/
107	public int getId() { return id; }
108
109	/**
110	* Gets the user-defined context data value.
111	*
112	* @return a data value
113	*/
114	public Object getContext() { return context; }
115
116	/**
117	* Gets the envelope of the chain.
118	*
119	* @return the envelope of the chain
120	*/
121	public Envelope getEnvelope()
122	{
123	if (env == null) {
124	/**
125	* The monotonicity property allows fast envelope determination
126	*/
127	Coordinate p0 = pts[start];
128	Coordinate p1 = pts[end];
129	env = new Envelope(p0, p1);
130	}
131	return env;
132	}
133
134	/**
135	* Gets the index of the start of the monotone chain
136	* in the underlying array of points.
137	*
138	* @return the start index of the chain
139	*/
140	public int getStartIndex() { return start; }
141
142	/**
143	* Gets the index of the end of the monotone chain
144	* in the underlying array of points.
145	*
146	* @return the end index of the chain
147	*/
148	public int getEndIndex() { return end; }
149
150	/**
151	* Gets the line segment starting at <code>index</code>
152	*
153	* @param index index of segment
154	* @param ls line segment to extract into
155	*/
156	public void getLineSegment(int index, LineSegment ls)
157	{
158	ls.p0 = pts[index];
159	ls.p1 = pts[index + 1];
160	}
161	/**
162	* Return the subsequence of coordinates forming this chain.
163	* Allocates a new array to hold the Coordinates
164	*/
165	public Coordinate[] getCoordinates()
166	{
167	Coordinate coord[] = new Coordinate[end - start + 1];
168	int index = 0;
169	for (int i = start; i <= end; i++) {
170	coord[index++] = pts[i];
171	}
172	return coord;
173	}
174
175	/**
176	* Determine all the line segments in the chain whose envelopes overlap
177	* the searchEnvelope, and process them.
178	* <p>
179	* The monotone chain search algorithm attempts to optimize
180	* performance by not calling the select action on chain segments
181	* which it can determine are not in the search envelope.
182	* However, it may call the select action on segments
183	* which do not intersect the search envelope.
184	* This saves on the overhead of checking envelope intersection
185	* each time, since clients may be able to do this more efficiently.
186	*
187	* @param searchEnv the search envelope
188	* @param mcs the select action to execute on selected segments
189	*/
190	public void select(Envelope searchEnv, MonotoneChainSelectAction mcs)
191	{
192	computeSelect(searchEnv, start, end, mcs);
193	}
194
195	private void computeSelect(
196	Envelope searchEnv,
197	int start0, int end0,
198	MonotoneChainSelectAction mcs )
199	{
200	Coordinate p0 = pts[start0];
201	Coordinate p1 = pts[end0];
202
203	//Debug.println("trying:" + p0 + p1 + " [ " + start0 + ", " + end0 + " ]");
204	// terminating condition for the recursion
205	if (end0 - start0 == 1) {
206	//Debug.println("computeSelect:" + p0 + p1);
207	mcs.select(this, start0);
208	return;
209	}
210	// nothing to do if the envelopes don't overlap
211	if (! searchEnv.intersects(p0, p1))
212	return;
213
214	// the chains overlap, so split each in half and iterate (binary search)
215	int mid = (start0 + end0) / 2;
216
217	// Assert: mid != start or end (since we checked above for end - start <= 1)
218	// check terminating conditions before recursing
219	if (start0 < mid) {
220	computeSelect(searchEnv, start0, mid, mcs);
221	}
222	if (mid < end0) {
223	computeSelect(searchEnv, mid, end0, mcs);
224	}
225	}
226
227	/**
228	* Determine all the line segments in two chains which may overlap, and process them.
229	* <p>
230	* The monotone chain search algorithm attempts to optimize
231	* performance by not calling the overlap action on chain segments
232	* which it can determine do not overlap.
233	* However, it may call the overlap action on segments
234	* which do not actually interact.
235	* This saves on the overhead of checking intersection
236	* each time, since clients may be able to do this more efficiently.
237	*
238	* @param searchEnv the search envelope
239	* @param mco the overlap action to execute on selected segments
240	*/
241	public void computeOverlaps(MonotoneChain mc, MonotoneChainOverlapAction mco)
242	{
243	computeOverlaps(start, end, mc, mc.start, mc.end, mco);
244	}
245
246	/**
247	* Uses an efficient mutual binary search strategy
248	* to determine which pairs of chain segments
249	* may overlap, and calls the given overlap action on them.
250	*
251	* @param start0 the start index of this chain section
252	* @param end0 the end index of this chain section
253	* @param mc the target monotone chain
254	* @param start1 the start index of the target chain section
255	* @param end1 the end index of the target chain section
256	* @param mco the overlap action to execute on selected segments
257	*/
258	private void computeOverlaps(
259	int start0, int end0,
260	MonotoneChain mc,
261	int start1, int end1,
262	MonotoneChainOverlapAction mco)
263	{
264	//Debug.println("computeIntersectsForChain:" + p00 + p01 + p10 + p11);
265	// terminating condition for the recursion
266	if (end0 - start0 == 1 && end1 - start1 == 1) {
267	mco.overlap(this, start0, mc, start1);
268	return;
269	}
270	// nothing to do if the envelopes of these subchains don't overlap
271	if (! overlaps(start0, end0, mc, start1, end1)) return;
272
273	// the chains overlap, so split each in half and iterate (binary search)
274	int mid0 = (start0 + end0) / 2;
275	int mid1 = (start1 + end1) / 2;
276
277	// Assert: mid != start or end (since we checked above for end - start <= 1)
278	// check terminating conditions before recursing
279	if (start0 < mid0) {
280	if (start1 < mid1) computeOverlaps(start0, mid0, mc, start1, mid1, mco);
281	if (mid1 < end1) computeOverlaps(start0, mid0, mc, mid1, end1, mco);
282	}
283	if (mid0 < end0) {
284	if (start1 < mid1) computeOverlaps(mid0, end0, mc, start1, mid1, mco);
285	if (mid1 < end1) computeOverlaps(mid0, end0, mc, mid1, end1, mco);
286	}
287	}
288
289	/**
290	* Tests whether the envelope of a section of the chain
291	* overlaps (intersects) the envelope of a section of another target chain.
292	* This test is efficient due to the monotonicity property
293	* of the sections (i.e. the envelopes can be are determined
294	* from the section endpoints
295	* rather than a full scan).
296	*
297	* @param start0 the start index of this chain section
298	* @param end0 the end index of this chain section
299	* @param mc the target monotone chain
300	* @param start1 the start index of the target chain section
301	* @param end1 the end index of the target chain section
302	* @return true if the section envelopes overlap
303	*/
304	private boolean overlaps(
305	int start0, int end0,
306	MonotoneChain mc,
307	int start1, int end1)
308	{
309	return Envelope.intersects(pts[start0], pts[end0], mc.pts[start1], mc.pts[end1]);
310	}
311
312	}
313