Class NodingIntersectionFinder

1	/*
2	* Copyright (c) 2016 Vivid Solutions.
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.noding;
13
14	import java.util.ArrayList;
15	import java.util.List;
16
17	import org.locationtech.jts.algorithm.LineIntersector;
18	import org.locationtech.jts.geom.Coordinate;
19
20
21	/**
22	* Finds non-noded intersections in a set of {@link SegmentString}s,
23	* if any exist.
24	* <p>
25	* Non-noded intersections include:
26	* <ul>
27	* <li><b>Interior intersections</b> which lie in the interior of a segment
28	* (with another segment interior or with a vertex or endpoint)
29	* <li><b>Vertex intersections</b> which occur at vertices in the interior of {@link SegmentString}s
30	* (with a segment string endpoint or with another interior vertex)
31	* </ul>
32	* The finder can be limited to finding only interior intersections
33	* by setting {@link #setInteriorIntersectionsOnly(boolean).
34	* <p>
35	* By default only the first intersection is found,
36	* but all can be found by setting {@link #setFindAllIntersections(boolean)
37	*
38	* @version 1.7
39	*/
40	public class NodingIntersectionFinder
41	implements SegmentIntersector
42	{
43	/**
44	* Creates a finder which tests if there is at least one intersection.
45	* Uses short-circuiting for efficient performance.
46	* The intersection found is recorded.
47	*
48	* @param li a line intersector
49	* @return a finder which tests if there is at least one intersection.
50	*/
51	public static NodingIntersectionFinder createAnyIntersectionFinder(LineIntersector li)
52	{
53	return new NodingIntersectionFinder(li);
54	}
55
56	/**
57	* Creates a finder which finds all intersections.
58	* The intersections are recorded for later inspection.
59	*
60	* @param li a line intersector
61	* @return a finder which finds all intersections.
62	*/
63	public static NodingIntersectionFinder createAllIntersectionsFinder(LineIntersector li)
64	{
65	NodingIntersectionFinder finder = new NodingIntersectionFinder(li);
66	finder.setFindAllIntersections(true);
67	return finder;
68	}
69
70	/**
71	* Creates a finder which finds all interior intersections.
72	* The intersections are recorded for later inspection.
73	*
74	* @param li a line intersector
75	* @return a finder which finds all interior intersections.
76	*/
77	public static NodingIntersectionFinder createInteriorIntersectionsFinder(LineIntersector li)
78	{
79	NodingIntersectionFinder finder = new NodingIntersectionFinder(li);
80	finder.setFindAllIntersections(true);
81	finder.setInteriorIntersectionsOnly(true);
82	return finder;
83	}
84
85	/**
86	* Creates an finder which counts all intersections.
87	* The intersections are note recorded to reduce memory usage.
88	*
89	* @param li a line intersector
90	* @return a finder which counts all intersections.
91	*/
92	public static NodingIntersectionFinder createIntersectionCounter(LineIntersector li)
93	{
94	NodingIntersectionFinder finder = new NodingIntersectionFinder(li);
95	finder.setFindAllIntersections(true);
96	finder.setKeepIntersections(false);
97	return finder;
98	}
99
100	/**
101	* Creates an finder which counts all interior intersections.
102	* The intersections are note recorded to reduce memory usage.
103	*
104	* @param li a line intersector
105	* @return a finder which counts all interior intersections.
106	*/
107	public static NodingIntersectionFinder createInteriorIntersectionCounter(LineIntersector li)
108	{
109	NodingIntersectionFinder finder = new NodingIntersectionFinder(li);
110	finder.setInteriorIntersectionsOnly(true);
111	finder.setFindAllIntersections(true);
112	finder.setKeepIntersections(false);
113	return finder;
114	}
115
116	private boolean findAllIntersections = false;
117	private boolean isCheckEndSegmentsOnly = false;
118	private boolean keepIntersections = true;
119	private boolean isInteriorIntersectionsOnly = false;
120
121	private LineIntersector li;
122	private Coordinate interiorIntersection = null;
123	private Coordinate[] intSegments = null;
124	private List intersections = new ArrayList();
125	private int intersectionCount = 0;
126
127	/**
128	* Creates an intersection finder which finds an intersection
129	* if one exists
130	*
131	* @param li the LineIntersector to use
132	*/
133	public NodingIntersectionFinder(LineIntersector li)
134	{
135	this.li = li;
136	interiorIntersection = null;
137	}
138
139	/**
140	* Sets whether all intersections should be computed.
141	* When this is <code>false</code> (the default value)
142	* the value of {@link #isDone()} is <code>true</code> after the first intersection is found.
143	* <p>
144	* Default is <code>false</code>.
145	*
146	* @param findAllIntersections whether all intersections should be computed
147	*/
148	public void setFindAllIntersections(boolean findAllIntersections)
149	{
150	this.findAllIntersections = findAllIntersections;
151	}
152
153	/**
154	* Sets whether only interior (proper) intersections will be found.
155	* @param isInteriorIntersectionsOnly whether to find only interior intersections
156	*/
157	public void setInteriorIntersectionsOnly(boolean isInteriorIntersectionsOnly)
158	{
159	this.isInteriorIntersectionsOnly = isInteriorIntersectionsOnly;
160	}
161
162	/**
163	* Sets whether only end segments should be tested for intersection.
164	* This is a performance optimization that may be used if
165	* the segments have been previously noded by an appropriate algorithm.
166	* It may be known that any potential noding failures will occur only in
167	* end segments.
168	*
169	* @param isCheckEndSegmentsOnly whether to test only end segments
170	*/
171	public void setCheckEndSegmentsOnly(boolean isCheckEndSegmentsOnly)
172	{
173	this.isCheckEndSegmentsOnly = isCheckEndSegmentsOnly;
174	}
175
176	/**
177	* Sets whether intersection points are recorded.
178	* If the only need is to count intersection points, this can be set to <code>false</code>.
179	* <p>
180	* Default is <code>true</code>.
181	*
182	* @param keepIntersections indicates whether intersections should be recorded
183	*/
184	public void setKeepIntersections(boolean keepIntersections)
185	{
186	this.keepIntersections = keepIntersections;
187	}
188
189	/**
190	* Gets the intersections found.
191	*
192	* @return a List of {@link Coordinate}
193	*/
194	public List getIntersections()
195	{
196	return intersections;
197	}
198
199	/**
200	* Gets the count of intersections found.
201	*
202	* @return the intersection count
203	*/
204	public int count()
205	{
206	return intersectionCount;
207	}
208
209	/**
210	* Tests whether an intersection was found.
211	*
212	* @return true if an intersection was found
213	*/
214	public boolean hasIntersection()
215	{
216	return interiorIntersection != null;
217	}
218
219	/**
220	* Gets the computed location of the intersection.
221	* Due to round-off, the location may not be exact.
222	*
223	* @return the coordinate for the intersection location
224	*/
225	public Coordinate getIntersection()
226	{
227	return interiorIntersection;
228	}
229
230	/**
231	* Gets the endpoints of the intersecting segments.
232	*
233	* @return an array of the segment endpoints (p00, p01, p10, p11)
234	*/
235	public Coordinate[] getIntersectionSegments()
236	{
237	return intSegments;
238	}
239
240	/**
241	* This method is called by clients
242	* of the {@link SegmentIntersector} class to process
243	* intersections for two segments of the {@link SegmentString}s being intersected.
244	* Note that some clients (such as <code>MonotoneChain</code>s) may optimize away
245	* this call for segment pairs which they have determined do not intersect
246	* (e.g. by an disjoint envelope test).
247	*/
248	public void processIntersections(
249	SegmentString e0, int segIndex0,
250	SegmentString e1, int segIndex1
251	)
252	{
253	// short-circuit if intersection already found
254	if (! findAllIntersections && hasIntersection())
255	return;
256
257	// don't bother intersecting a segment with itself
258	boolean isSameSegString = e0 == e1;
259	boolean isSameSegment = isSameSegString && segIndex0 == segIndex1;
260	if (isSameSegment) return;
261
262	/**
263	* If enabled, only test end segments (on either segString).
264	*
265	*/
266	if (isCheckEndSegmentsOnly) {
267	boolean isEndSegPresent = isEndSegment(e0, segIndex0) \|\| isEndSegment(e1, segIndex1);
268	if (! isEndSegPresent)
269	return;
270	}
271
272	Coordinate p00 = e0.getCoordinate(segIndex0);
273	Coordinate p01 = e0.getCoordinate(segIndex0 + 1);
274	Coordinate p10 = e1.getCoordinate(segIndex1);
275	Coordinate p11 = e1.getCoordinate(segIndex1 + 1);
276	boolean isEnd00 = segIndex0 == 0;
277	boolean isEnd01 = segIndex0 + 2 == e0.size();
278	boolean isEnd10 = segIndex1 == 0;
279	boolean isEnd11 = segIndex1 + 2 == e1.size();
280
281	li.computeIntersection(p00, p01, p10, p11);
282	//if (li.hasIntersection() && li.isProper()) Debug.println(li);
283
284	/**
285	* Check for an intersection in the interior of a segment
286	*/
287	boolean isInteriorInt = li.hasIntersection() && li.isInteriorIntersection();
288	/**
289	* Check for an intersection between two vertices which are not both endpoints.
290	*/
291	boolean isInteriorVertexInt = false;
292	if (! isInteriorIntersectionsOnly) {
293	boolean isAdjacentSegment = isSameSegString && Math.abs(segIndex1 - segIndex0) <= 1;
294	isInteriorVertexInt = (! isAdjacentSegment) && isInteriorVertexIntersection(p00, p01, p10, p11,
295	isEnd00, isEnd01, isEnd10, isEnd11);
296	}
297
298	if (isInteriorInt \|\| isInteriorVertexInt) {
299	// found an intersection!
300	intSegments = new Coordinate[4];
301	intSegments[0] = p00;
302	intSegments[1] = p01;
303	intSegments[2] = p10;
304	intSegments[3] = p11;
305
306	//TODO: record endpoint intersection(s)
307	interiorIntersection = li.getIntersection(0);
308	if (keepIntersections) intersections.add(interiorIntersection);
309	intersectionCount++;
310	}
311	}
312
313	/**
314	* Tests if an intersection occurs between a segmentString interior vertex and another vertex.
315	* Note that intersections between two endpoint vertices are valid noding,
316	* and are not flagged.
317	*
318	* @param p00 a segment vertex
319	* @param p01 a segment vertex
320	* @param p10 a segment vertex
321	* @param p11 a segment vertex
322	* @param isEnd00 true if vertex is a segmentString endpoint
323	* @param isEnd01 true if vertex is a segmentString endpoint
324	* @param isEnd10 true if vertex is a segmentString endpoint
325	* @param isEnd11 true if vertex is a segmentString endpoint
326	* @return true if an intersection is found
327	*/
328	private static boolean isInteriorVertexIntersection(
329	Coordinate p00, Coordinate p01,
330	Coordinate p10, Coordinate p11,
331	boolean isEnd00, boolean isEnd01,
332	boolean isEnd10, boolean isEnd11) {
333	if (isInteriorVertexIntersection(p00, p10, isEnd00, isEnd10)) return true;
334	if (isInteriorVertexIntersection(p00, p11, isEnd00, isEnd11)) return true;
335	if (isInteriorVertexIntersection(p01, p10, isEnd01, isEnd10)) return true;
336	if (isInteriorVertexIntersection(p01, p11, isEnd01, isEnd11)) return true;
337	return false;
338	}
339
340	/**
341	* Tests if two vertices with at least one in a segmentString interior
342	* are equal.
343	*
344	* @param p0 a segment vertex
345	* @param p1 a segment vertex
346	* @param isEnd0 true if vertex is a segmentString endpoint
347	* @param isEnd1 true if vertex is a segmentString endpoint
348	* @return true if an intersection is found
349	*/
350	private static boolean isInteriorVertexIntersection(
351	Coordinate p0, Coordinate p1,
352	boolean isEnd0, boolean isEnd1) {
353
354	// Intersections between endpoints are valid nodes, so not reported
355	if (isEnd0 && isEnd1) return false;
356
357	if (p0.equals2D(p1)) {
358	return true;
359	}
360	return false;
361	}
362
363	/**
364	* Tests whether a segment in a {@link SegmentString} is an end segment.
365	* (either the first or last).
366	*
367	* @param segStr a segment string
368	* @param index the index of a segment in the segment string
369	* @return true if the segment is an end segment
370	*/
371	private static boolean isEndSegment(SegmentString segStr, int index)
372	{
373	if (index == 0) return true;
374	if (index >= segStr.size() - 2) return true;
375	return false;
376	}
377
378	/**
379	*
380	*/
381	public boolean isDone()
382	{
383	if (findAllIntersections) return false;
384	return interiorIntersection != null;
385	}
386
387	}
388