001:
002: /*
003: * The JTS Topology Suite is a collection of Java classes that
004: * implement the fundamental operations required to validate a given
005: * geo-spatial data set to a known topological specification.
006: *
007: * Copyright (C) 2001 Vivid Solutions
008: *
009: * This library is free software; you can redistribute it and/or
010: * modify it under the terms of the GNU Lesser General Public
011: * License as published by the Free Software Foundation; either
012: * version 2.1 of the License, or (at your option) any later version.
013: *
014: * This library is distributed in the hope that it will be useful,
015: * but WITHOUT ANY WARRANTY; without even the implied warranty of
016: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
017: * Lesser General Public License for more details.
018: *
019: * You should have received a copy of the GNU Lesser General Public
020: * License along with this library; if not, write to the Free Software
021: * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
022: *
023: * For more information, contact:
024: *
025: * Vivid Solutions
026: * Suite #1A
027: * 2328 Government Street
028: * Victoria BC V8T 5G5
029: * Canada
030: *
031: * (250)385-6040
032: * www.vividsolutions.com
033: */
034: package com.vividsolutions.jts.geom;
035:
036: import java.io.Serializable;
037:
038: import com.vividsolutions.jts.algorithm.*;
039:
040: /**
041: * Represents a line segment defined by two {@link Coordinate}s.
042: * Provides methods to compute various geometric properties
043: * and relationships of line segments.
044: * <p>
045: * This class is designed to be easily mutable (to the extent of
046: * having its contained points public).
047: * This supports a common pattern of reusing a single LineSegment
048: * object as a way of computing segment properties on the
049: * segments defined by arrays or lists of {@link Coordinate}s.
050: *
051: *@version 1.7
052: */
053: public class LineSegment implements Comparable, Serializable {
054: private static final long serialVersionUID = 3252005833466256227L;
055:
056: public Coordinate p0, p1;
057:
058: public LineSegment(Coordinate p0, Coordinate p1) {
059: this .p0 = p0;
060: this .p1 = p1;
061: }
062:
063: public LineSegment(LineSegment ls) {
064: this (ls.p0, ls.p1);
065: }
066:
067: public LineSegment() {
068: this (new Coordinate(), new Coordinate());
069: }
070:
071: public Coordinate getCoordinate(int i) {
072: if (i == 0)
073: return p0;
074: return p1;
075: }
076:
077: public void setCoordinates(LineSegment ls) {
078: setCoordinates(ls.p0, ls.p1);
079: }
080:
081: public void setCoordinates(Coordinate p0, Coordinate p1) {
082: this .p0.x = p0.x;
083: this .p0.y = p0.y;
084: this .p1.x = p1.x;
085: this .p1.y = p1.y;
086: }
087:
088: /**
089: * Computes the length of the line segment.
090: * @return the length of the line segment
091: */
092: public double getLength() {
093: return p0.distance(p1);
094: }
095:
096: /**
097: * Tests whether the segment is horizontal.
098: *
099: * @return <code>true</code> if the segment is horizontal
100: */
101: public boolean isHorizontal() {
102: return p0.y == p1.y;
103: }
104:
105: /**
106: * Tests whether the segment is vertical.
107: *
108: * @return <code>true</code> if the segment is vertical
109: */
110: public boolean isVertical() {
111: return p0.x == p1.x;
112: }
113:
114: /**
115: * Determines the orientation of a LineSegment relative to this segment.
116: * The concept of orientation is specified as follows:
117: * Given two line segments A and L,
118: * <ul
119: * <li>A is to the left of a segment L if A lies wholly in the
120: * closed half-plane lying to the left of L
121: * <li>A is to the right of a segment L if A lies wholly in the
122: * closed half-plane lying to the right of L
123: * <li>otherwise, A has indeterminate orientation relative to L. This
124: * happens if A is collinear with L or if A crosses the line determined by L.
125: * </ul>
126: *
127: * @param seg the LineSegment to compare
128: *
129: * @return 1 if <code>seg</code> is to the left of this segment
130: * @return -1 if <code>seg</code> is to the right of this segment
131: * @return 0 if <code>seg</code> has indeterminate orientation relative to this segment
132: */
133: public int orientationIndex(LineSegment seg) {
134: int orient0 = CGAlgorithms.orientationIndex(p0, p1, seg.p0);
135: int orient1 = CGAlgorithms.orientationIndex(p0, p1, seg.p1);
136: // this handles the case where the points are L or collinear
137: if (orient0 >= 0 && orient1 >= 0)
138: return Math.max(orient0, orient1);
139: // this handles the case where the points are R or collinear
140: if (orient0 <= 0 && orient1 <= 0)
141: return Math.max(orient0, orient1);
142: // points lie on opposite sides ==> indeterminate orientation
143: return 0;
144: }
145:
146: /**
147: * Reverses the direction of the line segment.
148: */
149: public void reverse() {
150: Coordinate temp = p0;
151: p0 = p1;
152: p1 = temp;
153: }
154:
155: /**
156: * Puts the line segment into a normalized form.
157: * This is useful for using line segments in maps and indexes when
158: * topological equality rather than exact equality is desired.
159: * A segment in normalized form has the first point smaller
160: * than the second (according to the standard ordering on {@link Coordinate}).
161: */
162: public void normalize() {
163: if (p1.compareTo(p0) < 0)
164: reverse();
165: }
166:
167: /**
168: * Computes the angle that the vector defined by this segment
169: * makes with the X-axis.
170: * The angle will be in the range [ -PI, PI ] radians.
171: *
172: * @return the angle this segment makes with the X-axis (in radians)
173: */
174: public double angle() {
175: return Math.atan2(p1.y - p0.y, p1.x - p0.x);
176: }
177:
178: /**
179: * Computes the midpoint of the segment
180: *
181: * @return the midpoint of the segment
182: */
183: public Coordinate midPoint() {
184: return new Coordinate((p0.x + p1.x) / 2, (p0.y + p1.y) / 2);
185: }
186:
187: /**
188: * Computes the distance between this line segment and another segment.
189: *
190: * @return the distance to the other segment
191: */
192: public double distance(LineSegment ls) {
193: return CGAlgorithms.distanceLineLine(p0, p1, ls.p0, ls.p1);
194: }
195:
196: /**
197: * Computes the distance between this line segment and a given point.
198: *
199: * @return the distance from this segment to the given point
200: */
201: public double distance(Coordinate p) {
202: return CGAlgorithms.distancePointLine(p, p0, p1);
203: }
204:
205: /**
206: * Computes the perpendicular distance between the (infinite) line defined
207: * by this line segment and a point.
208: *
209: * @return the perpendicular distance between the defined line and the given point
210: */
211: public double distancePerpendicular(Coordinate p) {
212: return CGAlgorithms.distancePointLinePerpendicular(p, p0, p1);
213: }
214:
215: /**
216: * Computes the {@link Coordinate} that lies a given
217: * fraction along the line defined by this segment.
218: * A fraction of <code>0.0</code> returns the start point of the segment;
219: * a fraction of <code>1.0</code> returns the end point of the segment.
220: *
221: * @param segmentLengthFraction the fraction of the segment length along the line
222: * @return the point at that distance
223: */
224: public Coordinate pointAlong(double segmentLengthFraction) {
225: Coordinate coord = new Coordinate();
226: coord.x = p0.x + segmentLengthFraction * (p1.x - p0.x);
227: coord.y = p0.y + segmentLengthFraction * (p1.y - p0.y);
228: return coord;
229: }
230:
231: /**
232: * Computes the Projection Factor for the projection of the point p
233: * onto this LineSegment. The Projection Factor is the constant r
234: * by which the vector for this segment must be multiplied to
235: * equal the vector for the projection of p on the line
236: * defined by this segment.
237: */
238: public double projectionFactor(Coordinate p) {
239: if (p.equals(p0))
240: return 0.0;
241: if (p.equals(p1))
242: return 1.0;
243: // Otherwise, use comp.graphics.algorithms Frequently Asked Questions method
244: /* AC dot AB
245: r = ---------
246: ||AB||^2
247: r has the following meaning:
248: r=0 P = A
249: r=1 P = B
250: r<0 P is on the backward extension of AB
251: r>1 P is on the forward extension of AB
252: 0<r<1 P is interior to AB
253: */
254: double dx = p1.x - p0.x;
255: double dy = p1.y - p0.y;
256: double len2 = dx * dx + dy * dy;
257: double r = ((p.x - p0.x) * dx + (p.y - p0.y) * dy) / len2;
258: return r;
259: }
260:
261: /**
262: * Compute the projection of a point onto the line determined
263: * by this line segment.
264: * <p>
265: * Note that the projected point
266: * may lie outside the line segment. If this is the case,
267: * the projection factor will lie outside the range [0.0, 1.0].
268: */
269: public Coordinate project(Coordinate p) {
270: if (p.equals(p0) || p.equals(p1))
271: return new Coordinate(p);
272:
273: double r = projectionFactor(p);
274: Coordinate coord = new Coordinate();
275: coord.x = p0.x + r * (p1.x - p0.x);
276: coord.y = p0.y + r * (p1.y - p0.y);
277: return coord;
278: }
279:
280: /**
281: * Project a line segment onto this line segment and return the resulting
282: * line segment. The returned line segment will be a subset of
283: * the target line line segment. This subset may be null, if
284: * the segments are oriented in such a way that there is no projection.
285: * <p>
286: * Note that the returned line may have zero length (i.e. the same endpoints).
287: * This can happen for instance if the lines are perpendicular to one another.
288: *
289: * @param seg the line segment to project
290: * @return the projected line segment, or <code>null</code> if there is no overlap
291: */
292: public LineSegment project(LineSegment seg) {
293: double pf0 = projectionFactor(seg.p0);
294: double pf1 = projectionFactor(seg.p1);
295: // check if segment projects at all
296: if (pf0 >= 1.0 && pf1 >= 1.0)
297: return null;
298: if (pf0 <= 0.0 && pf1 <= 0.0)
299: return null;
300:
301: Coordinate newp0 = project(seg.p0);
302: if (pf0 < 0.0)
303: newp0 = p0;
304: if (pf0 > 1.0)
305: newp0 = p1;
306:
307: Coordinate newp1 = project(seg.p1);
308: if (pf1 < 0.0)
309: newp1 = p0;
310: if (pf1 > 1.0)
311: newp1 = p1;
312:
313: return new LineSegment(newp0, newp1);
314: }
315:
316: /**
317: * Computes the closest point on this line segment to another point.
318: * @param p the point to find the closest point to
319: * @return a Coordinate which is the closest point on the line segment to the point p
320: */
321: public Coordinate closestPoint(Coordinate p) {
322: double factor = projectionFactor(p);
323: if (factor > 0 && factor < 1) {
324: return project(p);
325: }
326: double dist0 = p0.distance(p);
327: double dist1 = p1.distance(p);
328: if (dist0 < dist1)
329: return p0;
330: return p1;
331: }
332:
333: /**
334: * Computes the closest points on two line segments.
335: * @param p the point to find the closest point to
336: * @return a pair of Coordinates which are the closest points on the line segments
337: */
338: public Coordinate[] closestPoints(LineSegment line) {
339: // test for intersection
340: Coordinate intPt = intersection(line);
341: if (intPt != null) {
342: return new Coordinate[] { intPt, intPt };
343: }
344:
345: /**
346: * if no intersection closest pair contains at least one endpoint.
347: * Test each endpoint in turn.
348: */
349: Coordinate[] closestPt = new Coordinate[2];
350: double minDistance = Double.MAX_VALUE;
351: double dist;
352:
353: Coordinate close00 = closestPoint(line.p0);
354: minDistance = close00.distance(line.p0);
355: closestPt[0] = close00;
356: closestPt[1] = line.p0;
357:
358: Coordinate close01 = closestPoint(line.p1);
359: dist = close01.distance(line.p1);
360: if (dist < minDistance) {
361: minDistance = dist;
362: closestPt[0] = close01;
363: closestPt[1] = line.p1;
364: }
365:
366: Coordinate close10 = line.closestPoint(p0);
367: dist = close10.distance(p0);
368: if (dist < minDistance) {
369: minDistance = dist;
370: closestPt[0] = p0;
371: closestPt[1] = close10;
372: }
373:
374: Coordinate close11 = line.closestPoint(p1);
375: dist = close11.distance(p1);
376: if (dist < minDistance) {
377: minDistance = dist;
378: closestPt[0] = p1;
379: closestPt[1] = close11;
380: }
381:
382: return closestPt;
383: }
384:
385: /**
386: * Computes an intersection point between two segments, if there is one.
387: * There may be 0, 1 or many intersection points between two segments.
388: * If there are 0, null is returned. If there is 1 or more, a single one
389: * is returned (chosen at the discretion of the algorithm). If
390: * more information is required about the details of the intersection,
391: * the {@link RobustLineIntersector} class should be used.
392: *
393: * @param line
394: * @return an intersection point, or <code>null</code> if there is none
395: */
396: public Coordinate intersection(LineSegment line) {
397: LineIntersector li = new RobustLineIntersector();
398: li.computeIntersection(p0, p1, line.p0, line.p1);
399: if (li.hasIntersection())
400: return li.getIntersection(0);
401: return null;
402: }
403:
404: /**
405: * Returns <code>true</code> if <code>other</code> has the same values for
406: * its points.
407: *
408: *@param other a <code>LineSegment</code> with which to do the comparison.
409: *@return <code>true</code> if <code>other</code> is a <code>LineSegment</code>
410: * with the same values for the x and y ordinates.
411: */
412: public boolean equals(Object o) {
413: if (!(o instanceof LineSegment)) {
414: return false;
415: }
416: LineSegment other = (LineSegment) o;
417: return p0.equals(other.p0) && p1.equals(other.p1);
418: }
419:
420: /**
421: * Compares this object with the specified object for order.
422: * Uses the standard lexicographic ordering for the points in the LineSegment.
423: *
424: *@param o the <code>LineSegment</code> with which this <code>LineSegment</code>
425: * is being compared
426: *@return a negative integer, zero, or a positive integer as this <code>LineSegment</code>
427: * is less than, equal to, or greater than the specified <code>LineSegment</code>
428: */
429: public int compareTo(Object o) {
430: LineSegment other = (LineSegment) o;
431: int comp0 = p0.compareTo(other.p0);
432: if (comp0 != 0)
433: return comp0;
434: return p1.compareTo(other.p1);
435: }
436:
437: /**
438: * Returns <code>true</code> if <code>other</code> is
439: * topologically equal to this LineSegment (e.g. irrespective
440: * of orientation).
441: *
442: *@param other a <code>LineSegment</code> with which to do the comparison.
443: *@return <code>true</code> if <code>other</code> is a <code>LineSegment</code>
444: * with the same values for the x and y ordinates.
445: */
446: public boolean equalsTopo(LineSegment other) {
447: return p0.equals(other.p0) && p1.equals(other.p1)
448: || p0.equals(other.p1) && p1.equals(other.p0);
449: }
450:
451: public String toString() {
452: return "LINESTRING( " + p0.x + " " + p0.y + ", " + p1.x + " "
453: + p1.y + ")";
454: }
455: }
|