View Javadoc

1   /**
2    * 
3    */
4   
5   package math.geom3d.line;
6   
7   import java.util.ArrayList;
8   import java.util.Collection;
9   
10  import math.geom3d.Box3D;
11  import math.geom3d.Point3D;
12  import math.geom3d.Shape3D;
13  import math.geom3d.Vector3D;
14  import math.geom3d.curve.ContinuousCurve3D;
15  import math.geom3d.curve.Curve3D;
16  import math.geom3d.transform.AffineTransform3D;
17  import math.utils.MathUtils;
18  
19  /**
20   * @author dlegland
21   */
22  public class LineSegment3D implements ContinuousCurve3D {
23  
24      // ===================================================================
25      // class variables
26  
27      protected double x1 = 0;
28      protected double y1 = 0;
29      protected double z1 = 0;
30      protected double x2 = 1;
31      protected double y2 = 0;
32      protected double z2 = 0;
33  
34      // ===================================================================
35      // constructors
36  
37      public LineSegment3D(Point3D p1, Point3D p2) {
38          this.x1 = p1.getX();
39          this.y1 = p1.getY();
40          this.z1 = p1.getZ();
41          this.x2 = p2.getX();
42          this.y2 = p2.getY();
43          this.z2 = p2.getZ();
44      }
45  
46      // ===================================================================
47      // methods specific to StraightLine3D
48  
49      public StraightLine3D getSupportingLine() {
50          return new StraightLine3D(x1, y1, z1, x2-x1, y2-y1, z2-z1);
51      }
52      
53      public Point3D projectPoint(Point3D point) {
54      	return getPoint(project(point));
55      }
56  
57      // ===================================================================
58      // methods implementing the Curve3D interface
59  
60      /*
61       * (non-Javadoc)
62       * 
63       * @see math.geom3d.curve.Curve3D#getContinuousCurves()
64       */
65      public Collection<LineSegment3D> getContinuousCurves() {
66          ArrayList<LineSegment3D> array = new ArrayList<LineSegment3D>(1);
67          array.add(this);
68          return array;
69      }
70  
71      /*
72       * (non-Javadoc)
73       * 
74       * @see math.geom3d.curve.Curve3D#getFirstPoint()
75       */
76      public Point3D getFirstPoint() {
77          return new Point3D(x1, y1, z1);
78      }
79  
80      /*
81       * (non-Javadoc)
82       * 
83       * @see math.geom3d.curve.Curve3D#getLastPoint()
84       */
85      public Point3D getLastPoint() {
86          return new Point3D(x2, y2, z2);
87      }
88  
89      /*
90       * (non-Javadoc)
91       * 
92       * @see math.geom3d.curve.Curve3D#getPoint(double)
93       */
94      public Point3D getPoint(double t) {
95          return getPoint(t, new Point3D());
96      }
97  
98      /*
99       * (non-Javadoc)
100      * 
101      * @see math.geom3d.curve.Curve3D#getPoint(double, math.geom3d.Point3D)
102      */
103     public Point3D getPoint(double t, Point3D point) {
104         if (point==null)
105             point = new Point3D();
106         t = Math.max(Math.min(t, 1), 0);
107         point.setLocation(x1+(x2-x1)*t, y1+(y2-y1)*t, z1+(z2-z1)*t);
108         return point;
109     }
110 
111     /**
112      * If point does not project on the line segment, return Double.NaN.
113      * 
114      * @see math.geom3d.curve.Curve3D#getPosition(math.geom3d.Point3D)
115      */
116     public double getPosition(Point3D point) {
117         double t = this.getSupportingLine().getPosition(point);
118         if (t>1)
119             return Double.NaN;
120         if (t<0)
121             return Double.NaN;
122         return t;
123     }
124 
125     /*
126      * (non-Javadoc)
127      * 
128      * @see math.geom3d.curve.Curve3D#getReverseCurve()
129      */
130     public Curve3D getReverseCurve() {
131         return new StraightLine3D(getLastPoint(), getFirstPoint());
132     }
133 
134     /**
135      * Returns the2 end points.
136      * 
137      * @see math.geom3d.curve.Curve3D#getSingularPoints()
138      */
139     public Collection<Point3D> getSingularPoints() {
140         ArrayList<Point3D> points = new ArrayList<Point3D>(2);
141         points.add(getFirstPoint());
142         points.add(getLastPoint());
143         return points;
144     }
145 
146     /*
147      * (non-Javadoc)
148      * 
149      * @see math.geom3d.curve.Curve3D#getSubCurve(double, double)
150      */
151     public LineSegment3D getSubCurve(double t0, double t1) {
152         t0 = Math.max(t0, 0);
153         t1 = Math.min(t1, 1);
154         return new LineSegment3D(getPoint(t0), getPoint(t1));
155     }
156 
157     /**
158      * Return 0, by definition of LineSegment.
159      * 
160      * @see math.geom3d.curve.Curve3D#getT0()
161      */
162     public double getT0() {
163         return 0;
164     }
165 
166     /**
167      * Return 1, by definition of LineSegment.
168      * 
169      * @see math.geom3d.curve.Curve3D#getT1()
170      */
171     public double getT1() {
172         return 1;
173     }
174 
175     /*
176      * (non-Javadoc)
177      * 
178      * @see math.geom3d.curve.Curve3D#project(math.geom3d.Point3D)
179      */
180     public double project(Point3D point) {
181         double t = getSupportingLine().project(point);
182         return Math.min(Math.max(t, 0), 1);
183     }
184 
185     /*
186      * (non-Javadoc)
187      * 
188      * @see math.geom3d.curve.Curve3D#transform(math.geom3d.transform.AffineTransform3D)
189      */
190     public Curve3D transform(AffineTransform3D trans) {
191         return new LineSegment3D(new Point3D(x1, y1, z1).transform(trans),
192                 new Point3D(x2, y2, z2).transform(trans));
193     }
194 
195     // ===================================================================
196     // methods implementing the Shape3D interface
197 
198     /*
199      * (non-Javadoc)
200      * 
201      * @see math.geom3d.Shape3D#clip(math.geom3d.Box3D)
202      */
203     public Shape3D clip(Box3D box) {
204         // TODO Auto-generated method stub
205         return null;
206     }
207 
208     /*
209      * (non-Javadoc)
210      * 
211      * @see math.geom3d.Shape3D#contains(math.geom3d.Point3D)
212      */
213     public boolean contains(Point3D point) {
214         StraightLine3D line = this.getSupportingLine();
215         if (!line.contains(point))
216             return false;
217         double t = line.getPosition(point);
218         if (t<-Shape3D.ACCURACY)
219             return false;
220         if (t>1+Shape3D.ACCURACY)
221             return false;
222         return true;
223     }
224 
225     /*
226      * (non-Javadoc)
227      * 
228      * @see math.geom3d.Shape3D#getBoundingBox()
229      */
230     public Box3D getBoundingBox() {
231         return new Box3D(x1, x2, y1, y2, z1, z2);
232     }
233 
234     /*
235      * (non-Javadoc)
236      * 
237      * @see math.geom3d.Shape3D#getDistance(math.geom3d.Point3D)
238      */
239     public double getDistance(Point3D point) {
240         double t = this.project(point);
241         return getPoint(t).getDistance(point);
242     }
243     
244     /**
245      * Returns distance of this segment from 'segment'.
246      * <p><p>
247      * Based on: http://softsurfer.com/Archive/algorithm_0106/ 
248      * <p>
249      * dist3D_Segment_to_Segment()
250      * 
251      * @param segment
252      * @return
253      */
254     public double getDistance(LineSegment3D segment) {
255     	LineSegment3D thisSegment = this;
256         Vector3D u = new Vector3D(thisSegment.getFirstPoint(), thisSegment.getLastPoint());
257         Vector3D v = new Vector3D(segment.getFirstPoint(), segment.getLastPoint());
258         Vector3D w = new Vector3D(segment.getFirstPoint(), thisSegment.getFirstPoint());
259         double   a = Vector3D.dotProduct(u,u);        // always >= 0
260         double   b = Vector3D.dotProduct(u,v);
261         double   c = Vector3D.dotProduct(v,v);        // always >= 0
262         double   d = Vector3D.dotProduct(u,w);
263         double   e = Vector3D.dotProduct(v,w);
264         double   D = a*c - b*b;       // always >= 0
265         double   sc, sN, sD = D;      // sc = sN / sD, default sD = D >= 0
266         double   tc, tN, tD = D;      // tc = tN / tD, default tD = D >= 0
267 
268         // compute the line parameters of the two closest points
269         if (D < MathUtils.EPSILON) { // the lines are almost parallel
270             sN = 0.0;        // force using point P0 on segment S1
271             sD = 1.0;        // to prevent possible division by 0.0 later
272             tN = e;
273             tD = c;
274         }
275         else {                // get the closest points on the infinite lines
276             sN = (b*e - c*d);
277             tN = (a*e - b*d);
278             if (sN < 0.0) {       // sc < 0 => the s=0 edge is visible
279                 sN = 0.0;
280                 tN = e;
281                 tD = c;
282             }
283             else if (sN > sD) {  // sc > 1 => the s=1 edge is visible
284                 sN = sD;
285                 tN = e + b;
286                 tD = c;
287             }
288         }
289 
290         if (tN < 0.0) {           // tc < 0 => the t=0 edge is visible
291             tN = 0.0;
292             // recompute sc for this edge
293             if (-d < 0.0)
294                 sN = 0.0;
295             else if (-d > a)
296                 sN = sD;
297             else {
298                 sN = -d;
299                 sD = a;
300             }
301         }
302         else if (tN > tD) {      // tc > 1 => the t=1 edge is visible
303             tN = tD;
304             // recompute sc for this edge
305             if ((-d + b) < 0.0)
306                 sN = 0;
307             else if ((-d + b) > a)
308                 sN = sD;
309             else {
310                 sN = (-d + b);
311                 sD = a;
312             }
313         }
314         // finally do the division to get sc and tc
315         sc = (Math.abs(sN) < MathUtils.EPSILON ? 0.0 : sN / sD);
316         tc = (Math.abs(tN) < MathUtils.EPSILON ? 0.0 : tN / tD);
317 
318         // get the difference of the two closest points
319         //       dP = w + (sc * u) - (tc * v);
320         Vector3D dP = w.plus(u.times(sc).minus(v.times(tc)));  // = S1(sc) - S2(tc)
321 
322         return dP.getLength();   // return the closest distance
323     }
324 
325     /**
326      * Returns true, as a LineSegment3D is always bounded.
327      * 
328      * @see math.geom3d.Shape3D#isBounded()
329      */
330     public boolean isBounded() {
331         return true;
332     }
333 
334     /**
335      * Returns false, as a LineSegment3D is never empty.
336      * 
337      * @see math.geom3d.Shape3D#isEmpty()
338      */
339     public boolean isEmpty() {
340         return false;
341     }
342 
343 }