Class LineSegment

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.geom;
15
16	import java.io.Serializable;
17
18	import org.locationtech.jts.algorithm.Distance;
19	import org.locationtech.jts.algorithm.Intersection;
20	import org.locationtech.jts.algorithm.LineIntersector;
21	import org.locationtech.jts.algorithm.Orientation;
22	import org.locationtech.jts.algorithm.RobustLineIntersector;
23
24
25	/**
26	* Represents a line segment defined by two {@link Coordinate}s.
27	* Provides methods to compute various geometric properties
28	* and relationships of line segments.
29	* <p>
30	* This class is designed to be easily mutable (to the extent of
31	* having its contained points public).
32	* This supports a common pattern of reusing a single LineSegment
33	* object as a way of computing segment properties on the
34	* segments defined by arrays or lists of {@link Coordinate}s.
35	*
36	*@version 1.7
37	*/
38	public class LineSegment
39	implements Comparable, Serializable
40	{
41	private static final long serialVersionUID = 3252005833466256227L;
42
43	public Coordinate p0, p1;
44
45	public LineSegment(Coordinate p0, Coordinate p1) {
46	this.p0 = p0;
47	this.p1 = p1;
48	}
49
50	public LineSegment(double x0, double y0, double x1, double y1) {
51	this(new Coordinate(x0, y0), new Coordinate(x1, y1));
52	}
53
54	public LineSegment(LineSegment ls) {
55	this(ls.p0, ls.p1);
56	}
57
58	public LineSegment() {
59	this(new Coordinate(), new Coordinate());
60	}
61
62	public Coordinate getCoordinate(int i)
63	{
64	if (i == 0) return p0;
65	return p1;
66	}
67
68	public void setCoordinates(LineSegment ls)
69	{
70	setCoordinates(ls.p0, ls.p1);
71	}
72
73	public void setCoordinates(Coordinate p0, Coordinate p1)
74	{
75	this.p0.x = p0.x;
76	this.p0.y = p0.y;
77	this.p1.x = p1.x;
78	this.p1.y = p1.y;
79	}
80
81	/**
82	* Gets the minimum X ordinate.
83	* @return the minimum X ordinate
84	*/
85	public double minX() {
86	return Math.min(p0.x, p1.x);
87	}
88
89	/**
90	* Gets the maximum X ordinate.
91	* @return the maximum X ordinate
92	*/
93	public double maxX() {
94	return Math.max(p0.x, p1.x);
95	}
96
97	/**
98	* Gets the minimum Y ordinate.
99	* @return the minimum Y ordinate
100	*/
101	public double minY() {
102	return Math.min(p0.y, p1.y);
103	}
104
105	/**
106	* Gets the maximum Y ordinate.
107	* @return the maximum Y ordinate
108	*/
109	public double maxY() {
110	return Math.max(p0.y, p1.y);
111	}
112
113	/**
114	* Computes the length of the line segment.
115	* @return the length of the line segment
116	*/
117	public double getLength()
118	{
119	return p0.distance(p1);
120	}
121
122	/**
123	* Tests whether the segment is horizontal.
124	*
125	* @return <code>true</code> if the segment is horizontal
126	*/
127	public boolean isHorizontal() { return p0.y == p1.y; }
128
129	/**
130	* Tests whether the segment is vertical.
131	*
132	* @return <code>true</code> if the segment is vertical
133	*/
134	public boolean isVertical() { return p0.x == p1.x; }
135
136	/**
137	* Determines the orientation of a LineSegment relative to this segment.
138	* The concept of orientation is specified as follows:
139	* Given two line segments A and L,
140	* <ul>
141	* <li>A is to the left of a segment L if A lies wholly in the
142	* closed half-plane lying to the left of L
143	* <li>A is to the right of a segment L if A lies wholly in the
144	* closed half-plane lying to the right of L
145	* <li>otherwise, A has indeterminate orientation relative to L. This
146	* happens if A is collinear with L or if A crosses the line determined by L.
147	* </ul>
148	*
149	* @param seg the LineSegment to compare
150	*
151	* @return 1 if <code>seg</code> is to the left of this segment
152	* @return -1 if <code>seg</code> is to the right of this segment
153	* @return 0 if <code>seg</code> is collinear to or crosses this segment
154	*/
155	public int orientationIndex(LineSegment seg)
156	{
157	int orient0 = Orientation.index(p0, p1, seg.p0);
158	int orient1 = Orientation.index(p0, p1, seg.p1);
159	// this handles the case where the points are L or collinear
160	if (orient0 >= 0 && orient1 >= 0)
161	return Math.max(orient0, orient1);
162	// this handles the case where the points are R or collinear
163	if (orient0 <= 0 && orient1 <= 0)
164	return Math.max(orient0, orient1);
165	// points lie on opposite sides ==> indeterminate orientation
166	return 0;
167	}
168
169	/**
170	* Determines the orientation index of a {@link Coordinate} relative to this segment.
171	* The orientation index is as defined in {@link Orientation#computeOrientation}.
172	*
173	* @param p the coordinate to compare
174	*
175	* @return 1 (LEFT) if <code>p</code> is to the left of this segment
176	* @return -1 (RIGHT) if <code>p</code> is to the right of this segment
177	* @return 0 (COLLINEAR) if <code>p</code> is collinear with this segment
178	*
179	* @see Orientation#computeOrientation(Coordinate, Coordinate, Coordinate)
180	*/
181	public int orientationIndex(Coordinate p)
182	{
183	return Orientation.index(p0, p1, p);
184	}
185
186	/**
187	* Reverses the direction of the line segment.
188	*/
189	public void reverse()
190	{
191	Coordinate temp = p0;
192	p0 = p1;
193	p1 = temp;
194	}
195
196	/**
197	* Puts the line segment into a normalized form.
198	* This is useful for using line segments in maps and indexes when
199	* topological equality rather than exact equality is desired.
200	* A segment in normalized form has the first point smaller
201	* than the second (according to the standard ordering on {@link Coordinate}).
202	*/
203	public void normalize()
204	{
205	if (p1.compareTo(p0) < 0) reverse();
206	}
207
208	/**
209	* Computes the angle that the vector defined by this segment
210	* makes with the X-axis.
211	* The angle will be in the range [ -PI, PI ] radians.
212	*
213	* @return the angle this segment makes with the X-axis (in radians)
214	*/
215	public double angle()
216	{
217	return Math.atan2(p1.y - p0.y, p1.x - p0.x);
218	}
219
220	/**
221	* Computes the midpoint of the segment
222	*
223	* @return the midpoint of the segment
224	*/
225	public Coordinate midPoint()
226	{
227	return midPoint(p0, p1);
228	}
229
230	/**
231	* Computes the midpoint of a segment
232	*
233	* @return the midpoint of the segment
234	*/
235	public static Coordinate midPoint(Coordinate p0, Coordinate p1)
236	{
237	return new Coordinate( (p0.x + p1.x) / 2,
238	(p0.y + p1.y) / 2);
239	}
240
241	/**
242	* Computes the distance between this line segment and another segment.
243	*
244	* @return the distance to the other segment
245	*/
246	public double distance(LineSegment ls)
247	{
248	return Distance.segmentToSegment(p0, p1, ls.p0, ls.p1);
249	}
250
251	/**
252	* Computes the distance between this line segment and a given point.
253	*
254	* @return the distance from this segment to the given point
255	*/
256	public double distance(Coordinate p)
257	{
258	return Distance.pointToSegment(p, p0, p1);
259	}
260
261	/**
262	* Computes the perpendicular distance between the (infinite) line defined
263	* by this line segment and a point.
264	*
265	* @return the perpendicular distance between the defined line and the given point
266	*/
267	public double distancePerpendicular(Coordinate p)
268	{
269	return Distance.pointToLinePerpendicular(p, p0, p1);
270	}
271
272	/**
273	* Computes the {@link Coordinate} that lies a given
274	* fraction along the line defined by this segment.
275	* A fraction of <code>0.0</code> returns the start point of the segment;
276	* a fraction of <code>1.0</code> returns the end point of the segment.
277	* If the fraction is < 0.0 or > 1.0 the point returned
278	* will lie before the start or beyond the end of the segment.
279	*
280	* @param segmentLengthFraction the fraction of the segment length along the line
281	* @return the point at that distance
282	*/
283	public Coordinate pointAlong(double segmentLengthFraction)
284	{
285	Coordinate coord = new Coordinate();
286	coord.x = p0.x + segmentLengthFraction * (p1.x - p0.x);
287	coord.y = p0.y + segmentLengthFraction * (p1.y - p0.y);
288	return coord;
289	}
290
291	/**
292	* Computes the {@link Coordinate} that lies a given
293	* fraction along the line defined by this segment and offset from
294	* the segment by a given distance.
295	* A fraction of <code>0.0</code> offsets from the start point of the segment;
296	* a fraction of <code>1.0</code> offsets from the end point of the segment.
297	* The computed point is offset to the left of the line if the offset distance is
298	* positive, to the right if negative.
299	*
300	* @param segmentLengthFraction the fraction of the segment length along the line
301	* @param offsetDistance the distance the point is offset from the segment
302	* (positive is to the left, negative is to the right)
303	* @return the point at that distance and offset
304	*
305	* @throws IllegalStateException if the segment has zero length
306	*/
307	public Coordinate pointAlongOffset(double segmentLengthFraction, double offsetDistance)
308	{
309	// the point on the segment line
310	double segx = p0.x + segmentLengthFraction * (p1.x - p0.x);
311	double segy = p0.y + segmentLengthFraction * (p1.y - p0.y);
312
313	double dx = p1.x - p0.x;
314	double dy = p1.y - p0.y;
315	double len = Math.sqrt(dx * dx + dy * dy);
316	double ux = 0.0;
317	double uy = 0.0;
318	if (offsetDistance != 0.0) {
319	if (len <= 0.0)
320	throw new IllegalStateException("Cannot compute offset from zero-length line segment");
321
322	// u is the vector that is the length of the offset, in the direction of the segment
323	ux = offsetDistance * dx / len;
324	uy = offsetDistance * dy / len;
325	}
326
327	// the offset point is the seg point plus the offset vector rotated 90 degrees CCW
328	double offsetx = segx - uy;
329	double offsety = segy + ux;
330
331	Coordinate coord = new Coordinate(offsetx, offsety);
332	return coord;
333	}
334
335	/**
336	* Computes the Projection Factor for the projection of the point p
337	* onto this LineSegment. The Projection Factor is the constant r
338	* by which the vector for this segment must be multiplied to
339	* equal the vector for the projection of <tt>p</tt> on the line
340	* defined by this segment.
341	* <p>
342	* The projection factor will lie in the range <tt>(-inf, +inf)</tt>,
343	* or be <code>NaN</code> if the line segment has zero length..
344	*
345	* @param p the point to compute the factor for
346	* @return the projection factor for the point
347	*/
348	public double projectionFactor(Coordinate p)
349	{
350	if (p.equals(p0)) return 0.0;
351	if (p.equals(p1)) return 1.0;
352	// Otherwise, use comp.graphics.algorithms Frequently Asked Questions method
353	/* AC dot AB
354	r = ---------
355	\|\|AB\|\|^2
356	r has the following meaning:
357	r=0 P = A
358	r=1 P = B
359	r<0 P is on the backward extension of AB
360	r>1 P is on the forward extension of AB
361	0<r<1 P is interior to AB
362	*/
363	double dx = p1.x - p0.x;
364	double dy = p1.y - p0.y;
365	double len = dx * dx + dy * dy;
366
367	// handle zero-length segments
368	if (len <= 0.0) return Double.NaN;
369
370	double r = ( (p.x - p0.x) * dx + (p.y - p0.y) * dy )
371	/ len;
372	return r;
373	}
374
375	/**
376	* Computes the fraction of distance (in <tt>[0.0, 1.0]</tt>)
377	* that the projection of a point occurs along this line segment.
378	* If the point is beyond either ends of the line segment,
379	* the closest fractional value (<tt>0.0</tt> or <tt>1.0</tt>) is returned.
380	* <p>
381	* Essentially, this is the {@link #projectionFactor} clamped to
382	* the range <tt>[0.0, 1.0]</tt>.
383	* If the segment has zero length, 1.0 is returned.
384	*
385	* @param inputPt the point
386	* @return the fraction along the line segment the projection of the point occurs
387	*/
388	public double segmentFraction(
389	Coordinate inputPt)
390	{
391	double segFrac = projectionFactor(inputPt);
392	if (segFrac < 0.0)
393	segFrac = 0.0;
394	else if (segFrac > 1.0 \|\| Double.isNaN(segFrac))
395	segFrac = 1.0;
396	return segFrac;
397	}
398
399	/**
400	* Compute the projection of a point onto the line determined
401	* by this line segment.
402	* <p>
403	* Note that the projected point
404	* may lie outside the line segment. If this is the case,
405	* the projection factor will lie outside the range [0.0, 1.0].
406	*/
407	public Coordinate project(Coordinate p)
408	{
409	if (p.equals(p0) \|\| p.equals(p1)) return new Coordinate(p);
410
411	double r = projectionFactor(p);
412	Coordinate coord = new Coordinate();
413	coord.x = p0.x + r * (p1.x - p0.x);
414	coord.y = p0.y + r * (p1.y - p0.y);
415	return coord;
416	}
417	/**
418	* Project a line segment onto this line segment and return the resulting
419	* line segment. The returned line segment will be a subset of
420	* the target line line segment. This subset may be null, if
421	* the segments are oriented in such a way that there is no projection.
422	* <p>
423	* Note that the returned line may have zero length (i.e. the same endpoints).
424	* This can happen for instance if the lines are perpendicular to one another.
425	*
426	* @param seg the line segment to project
427	* @return the projected line segment, or <code>null</code> if there is no overlap
428	*/
429	public LineSegment project(LineSegment seg)
430	{
431	double pf0 = projectionFactor(seg.p0);
432	double pf1 = projectionFactor(seg.p1);
433	// check if segment projects at all
434	if (pf0 >= 1.0 && pf1 >= 1.0) return null;
435	if (pf0 <= 0.0 && pf1 <= 0.0) return null;
436
437	Coordinate newp0 = project(seg.p0);
438	if (pf0 < 0.0) newp0 = p0;
439	if (pf0 > 1.0) newp0 = p1;
440
441	Coordinate newp1 = project(seg.p1);
442	if (pf1 < 0.0) newp1 = p0;
443	if (pf1 > 1.0) newp1 = p1;
444
445	return new LineSegment(newp0, newp1);
446	}
447
448	/**
449	* Computes the reflection of a point in the line defined
450	* by this line segment.
451	*
452	* @param p the point to reflect
453	* @return the reflected point
454	*/
455	public Coordinate reflect(Coordinate p) {
456	// general line equation
457	double A = p1.getY() - p0.getY();
458	double B = p0.getX() - p1.getX();
459	double C = p0.getY() * (p1.getX() - p0.getX()) - p0.getX()*( p1.getY() - p0.getY() );
460
461	// compute reflected point
462	double A2plusB2 = AA + BB;
463	double A2subB2 = AA - BB;
464
465	double x = p.getX();
466	double y = p.getY();
467	double rx = ( -A2subB2x - 2ABy - 2AC ) / A2plusB2;
468	double ry = ( A2subB2y - 2ABx - 2BC ) / A2plusB2;
469
470	return new Coordinate(rx, ry);
471	}
472
473	/**
474	* Computes the closest point on this line segment to another point.
475	* @param p the point to find the closest point to
476	* @return a Coordinate which is the closest point on the line segment to the point p
477	*/
478	public Coordinate closestPoint(Coordinate p)
479	{
480	double factor = projectionFactor(p);
481	if (factor > 0 && factor < 1) {
482	return project(p);
483	}
484	double dist0 = p0.distance(p);
485	double dist1 = p1.distance(p);
486	if (dist0 < dist1)
487	return p0;
488	return p1;
489	}
490	/**
491	* Computes the closest points on two line segments.
492	*
493	* @param line the segment to find the closest point to
494	* @return a pair of Coordinates which are the closest points on the line segments
495	*/
496	public Coordinate[] closestPoints(LineSegment line)
497	{
498	// test for intersection
499	Coordinate intPt = intersection(line);
500	if (intPt != null) {
501	return new Coordinate[] { intPt, intPt };
502	}
503
504	/**
505	* if no intersection closest pair contains at least one endpoint.
506	* Test each endpoint in turn.
507	*/
508	Coordinate[] closestPt = new Coordinate[2];
509	double minDistance = Double.MAX_VALUE;
510	double dist;
511
512	Coordinate close00 = closestPoint(line.p0);
513	minDistance = close00.distance(line.p0);
514	closestPt[0] = close00;
515	closestPt[1] = line.p0;
516
517	Coordinate close01 = closestPoint(line.p1);
518	dist = close01.distance(line.p1);
519	if (dist < minDistance) {
520	minDistance = dist;
521	closestPt[0] = close01;
522	closestPt[1] = line.p1;
523	}
524
525	Coordinate close10 = line.closestPoint(p0);
526	dist = close10.distance(p0);
527	if (dist < minDistance) {
528	minDistance = dist;
529	closestPt[0] = p0;
530	closestPt[1] = close10;
531	}
532
533	Coordinate close11 = line.closestPoint(p1);
534	dist = close11.distance(p1);
535	if (dist < minDistance) {
536	minDistance = dist;
537	closestPt[0] = p1;
538	closestPt[1] = close11;
539	}
540
541	return closestPt;
542	}
543
544	/**
545	* Computes an intersection point between two line segments, if there is one.
546	* There may be 0, 1 or many intersection points between two segments.
547	* If there are 0, null is returned. If there is 1 or more,
548	* exactly one of them is returned
549	* (chosen at the discretion of the algorithm).
550	* If more information is required about the details of the intersection,
551	* the {@link RobustLineIntersector} class should be used.
552	*
553	* @param line a line segment
554	* @return an intersection point, or <code>null</code> if there is none
555	*
556	* @see RobustLineIntersector
557	*/
558	public Coordinate intersection(LineSegment line)
559	{
560	LineIntersector li = new RobustLineIntersector();
561	li.computeIntersection(p0, p1, line.p0, line.p1);
562	if (li.hasIntersection())
563	return li.getIntersection(0);
564	return null;
565	}
566
567	/**
568	* Computes the intersection point of the lines of infinite extent defined
569	* by two line segments (if there is one).
570	* There may be 0, 1 or an infinite number of intersection points
571	* between two lines.
572	* If there is a unique intersection point, it is returned.
573	* Otherwise, <tt>null</tt> is returned.
574	* If more information is required about the details of the intersection,
575	* the {@link RobustLineIntersector} class should be used.
576	*
577	* @param line a line segment defining an straight line with infinite extent
578	* @return an intersection point,
579	* or <code>null</code> if there is no point of intersection
580	* or an infinite number of intersection points
581	*
582	* @see RobustLineIntersector
583	*/
584	public Coordinate lineIntersection(LineSegment line)
585	{
586	Coordinate intPt = Intersection.intersection(p0, p1, line.p0, line.p1);
587	return intPt;
588	}
589
590	/**
591	* Creates a LineString with the same coordinates as this segment
592	*
593	* @param geomFactory the geometry factory to use
594	* @return a LineString with the same geometry as this segment
595	*/
596	public LineString toGeometry(GeometryFactory geomFactory)
597	{
598	return geomFactory.createLineString(new Coordinate[] { p0, p1 });
599	}
600
601	/**
602	* Returns <code>true</code> if <code>other</code> has the same values for
603	* its points.
604	*
605	*@param o a <code>LineSegment</code> with which to do the comparison.
606	*@return <code>true</code> if <code>other</code> is a <code>LineSegment</code>
607	* with the same values for the x and y ordinates.
608	*/
609	public boolean equals(Object o) {
610	if (!(o instanceof LineSegment)) {
611	return false;
612	}
613	LineSegment other = (LineSegment) o;
614	return p0.equals(other.p0) && p1.equals(other.p1);
615	}
616
617	/**
618	* Gets a hashcode for this object.
619	*
620	* @return a hashcode for this object
621	*/
622	public int hashCode() {
623	long bits0 = java.lang.Double.doubleToLongBits(p0.x);
624	bits0 ^= java.lang.Double.doubleToLongBits(p0.y) * 31;
625	int hash0 = (((int) bits0) ^ ((int) (bits0 >> 32)));
626
627	long bits1 = java.lang.Double.doubleToLongBits(p1.x);
628	bits1 ^= java.lang.Double.doubleToLongBits(p1.y) * 31;
629	int hash1 = (((int) bits1) ^ ((int) (bits1 >> 32)));
630
631	// XOR is supposed to be a good way to combine hashcodes
632	return hash0 ^ hash1;
633	}
634
635	/**
636	* Compares this object with the specified object for order.
637	* Uses the standard lexicographic ordering for the points in the LineSegment.
638	*
639	*@param o the <code>LineSegment</code> with which this <code>LineSegment</code>
640	* is being compared
641	*@return a negative integer, zero, or a positive integer as this <code>LineSegment</code>
642	* is less than, equal to, or greater than the specified <code>LineSegment</code>
643	*/
644	public int compareTo(Object o) {
645	LineSegment other = (LineSegment) o;
646	int comp0 = p0.compareTo(other.p0);
647	if (comp0 != 0) return comp0;
648	return p1.compareTo(other.p1);
649	}
650
651	/**
652	* Returns <code>true</code> if <code>other</code> is
653	* topologically equal to this LineSegment (e.g. irrespective
654	* of orientation).
655	*
656	*@param other a <code>LineSegment</code> with which to do the comparison.
657	*@return <code>true</code> if <code>other</code> is a <code>LineSegment</code>
658	* with the same values for the x and y ordinates.
659	*/
660	public boolean equalsTopo(LineSegment other)
661	{
662	return
663	p0.equals(other.p0) && p1.equals(other.p1)
664	\|\| p0.equals(other.p1) && p1.equals(other.p0);
665	}
666
667	public String toString()
668	{
669	return "LINESTRING( " +
670	p0.x + " " + p0.y
671	+ ", " +
672	p1.x + " " + p1.y + ")";
673	}
674	}
675