Class LineIntersector

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.algorithm;
13
14	/**
15	* @version 1.7
16	*/
17	import org.locationtech.jts.geom.Coordinate;
18	import org.locationtech.jts.geom.PrecisionModel;
19	import org.locationtech.jts.io.WKTWriter;
20	import org.locationtech.jts.util.Assert;
21
22	/**
23	* A <code>LineIntersector</code> is an algorithm that can both test whether
24	* two line segments intersect and compute the intersection point(s)
25	* if they do.
26	* <p>
27	* There are three possible outcomes when determining whether two line segments intersect:
28	* <ul>
29	* <li>{@link #NO_INTERSECTION} - the segments do not intersect
30	* <li>{@link #POINT_INTERSECTION} - the segments intersect in a single point
31	* <li>{@link #COLLINEAR_INTERSECTION} - the segments are collinear and they intersect in a line segment
32	* </ul>
33	* For segments which intersect in a single point, the point may be either an endpoint
34	* or in the interior of each segment.
35	* If the point lies in the interior of both segments,
36	* this is termed a <i>proper intersection</i>.
37	* The method {@link #isProper()} test for this situation.
38	* <p>
39	* The intersection point(s) may be computed in a precise or non-precise manner.
40	* Computing an intersection point precisely involves rounding it
41	* via a supplied {@link PrecisionModel}.
42	* <p>
43	* LineIntersectors do not perform an initial envelope intersection test
44	* to determine if the segments are disjoint.
45	* This is because this class is likely to be used in a context where
46	* envelope overlap is already known to occur (or be likely).
47	*
48	* @version 1.7
49	*/
50	public abstract class LineIntersector
51	{
52	/**
53	* These are deprecated, due to ambiguous naming
54	*/
55	public final static int DONT_INTERSECT = 0;
56	public final static int DO_INTERSECT = 1;
57	public final static int COLLINEAR = 2;
58
59	/**
60	* Indicates that line segments do not intersect
61	*/
62	public final static int NO_INTERSECTION = 0;
63
64	/**
65	* Indicates that line segments intersect in a single point
66	*/
67	public final static int POINT_INTERSECTION = 1;
68
69	/**
70	* Indicates that line segments intersect in a line segment
71	*/
72	public final static int COLLINEAR_INTERSECTION = 2;
73
74	/**
75	* Computes the "edge distance" of an intersection point p along a segment.
76	* The edge distance is a metric of the point along the edge.
77	* The metric used is a robust and easy to compute metric function.
78	* It is <b>not</b> equivalent to the usual Euclidean metric.
79	* It relies on the fact that either the x or the y ordinates of the
80	* points in the edge are unique, depending on whether the edge is longer in
81	* the horizontal or vertical direction.
82	* <p>
83	* NOTE: This function may produce incorrect distances
84	* for inputs where p is not precisely on p1-p2
85	* (E.g. p = (139,9) p1 = (139,10), p2 = (280,1) produces distance 0.0, which is incorrect.
86	* <p>
87	* My hypothesis is that the function is safe to use for points which are the
88	* result of <b>rounding</b> points which lie on the line,
89	* but not safe to use for <b>truncated</b> points.
90	*/
91	public static double computeEdgeDistance(
92	Coordinate p,
93	Coordinate p0,
94	Coordinate p1)
95	{
96	double dx = Math.abs(p1.x - p0.x);
97	double dy = Math.abs(p1.y - p0.y);
98
99	double dist = -1.0; // sentinel value
100	if (p.equals(p0)) {
101	dist = 0.0;
102	}
103	else if (p.equals(p1)) {
104	if (dx > dy)
105	dist = dx;
106	else
107	dist = dy;
108	}
109	else {
110	double pdx = Math.abs(p.x - p0.x);
111	double pdy = Math.abs(p.y - p0.y);
112	if (dx > dy)
113	dist = pdx;
114	else
115	dist = pdy;
116	// <FIX>
117	// hack to ensure that non-endpoints always have a non-zero distance
118	if (dist == 0.0 && ! p.equals(p0))
119	{
120	dist = Math.max(pdx, pdy);
121	}
122	}
123	Assert.isTrue(! (dist == 0.0 && ! p.equals(p0)), "Bad distance calculation");
124	return dist;
125	}
126
127	/**
128	* This function is non-robust, since it may compute the square of large numbers.
129	* Currently not sure how to improve this.
130	*/
131	public static double nonRobustComputeEdgeDistance(
132	Coordinate p,
133	Coordinate p1,
134	Coordinate p2)
135	{
136	double dx = p.x - p1.x;
137	double dy = p.y - p1.y;
138	double dist = Math.sqrt(dx * dx + dy * dy); // dummy value
139	Assert.isTrue(! (dist == 0.0 && ! p.equals(p1)), "Invalid distance calculation");
140	return dist;
141	}
142
143	protected int result;
144	protected Coordinate[][] inputLines = new Coordinate[2][2];
145	protected Coordinate[] intPt = new Coordinate[2];
146	/**
147	* The indexes of the endpoints of the intersection lines, in order along
148	* the corresponding line
149	*/
150	protected int[][] intLineIndex;
151	protected boolean isProper;
152	protected Coordinate pa;
153	protected Coordinate pb;
154	/**
155	* If makePrecise is true, computed intersection coordinates will be made precise
156	* using Coordinate#makePrecise
157	*/
158	protected PrecisionModel precisionModel = null;
159	//public int numIntersects = 0;
160
161	public LineIntersector() {
162	intPt[0] = new Coordinate();
163	intPt[1] = new Coordinate();
164	// alias the intersection points for ease of reference
165	pa = intPt[0];
166	pb = intPt[1];
167	result = 0;
168	}
169
170	/**
171	* Force computed intersection to be rounded to a given precision model
172	* @param precisionModel
173	* @deprecated use <code>setPrecisionModel</code> instead
174	*/
175	public void setMakePrecise(PrecisionModel precisionModel)
176	{
177	this.precisionModel = precisionModel;
178	}
179
180	/**
181	* Force computed intersection to be rounded to a given precision model.
182	* No getter is provided, because the precision model is not required to be specified.
183	* @param precisionModel
184	*/
185	public void setPrecisionModel(PrecisionModel precisionModel)
186	{
187	this.precisionModel = precisionModel;
188	}
189
190	/**
191	* Gets an endpoint of an input segment.
192	*
193	* @param segmentIndex the index of the input segment (0 or 1)
194	* @param ptIndex the index of the endpoint (0 or 1)
195	* @return the specified endpoint
196	*/
197	public Coordinate getEndpoint(int segmentIndex, int ptIndex)
198	{
199	return inputLines[segmentIndex][ptIndex];
200	}
201
202	/**
203	* Compute the intersection of a point p and the line p1-p2.
204	* This function computes the boolean value of the hasIntersection test.
205	* The actual value of the intersection (if there is one)
206	* is equal to the value of <code>p</code>.
207	*/
208	public abstract void computeIntersection(
209	Coordinate p,
210	Coordinate p1, Coordinate p2);
211
212	protected boolean isCollinear() {
213	return result == COLLINEAR_INTERSECTION;
214	}
215
216	/**
217	* Computes the intersection of the lines p1-p2 and p3-p4.
218	* This function computes both the boolean value of the hasIntersection test
219	* and the (approximate) value of the intersection point itself (if there is one).
220	*/
221	public void computeIntersection(
222	Coordinate p1, Coordinate p2,
223	Coordinate p3, Coordinate p4) {
224	inputLines[0][0] = p1;
225	inputLines[0][1] = p2;
226	inputLines[1][0] = p3;
227	inputLines[1][1] = p4;
228	result = computeIntersect(p1, p2, p3, p4);
229	//numIntersects++;
230	}
231
232	protected abstract int computeIntersect(
233	Coordinate p1, Coordinate p2,
234	Coordinate q1, Coordinate q2);
235
236	/*
237	public String toString() {
238	String str = inputLines[0][0] + "-"
239	+ inputLines[0][1] + " "
240	+ inputLines[1][0] + "-"
241	+ inputLines[1][1] + " : "
242	+ getTopologySummary();
243	return str;
244	}
245	*/
246
247	public String toString() {
248	return WKTWriter.toLineString(inputLines[0][0], inputLines[0][1]) + " - "
249	+ WKTWriter.toLineString(inputLines[1][0], inputLines[1][1])
250	+ getTopologySummary();
251	}
252
253	private String getTopologySummary()
254	{
255	StringBuilder catBuilder = new StringBuilder();
256	if (isEndPoint()) catBuilder.append(" endpoint");
257	if (isProper) catBuilder.append(" proper");
258	if (isCollinear()) catBuilder.append(" collinear");
259	return catBuilder.toString();
260	}
261
262	protected boolean isEndPoint() {
263	return hasIntersection() && !isProper;
264	}
265
266	/**
267	* Tests whether the input geometries intersect.
268	*
269	* @return true if the input geometries intersect
270	*/
271	public boolean hasIntersection() {
272	return result != NO_INTERSECTION;
273	}
274
275	/**
276	* Returns the number of intersection points found. This will be either 0, 1 or 2.
277	*
278	* @return the number of intersection points found (0, 1, or 2)
279	*/
280	public int getIntersectionNum() { return result; }
281
282	/**
283	* Returns the intIndex'th intersection point
284	*
285	* @param intIndex is 0 or 1
286	*
287	* @return the intIndex'th intersection point
288	*/
289	public Coordinate getIntersection(int intIndex) { return intPt[intIndex]; }
290
291	protected void computeIntLineIndex() {
292	if (intLineIndex == null) {
293	intLineIndex = new int[2][2];
294	computeIntLineIndex(0);
295	computeIntLineIndex(1);
296	}
297	}
298
299	/**
300	* Test whether a point is a intersection point of two line segments.
301	* Note that if the intersection is a line segment, this method only tests for
302	* equality with the endpoints of the intersection segment.
303	* It does <b>not</b> return true if
304	* the input point is internal to the intersection segment.
305	*
306	* @return true if the input point is one of the intersection points.
307	*/
308	public boolean isIntersection(Coordinate pt) {
309	for (int i = 0; i < result; i++) {
310	if (intPt[i].equals2D(pt)) {
311	return true;
312	}
313	}
314	return false;
315	}
316
317	/**
318	* Tests whether either intersection point is an interior point of one of the input segments.
319	*
320	* @return <code>true</code> if either intersection point is in the interior of one of the input segments
321	*/
322	public boolean isInteriorIntersection()
323	{
324	if (isInteriorIntersection(0)) return true;
325	if (isInteriorIntersection(1)) return true;
326	return false;
327	}
328
329	/**
330	* Tests whether either intersection point is an interior point of the specified input segment.
331	*
332	* @return <code>true</code> if either intersection point is in the interior of the input segment
333	*/
334	public boolean isInteriorIntersection(int inputLineIndex)
335	{
336	for (int i = 0; i < result; i++) {
337	if (! ( intPt[i].equals2D(inputLines[inputLineIndex][0])
338	\|\| intPt[i].equals2D(inputLines[inputLineIndex][1]) )) {
339	return true;
340	}
341	}
342	return false;
343	}
344
345	/**
346	* Tests whether an intersection is proper.
347	* <br>
348	* The intersection between two line segments is considered proper if
349	* they intersect in a single point in the interior of both segments
350	* (e.g. the intersection is a single point and is not equal to any of the
351	* endpoints).
352	* <p>
353	* The intersection between a point and a line segment is considered proper
354	* if the point lies in the interior of the segment (e.g. is not equal to
355	* either of the endpoints).
356	*
357	* @return true if the intersection is proper
358	*/
359	public boolean isProper() {
360	return hasIntersection() && isProper;
361	}
362
363	/**
364	* Computes the intIndex'th intersection point in the direction of
365	* a specified input line segment
366	*
367	* @param segmentIndex is 0 or 1
368	* @param intIndex is 0 or 1
369	*
370	* @return the intIndex'th intersection point in the direction of the specified input line segment
371	*/
372	public Coordinate getIntersectionAlongSegment(int segmentIndex, int intIndex) {
373	// lazily compute int line array
374	computeIntLineIndex();
375	return intPt[intLineIndex[segmentIndex][intIndex]];
376	}
377
378	/**
379	* Computes the index (order) of the intIndex'th intersection point in the direction of
380	* a specified input line segment
381	*
382	* @param segmentIndex is 0 or 1
383	* @param intIndex is 0 or 1
384	*
385	* @return the index of the intersection point along the input segment (0 or 1)
386	*/
387	public int getIndexAlongSegment(int segmentIndex, int intIndex) {
388	computeIntLineIndex();
389	return intLineIndex[segmentIndex][intIndex];
390	}
391
392	protected void computeIntLineIndex(int segmentIndex) {
393	double dist0 = getEdgeDistance(segmentIndex, 0);
394	double dist1 = getEdgeDistance(segmentIndex, 1);
395	if (dist0 > dist1) {
396	intLineIndex[segmentIndex][0] = 0;
397	intLineIndex[segmentIndex][1] = 1;
398	}
399	else {
400	intLineIndex[segmentIndex][0] = 1;
401	intLineIndex[segmentIndex][1] = 0;
402	}
403	}
404
405	/**
406	* Computes the "edge distance" of an intersection point along the specified input line segment.
407	*
408	* @param segmentIndex is 0 or 1
409	* @param intIndex is 0 or 1
410	*
411	* @return the edge distance of the intersection point
412	*/
413	public double getEdgeDistance(int segmentIndex, int intIndex) {
414	double dist = computeEdgeDistance(intPt[intIndex], inputLines[segmentIndex][0],
415	inputLines[segmentIndex][1]);
416	return dist;
417	}
418	}
419