View Javadoc

1   /* File Line2D.java 
2    *
3    * Project : Java Geometry Library
4    *
5    * ===========================================
6    * 
7    * This library is free software; you can redistribute it and/or modify it 
8    * under the terms of the GNU Lesser General Public License as published by
9    * the Free Software Foundation, either version 2.1 of the License, or (at
10   * your option) any later version.
11   *
12   * This library is distributed in the hope that it will be useful, but 
13   * WITHOUT ANY WARRANTY, without even the implied warranty of MERCHANTABILITY
14   * or FITNESS FOR A PARTICULAR PURPOSE.
15   *
16   * See the GNU Lesser General Public License for more details.
17   *
18   * You should have received a copy of the GNU Lesser General Public License
19   * along with this library. if not, write to :
20   * The Free Software Foundation, Inc., 59 Temple Place, Suite 330,
21   * Boston, MA 02111-1307, USA.
22   */
23  
24  // package
25  
26  package math.geom2d.line;
27  
28  import java.util.ArrayList;
29  import java.util.Collection;
30  
31  import math.geom2d.AffineTransform2D;
32  import math.geom2d.Angle2D;
33  import math.geom2d.Box2D;
34  import math.geom2d.Point2D;
35  import math.geom2d.Shape2D;
36  import math.geom2d.Vector2D;
37  import math.geom2d.curve.AbstractSmoothCurve2D;
38  import math.geom2d.circulinear.CirculinearCurve2DUtils;
39  import math.geom2d.circulinear.CirculinearDomain2D;
40  import math.geom2d.circulinear.CirculinearElement2D;
41  import math.geom2d.conic.CircleArc2D;
42  import math.geom2d.curve.Curve2D;
43  import math.geom2d.curve.Curve2DUtils;
44  import math.geom2d.curve.CurveArray2D;
45  import math.geom2d.curve.CurveSet2D;
46  import math.geom2d.transform.CircleInversion2D;
47  
48  // Imports
49  
50  /**
51   * Line object defined from 2 points. This object keep points reference in
52   * memory, and recomputes properties directly from points. Line2D is
53   * mutable.
54   * <p>
55   * Example :
56   * <p>
57   * <code>
58   * // Create an Edge2D<br>
59   * Line2D line = new Line2D(new Point2D(0, 0), new Point2D(1, 2));<br>
60   * // Change direction of line, by changing second point :<br>
61   * line.setPoint2(new Point2D(4, 5));<br>
62   * // Change position and direction of the line, by changing first point. <br>
63   * // 'line' is now the edge (2,3)-(4,5)<br>
64   * line.setPoint1(new Point2D(2, 3));<br>
65   * </code>
66   * <p>
67   * <p>
68   * This class may be slower than Edge2D or StraightLine2D, because parameters
69   * are updated each time a computation is made, causing lot of additional
70   * processing. Moreover, as inner point fields are public, it is not as safe
71   * as LineSegment2D.
72   * {@See LineSegment2D}
73   */
74  public class Line2D extends AbstractSmoothCurve2D
75  implements LinearShape2D, CirculinearElement2D, Cloneable {
76  
77      // ===================================================================
78      // constants
79  
80      // ===================================================================
81      // class variables
82  
83      /**
84       * The origin point.
85       */
86      public Point2D p1;
87      
88      /**
89       * The destination point.
90       */
91      public Point2D p2;
92  
93  
94      // ===================================================================
95      // constructors
96  
97      /**
98       * Checks if two line intersect. Uses the
99       * {@link math.geom2d.Point2D#ccw(Point2D, Point2D, Point2D) Point2D.ccw}
100      * method, which is based on Sedgewick algorithm.
101      * 
102      * @param line1 a Line2D object
103      * @param line2 a Line2D object
104      * @return true if the 2 lines intersect
105      */
106     public static boolean intersects(Line2D line1, Line2D line2) {
107         Point2D e1p1 = line1.getFirstPoint();
108         Point2D e1p2 = line1.getLastPoint();
109         Point2D e2p1 = line2.getFirstPoint();
110         Point2D e2p2 = line2.getLastPoint();
111 
112         boolean b1 = Point2D.ccw(e1p1, e1p2, e2p1)
113                 *Point2D.ccw(e1p1, e1p2, e2p2)<=0;
114         boolean b2 = Point2D.ccw(e2p1, e2p2, e1p1)
115                 *Point2D.ccw(e2p1, e2p2, e1p2)<=0;
116         return b1&&b2;
117     }
118 
119     // ===================================================================
120     // constructors
121 
122     /** Define a new Line2D with two extremities. */
123     public Line2D(Point2D point1, Point2D point2) {
124         this.p1 = point1;
125         this.p2 = point2;
126     }
127 
128     /** Define a new Line2D with two extremities. */
129     public Line2D(double x1, double y1, double x2, double y2) {
130         p1 = new Point2D(x1, y1);
131         p2 = new Point2D(x2, y2);
132     }
133 
134     // ===================================================================
135     // Static factory
136 
137     /**
138      * Static factory for creating a new Line2D, starting from p1
139      * and finishing at p2.
140      * @since 0.8.1
141      */
142     public static Line2D create(Point2D p1, Point2D p2) {
143     	return new Line2D(p1, p2);
144     }
145     
146     
147     // ===================================================================
148     // Methods specific to Line2D
149 
150     /**
151      * Return the first point of the edge. It corresponds to getPoint(0).
152      * 
153      * @return the first point.
154      */
155     public Point2D getPoint1() {
156         return p1;
157     }
158 
159     /**
160      * Return the last point of the edge. It corresponds to getPoint(1).
161      * 
162      * @return the last point.
163      */
164     public Point2D getPoint2() {
165         return p2;
166     }
167 
168     public double getX1() {
169         return p1.getX();
170     }
171 
172     public double getY1() {
173         return p1.getY();
174     }
175 
176     public double getX2() {
177         return p2.getX();
178     }
179 
180     public double getY2() {
181         return p2.getY();
182     }
183 
184     /**
185      * Return the opposite vertex of the edge.
186      * 
187      * @param point : one of the vertices of the edge
188      * @return the other vertex
189      */
190     public Point2D getOtherPoint(Point2D point) {
191         if (point.equals(p1))
192             return p2;
193         if (point.equals(p2))
194             return p1;
195         return null;
196     }
197 
198     public void setPoint1(Point2D point) {
199         p1 = point;
200     }
201 
202     public void setPoint2(Point2D point) {
203         p2 = point;
204     }
205 
206     // ===================================================================
207     // methods implementing the LinearShape2D interface
208 
209     public boolean isColinear(LinearShape2D line) {
210         return new LineSegment2D(p1, p2).isColinear(line);
211     }
212 
213     /**
214      * Test if the this object is parallel to the given one. This method is
215      * overloaded to update parameters before computation.
216      */
217     public boolean isParallel(LinearShape2D line) {
218         return new LineSegment2D(p1, p2).isParallel(line);
219     }
220 
221     // ===================================================================
222     // methods implementing the CirculinearCurve2D interface
223 
224 	/* (non-Javadoc)
225 	 * @see math.geom2d.circulinear.CirculinearShape2D#getBuffer(double)
226 	 */
227 	public CirculinearDomain2D getBuffer(double dist) {
228 		return CirculinearCurve2DUtils.computeBuffer(this, dist);
229 	}
230 
231 	/* (non-Javadoc)
232 	 * @see math.geom2d.circulinear.CirculinearCurve2D#getParallel(double)
233 	 */
234 	public Line2D getParallel(double d) {
235 		double x0 = getX1();
236 		double y0 = getY1();
237 		double dx = getX2()-x0;
238 		double dy = getY2()-y0;
239         double dd = Math.sqrt(dx*dx+dy*dy);
240         return new Line2D(
241         		x0+dy*d/dd, y0-dx*d/dd, 
242         		x0+dx+dy*d/dd, y0+dy-dx*d/dd);
243 	}
244 
245 	/* (non-Javadoc)
246 	 * @see math.geom2d.circulinear.CirculinearCurve2D#getLength()
247 	 */
248 	public double getLength() {
249 		return p1.getDistance(p2);
250 	}
251 
252 	/* (non-Javadoc)
253 	 * @see math.geom2d.circulinear.CirculinearCurve2D#getLength(double)
254 	 */
255 	public double getLength(double pos) {
256 		double dx = p2.getX()-p1.getX();
257 		double dy = p2.getY()-p1.getY();
258 		return pos*Math.hypot(dx, dy);
259 	}
260 
261 	/* (non-Javadoc)
262 	 * @see math.geom2d.circulinear.CirculinearCurve2D#getPosition(double)
263 	 */
264 	public double getPosition(double length) {
265 		double dx = p2.getX()-p1.getX();
266 		double dy = p2.getY()-p1.getY();
267 		return length/Math.hypot(dx, dy);
268 	}
269 
270 	/* (non-Javadoc)
271 	 * @see math.geom2d.circulinear.CirculinearCurve2D#transform(math.geom2d.transform.CircleInversion2D)
272 	 */
273 	public CirculinearElement2D transform(CircleInversion2D inv) {
274 		// Extract inversion parameters
275         Point2D center 	= inv.getCenter();
276         double r 		= inv.getRadius();
277         
278         // compute distance of line to inversion center
279         Point2D po 	= new StraightLine2D(this).getProjectedPoint(center);
280         double d 	= this.getDistance(po);
281         
282         // Degenerate case of a line passing through the center.
283         // returns the line itself.
284         if (Math.abs(d)<Shape2D.ACCURACY){
285         	Point2D p1 = this.getFirstPoint().transform(inv);
286         	Point2D p2 = this.getLastPoint().transform(inv);
287         	return new LineSegment2D(p1, p2);
288         }
289         
290         // angle from center to line
291         double angle = Angle2D.getHorizontalAngle(center, po);
292 
293         // center of transformed circle
294         double r2 	= r*r/d/2;
295         Point2D c2 	= Point2D.createPolar(center, r2, angle);
296 
297         // choose direction of circle arc
298         boolean direct = !this.isInside(center);
299         
300         // compute angle between center of transformed circle and end points
301         double theta1 = Angle2D.getHorizontalAngle(c2, p1);
302         double theta2 = Angle2D.getHorizontalAngle(c2, p2);
303         
304         // create the new circle arc
305         return new CircleArc2D(c2, r2, theta1, theta2, direct);
306 	}
307 	
308     // ===================================================================
309     // methods implementing the LinearShape2D interface
310 
311 	/* (non-Javadoc)
312 	 */
313     public double[][] getParametric() {
314         return new LineSegment2D(p1, p2).getParametric();
315     }
316 
317     public double[] getCartesianEquation() {
318         return new LineSegment2D(p1, p2).getCartesianEquation();
319     }
320 
321     public double[] getPolarCoefficients() {
322         return new LineSegment2D(p1, p2).getPolarCoefficients();
323     }
324 
325     public double[] getSignedPolarCoefficients() {
326         return new LineSegment2D(p1, p2).getSignedPolarCoefficients();
327     }
328 
329     // ===================================================================
330     // methods implementing the LinearShape2D interface
331     
332     public double getHorizontalAngle() {
333         return new LineSegment2D(p1, p2).getHorizontalAngle();
334     }
335   
336     /* (non-Javadoc)
337      * @see math.geom2d.line.LinearShape2D#getIntersection(math.geom2d.line.LinearShape2D)
338      */
339     public Point2D getIntersection(LinearShape2D line) {
340         return new LineSegment2D(p1, p2).getIntersection(line);
341     }
342 
343     /* (non-Javadoc)
344      * @see math.geom2d.line.LinearShape2D#getOrigin()
345      */
346     public Point2D getOrigin() {
347         return p1;
348     }
349 
350     /* (non-Javadoc)
351      * @see math.geom2d.line.LinearShape2D#getSupportingLine()
352      */
353     public StraightLine2D getSupportingLine() {
354         return new StraightLine2D(p1, p2);
355     }
356 
357     /* (non-Javadoc)
358      * @see math.geom2d.line.LinearShape2D#getVector()
359      */
360     public Vector2D getVector() {
361         return new Vector2D(p1, p2);
362     }
363 
364     
365     // ===================================================================
366     // methods implementing the OrientedCurve2D interface
367     
368     public double getSignedDistance(java.awt.geom.Point2D p) {
369         return getSignedDistance(p.getX(), p.getY());
370     }
371 
372     public double getSignedDistance(double x, double y) {
373         return new LineSegment2D(p1, p2).getSignedDistance(x, y);
374     }
375 
376     
377     // ===================================================================
378     // methods implementing the ContinuousCurve2D interface
379     
380     /* (non-Javadoc)
381      * @see math.geom2d.curve.ContinuousCurve2D#getSmoothPieces()
382      */
383     @Override
384 	public Collection<? extends Line2D> getSmoothPieces() {
385         ArrayList<Line2D> array = new ArrayList<Line2D>(1);
386         array.add(this);
387         return array;
388     }
389 
390     /**
391      * Returns false.
392      * @see math.geom2d.curve.ContinuousCurve2D#isClosed()
393      */
394     public boolean isClosed() {
395         return false;
396     }
397     
398     // ===================================================================
399     // methods implementing the Shape2D interface
400 
401     /**
402      * Get the distance of the point (x, y) to this edge.
403      */
404     public double getDistance(java.awt.geom.Point2D p) {
405         return getDistance(p.getX(), p.getY());
406     }
407 
408     /**
409      * Get the distance of the point (x, y) to this edge.
410      */
411     public double getDistance(double x, double y) {
412         StraightLine2D support = new StraightLine2D(p1, p2);
413         Point2D proj = support.getProjectedPoint(x, y);
414         if (contains(proj))
415             return proj.distance(x, y);
416         double d1 = Math.hypot(p1.getX()-x, p1.getY()-y);
417         double d2 = Math.hypot(p2.getX()-x, p2.getY()-y);
418         // System.out.println("dist lineObject2D : " + Math.min(d1, d2));
419         return Math.min(d1, d2);
420     }
421 
422     /**
423      * Create a straight line parallel to this object, and going through the
424      * given point.
425      * 
426      * @param point the point to go through
427      * @return the parallel through the point
428      */
429     public StraightLine2D getParallel(Point2D point) {
430         return new LineSegment2D(p1, p2).getParallel(point);
431     }
432 
433     /**
434      * Create a straight line perpendicular to this object, and going through
435      * the given point.
436      * 
437      * @param point : the point to go through
438      * @return the perpendicular through point
439      */
440     public StraightLine2D getPerpendicular(Point2D point) {
441         return new LineSegment2D(p1, p2).getPerpendicular(point);
442     }
443 
444     /**
445      * Clip the line object by a box. The result is an instance of CurveSet2D<LineArc2D>,
446      * which contains only instances of LineArc2D. If the line object is not
447      * clipped, the result is an instance of CurveSet2D<LineArc2D> which
448      * contains 0 curves.
449      */
450     public CurveSet2D<? extends Line2D> clip(Box2D box) {
451         // Clip the curve
452         CurveSet2D<? extends Curve2D> set = Curve2DUtils.clipCurve(this, box);
453 
454         // Stores the result in appropriate structure
455         CurveArray2D<Line2D> result = 
456         	new CurveArray2D<Line2D>(set.getCurveNumber());
457 
458         // convert the result
459         for (Curve2D curve : set.getCurves()) {
460             if (curve instanceof Line2D)
461                 result.addCurve((Line2D) curve);
462         }
463         return result;
464     }
465 
466     /**
467      * Returns the bounding box of the Line2D.
468      */
469     public Box2D getBoundingBox() {
470         return new Box2D(p1, p2);
471     }
472 
473     // ===================================================================
474     // methods inherited from SmoothCurve2D interface
475 
476     public Vector2D getTangent(double t) {
477         return new Vector2D(p1, p2);
478     }
479 
480     /**
481      * Returns 0 as every linear shape.
482      */
483     public double getCurvature(double t) {
484         return 0.0;
485     }
486 
487     // ===================================================================
488     // methods inherited from OrientedCurve2D interface
489 
490     public double getWindingAngle(java.awt.geom.Point2D point) {
491         return new LineSegment2D(p1, p2).getWindingAngle(point);
492     }
493 
494     public boolean isInside(java.awt.geom.Point2D point) {
495         return new LineSegment2D(p1, p2).getSignedDistance(point)<0;
496     }
497 
498     // ===================================================================
499     // methods inherited from Curve2D interface
500 
501     /**
502      * Returns 0.
503      */
504     public double getT0() {
505         return 0.0;
506     }
507 
508     /**
509      * Returns 1.
510      */
511     public double getT1() {
512         return 1.0;
513     }
514 
515     public Point2D getPoint(double t) {
516         if (t<0)
517             return null;
518         if (t>1)
519             return null;
520         double x = p1.getX()*(1-t) + p2.getX()*t;
521         double y = p1.getY()*(1-t) + p2.getY()*t;
522         return new Point2D(x, y);
523     }
524 
525     /**
526      * Get the first point of the curve.
527      * 
528      * @return the first point of the curve
529      */
530     @Override
531     public Point2D getFirstPoint() {
532         return p1;
533     }
534 
535     /**
536      * Get the last point of the curve.
537      * 
538      * @return the last point of the curve.
539      */
540     @Override
541     public Point2D getLastPoint() {
542         return p2;
543     }
544 
545     /**
546      * Gets position of the point on the line. If point belongs to the line,
547      * this position is defined by the ratio :
548      * <p>
549      * <code> t = (xp - x0)/dx <\code>, or equivalently :<p>
550      * <code> t = (yp - y0)/dy <\code>.<p>
551      * If point does not belong to edge, return Double.NaN. The current implementation 
552      * uses the direction with the biggest derivative, in order to avoid divisions 
553      * by zero.
554      */
555     public double getPosition(java.awt.geom.Point2D point) {
556         return new LineSegment2D(p1, p2).getPosition(point);
557     }
558 
559     public double project(java.awt.geom.Point2D point) {
560         return new LineSegment2D(p1, p2).project(point);
561     }
562 
563     /**
564      * Returns the line object which starts at <code>point2</code> and ends at
565      * <code>point1</code>.
566      */
567     public Line2D getReverseCurve() {
568         return new Line2D(p2, p1);
569     }
570 
571     @Override
572 	public Collection<? extends Line2D> getContinuousCurves() {
573     	return wrapCurve(this);
574     }
575 
576     /**
577      * Return a new Line2D, which is the portion of the line delimited by
578      * parameters t0 and t1.
579      */
580     public Line2D getSubCurve(double t0, double t1) {
581         if(t0>t1) 
582             return null;
583         t0 = Math.max(t0, getT0());
584         t1 = Math.min(t1, getT1());
585         return new Line2D(this.getPoint(t0), this.getPoint(t1));
586     }
587 
588     /* (non-Javadoc)
589      * @see math.geom2d.curve.Curve2D#getIntersections(math.geom2d.line.LinearShape2D)
590      */
591     public Collection<Point2D> getIntersections(LinearShape2D line) {
592         return new LineSegment2D(p1, p2).getIntersections(line);
593     }
594 
595     // ===================================================================
596     // methods inherited from Shape2D interface
597 
598     public Line2D transform(AffineTransform2D trans) {
599         return new Line2D(
600                 p1.transform(trans), 
601                 p2.transform(trans));
602     }
603 
604     // ===================================================================
605     // methods inherited from Shape interface
606 
607     /**
608      * Returns true if the point (x, y) lies on the line, with precision given
609      * by Shape2D.ACCURACY.
610      */
611     public boolean contains(double x, double y) {
612         return new LineSegment2D(p1, p2).contains(x, y);
613     }
614 
615     /**
616      * Returns true if the point p lies on the line, with precision given by
617      * Shape2D.ACCURACY.
618      */
619     public boolean contains(java.awt.geom.Point2D p) {
620         return contains(p.getX(), p.getY());
621     }
622 
623     /**
624      * Returns true
625      */
626     public boolean isBounded() {
627         return true;
628     }
629 
630     /**
631      * Returns false
632      */
633     public boolean isEmpty() {
634         return false;
635     }
636 
637     public java.awt.geom.GeneralPath getGeneralPath() {
638         java.awt.geom.GeneralPath path = new java.awt.geom.GeneralPath();
639         path.moveTo((float) p1.getX(), (float) p1.getY());
640         path.lineTo((float) p2.getX(), (float) p2.getY());
641         return path;
642     }
643 
644     public java.awt.geom.GeneralPath appendPath(java.awt.geom.GeneralPath path) {
645         path.lineTo((float) p2.getX(), (float) p2.getY());
646         return path;
647     }
648 
649     // ===================================================================
650     // methods inherited from Object interface
651 
652     @Override
653     public String toString() {
654         return "Line2D(" + p1 + ")-(" + p2 + ")";
655     }
656 
657     /**
658      * Two Line2D are equals if the share the two same points, 
659      * in the same order.
660      * 
661      * @param obj the edge to compare to.
662      * @return true if extremities of both edges are the same.
663      */
664     @Override
665     public boolean equals(Object obj) {
666         // check class
667         if(!(obj instanceof Line2D))
668             return false;
669         
670         // cast class, and compare members
671         Line2D edge = (Line2D) obj;
672         return p1.equals(edge.p1) && p2.equals(edge.p2);
673     }
674     
675     @Override
676     public Line2D clone() {
677         return new Line2D(p1.clone(), p2.clone());
678     }
679 }