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 }