1 // Copyright (C) 2002-2012 Nikolaus Gebhardt
\r
2 // This file is part of the "Irrlicht Engine".
\r
3 // For conditions of distribution and use, see copyright notice in irrlicht.h
\r
5 #ifndef __IRR_LINE_2D_H_INCLUDED__
\r
6 #define __IRR_LINE_2D_H_INCLUDED__
\r
8 #include "irrTypes.h"
\r
9 #include "vector2d.h"
\r
16 //! 2D line between two points with intersection methods.
\r
21 //! Default constructor for line going from (0,0) to (1,1).
\r
22 line2d() : start(0,0), end(1,1) {}
\r
23 //! Constructor for line between the two points.
\r
24 line2d(T xa, T ya, T xb, T yb) : start(xa, ya), end(xb, yb) {}
\r
25 //! Constructor for line between the two points given as vectors.
\r
26 line2d(const vector2d<T>& start, const vector2d<T>& end) : start(start), end(end) {}
\r
30 line2d<T> operator+(const vector2d<T>& point) const { return line2d<T>(start + point, end + point); }
\r
31 line2d<T>& operator+=(const vector2d<T>& point) { start += point; end += point; return *this; }
\r
33 line2d<T> operator-(const vector2d<T>& point) const { return line2d<T>(start - point, end - point); }
\r
34 line2d<T>& operator-=(const vector2d<T>& point) { start -= point; end -= point; return *this; }
\r
36 bool operator==(const line2d<T>& other) const
\r
37 { return (start==other.start && end==other.end) || (end==other.start && start==other.end);}
\r
38 bool operator!=(const line2d<T>& other) const
\r
39 { return !(start==other.start && end==other.end) || (end==other.start && start==other.end);}
\r
42 //! Set this line to new line going through the two points.
\r
43 void setLine(const T& xa, const T& ya, const T& xb, const T& yb){start.set(xa, ya); end.set(xb, yb);}
\r
44 //! Set this line to new line going through the two points.
\r
45 void setLine(const vector2d<T>& nstart, const vector2d<T>& nend){start.set(nstart); end.set(nend);}
\r
46 //! Set this line to new line given as parameter.
\r
47 void setLine(const line2d<T>& line){start.set(line.start); end.set(line.end);}
\r
49 //! Get length of line
\r
50 /** \return Length of the line. */
\r
51 T getLength() const { return start.getDistanceFrom(end); }
\r
53 //! Get squared length of the line
\r
54 /** \return Squared length of line. */
\r
55 T getLengthSQ() const { return start.getDistanceFromSQ(end); }
\r
57 //! Get middle of the line
\r
58 /** \return center of the line. */
\r
59 vector2d<T> getMiddle() const
\r
61 return (start + end)/(T)2;
\r
64 //! Get the vector of the line.
\r
65 /** \return The vector of the line. */
\r
66 vector2d<T> getVector() const { return vector2d<T>( end.X - start.X, end.Y - start.Y); }
\r
68 /*! Check if this segment intersects another segment,
\r
69 or if segments are coincindent (colinear). */
\r
70 bool intersectAsSegments( const line2d<T>& other) const
\r
73 // http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/
\r
75 // Find the four orientations needed for general and
\r
77 s32 o1 = start.checkOrientation( end, other.start);
\r
78 s32 o2 = start.checkOrientation( end, other.end);
\r
79 s32 o3 = other.start.checkOrientation( other.end, start);
\r
80 s32 o4 = other.start.checkOrientation( other.end, end);
\r
83 if (o1 != o2 && o3 != o4)
\r
86 // Special Cases to check if segments are coolinear
\r
87 if (o1 == 0 && other.start.isBetweenPoints( start, end)) return true;
\r
88 if (o2 == 0 && other.end.isBetweenPoints( start, end)) return true;
\r
89 if (o3 == 0 && start.isBetweenPoints( other.start, other.end)) return true;
\r
90 if (o4 == 0 && end.isBetweenPoints( other.start, other.end)) return true;
\r
92 return false; // Doesn't fall in any of the above cases
\r
95 /*! Check if 2 segments are incident (intersects in exactly 1 point).*/
\r
96 bool incidentSegments( const line2d<T>& other) const
\r
99 start.checkOrientation( end, other.start) != start.checkOrientation( end, other.end)
\r
100 && other.start.checkOrientation( other.end, start) != other.start.checkOrientation( other.end, end);
\r
103 /*! Check if 2 lines/segments are parallel or nearly parallel.*/
\r
104 bool nearlyParallel( const line2d<T>& line, const T factor = relativeErrorFactor<T>()) const
\r
106 const vector2d<T> a = getVector();
\r
107 const vector2d<T> b = line.getVector();
\r
109 return a.nearlyParallel( b, factor);
\r
112 /*! returns a intersection point of 2 lines (if lines are not parallel). Behaviour
\r
113 undefined if lines are parallel or coincident.
\r
114 It's on optimized intersectWith with checkOnlySegments=false and ignoreCoincidentLines=true
\r
116 vector2d<T> fastLinesIntersection( const line2d<T>& l) const
\r
118 const f32 commonDenominator = (f32)((l.end.Y - l.start.Y)*(end.X - start.X) -
\r
119 (l.end.X - l.start.X)*(end.Y - start.Y));
\r
121 if ( commonDenominator != 0.f )
\r
123 const f32 numeratorA = (f32)((l.end.X - l.start.X)*(start.Y - l.start.Y) -
\r
124 (l.end.Y - l.start.Y)*(start.X - l.start.X));
\r
126 const f32 uA = numeratorA / commonDenominator;
\r
128 // Calculate the intersection point.
\r
129 return vector2d<T> (
\r
130 (T)(start.X + uA * (end.X - start.X)),
\r
131 (T)(start.Y + uA * (end.Y - start.Y))
\r
138 /*! Check if this line intersect a segment. The eventual intersection point is returned in "out".*/
\r
139 bool lineIntersectSegment( const line2d<T>& segment, vector2d<T> & out) const
\r
141 if (nearlyParallel( segment))
\r
144 out = fastLinesIntersection( segment);
\r
146 return out.isBetweenPoints( segment.start, segment.end);
\r
149 //! Tests if this line intersects with another line.
\r
150 /** \param l: Other line to test intersection with.
\r
151 \param checkOnlySegments: Default is to check intersection between the begin and endpoints.
\r
152 When set to false the function will check for the first intersection point when extending the lines.
\r
153 \param out: If there is an intersection, the location of the
\r
154 intersection will be stored in this vector.
\r
155 \param ignoreCoincidentLines: When true coincident lines (lines above each other) are never considered as intersecting.
\r
156 When false the center of the overlapping part is returned.
\r
157 \return True if there is an intersection, false if not. */
\r
158 bool intersectWith(const line2d<T>& l, vector2d<T>& out, bool checkOnlySegments=true, bool ignoreCoincidentLines=false) const
\r
160 // Uses the method given at:
\r
161 // http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
\r
162 const f32 commonDenominator = (f32)((l.end.Y - l.start.Y)*(end.X - start.X) -
\r
163 (l.end.X - l.start.X)*(end.Y - start.Y));
\r
165 const f32 numeratorA = (f32)((l.end.X - l.start.X)*(start.Y - l.start.Y) -
\r
166 (l.end.Y - l.start.Y)*(start.X -l.start.X));
\r
168 const f32 numeratorB = (f32)((end.X - start.X)*(start.Y - l.start.Y) -
\r
169 (end.Y - start.Y)*(start.X -l.start.X));
\r
171 if(equals(commonDenominator, 0.f))
\r
173 // The lines are either coincident or parallel
\r
174 // if both numerators are 0, the lines are coincident
\r
175 if(!ignoreCoincidentLines && equals(numeratorA, 0.f) && equals(numeratorB, 0.f))
\r
177 // Try and find a common endpoint
\r
178 if(l.start == start || l.end == start)
\r
180 else if(l.end == end || l.start == end)
\r
182 // now check if the two segments are disjunct
\r
183 else if (l.start.X>start.X && l.end.X>start.X && l.start.X>end.X && l.end.X>end.X)
\r
185 else if (l.start.Y>start.Y && l.end.Y>start.Y && l.start.Y>end.Y && l.end.Y>end.Y)
\r
187 else if (l.start.X<start.X && l.end.X<start.X && l.start.X<end.X && l.end.X<end.X)
\r
189 else if (l.start.Y<start.Y && l.end.Y<start.Y && l.start.Y<end.Y && l.end.Y<end.Y)
\r
191 // else the lines are overlapping to some extent
\r
194 // find the points which are not contributing to the
\r
198 if ((start.X>l.start.X && start.X>l.end.X && start.X>end.X) || (start.Y>l.start.Y && start.Y>l.end.Y && start.Y>end.Y))
\r
200 else if ((end.X>l.start.X && end.X>l.end.X && end.X>start.X) || (end.Y>l.start.Y && end.Y>l.end.Y && end.Y>start.Y))
\r
202 else if ((l.start.X>start.X && l.start.X>l.end.X && l.start.X>end.X) || (l.start.Y>start.Y && l.start.Y>l.end.Y && l.start.Y>end.Y))
\r
206 if (maxp != start && ((start.X<l.start.X && start.X<l.end.X && start.X<end.X) || (start.Y<l.start.Y && start.Y<l.end.Y && start.Y<end.Y)))
\r
208 else if (maxp != end && ((end.X<l.start.X && end.X<l.end.X && end.X<start.X) || (end.Y<l.start.Y && end.Y<l.end.Y && end.Y<start.Y)))
\r
210 else if (maxp != l.start && ((l.start.X<start.X && l.start.X<l.end.X && l.start.X<end.X) || (l.start.Y<start.Y && l.start.Y<l.end.Y && l.start.Y<end.Y)))
\r
215 // one line is contained in the other. Pick the center
\r
216 // of the remaining points, which overlap for sure
\r
217 out = core::vector2d<T>();
\r
218 if (start != maxp && start != minp)
\r
220 if (end != maxp && end != minp)
\r
222 if (l.start != maxp && l.start != minp)
\r
224 if (l.end != maxp && l.end != minp)
\r
226 out.X = (T)(out.X/2);
\r
227 out.Y = (T)(out.Y/2);
\r
230 return true; // coincident
\r
233 return false; // parallel
\r
236 // Get the point of intersection on this line, checking that
\r
237 // it is within the line segment.
\r
238 const f32 uA = numeratorA / commonDenominator;
\r
239 if (checkOnlySegments)
\r
241 if(uA < 0.f || uA > 1.f)
\r
242 return false; // Outside the line segment
\r
244 const f32 uB = numeratorB / commonDenominator;
\r
245 if(uB < 0.f || uB > 1.f)
\r
246 return false; // Outside the line segment
\r
249 // Calculate the intersection point.
\r
250 out.X = (T)(start.X + uA * (end.X - start.X));
\r
251 out.Y = (T)(start.Y + uA * (end.Y - start.Y));
\r
255 //! Get unit vector of the line.
\r
256 /** \return Unit vector of this line. */
\r
257 vector2d<T> getUnitVector() const
\r
259 T len = (T)(1.0 / getLength());
\r
260 return vector2d<T>((end.X - start.X) * len, (end.Y - start.Y) * len);
\r
263 //! Get angle between this line and given line.
\r
264 /** \param l Other line for test.
\r
265 \return Angle in degrees. */
\r
266 f64 getAngleWith(const line2d<T>& l) const
\r
268 vector2d<T> vect = getVector();
\r
269 vector2d<T> vect2 = l.getVector();
\r
270 return vect.getAngleWith(vect2);
\r
273 //! Tells us if the given point lies to the left, right, or on the line.
\r
274 /** \return 0 if the point is on the line
\r
275 <0 if to the left, or >0 if to the right. */
\r
276 T getPointOrientation(const vector2d<T>& point) const
\r
278 return ( (end.X - start.X) * (point.Y - start.Y) -
\r
279 (point.X - start.X) * (end.Y - start.Y) );
\r
282 //! Check if the given point is a member of the line
\r
283 /** \return True if point is between start and end, else false. */
\r
284 bool isPointOnLine(const vector2d<T>& point) const
\r
286 T d = getPointOrientation(point);
\r
287 return (d == 0 && point.isBetweenPoints(start, end));
\r
290 //! Check if the given point is between start and end of the line.
\r
291 /** Assumes that the point is already somewhere on the line. */
\r
292 bool isPointBetweenStartAndEnd(const vector2d<T>& point) const
\r
294 return point.isBetweenPoints(start, end);
\r
297 //! Get the closest point on this line to a point
\r
298 /** \param point: Starting search at this point
\r
299 \param checkOnlySegments: Default (true) is to return a point on the line-segment (between begin and end) of the line.
\r
300 When set to false the function will check for the first the closest point on the the line even when outside the segment. */
\r
301 vector2d<T> getClosestPoint(const vector2d<T>& point, bool checkOnlySegments=true) const
\r
303 vector2d<f64> c((f64)(point.X-start.X), (f64)(point.Y- start.Y));
\r
304 vector2d<f64> v((f64)(end.X-start.X), (f64)(end.Y-start.Y));
\r
305 f64 d = v.getLength();
\r
306 if ( d == 0 ) // can't tell much when the line is just a single point
\r
309 f64 t = v.dotProduct(c);
\r
311 if ( checkOnlySegments )
\r
313 if (t < 0) return vector2d<T>((T)start.X, (T)start.Y);
\r
314 if (t > d) return vector2d<T>((T)end.X, (T)end.Y);
\r
318 return vector2d<T>((T)(start.X + v.X), (T)(start.Y + v.Y));
\r
321 //! Start point of the line.
\r
323 //! End point of the line.
\r
327 // partial specialization to optimize <f32> lines (avoiding casts)
\r
329 inline vector2df line2d<irr::f32>::getClosestPoint(const vector2df& point, bool checkOnlySegments) const
\r
331 const vector2df c = point - start;
\r
332 vector2df v = end - start;
\r
333 const f32 d = (f32)v.getLength();
\r
334 if ( d == 0 ) // can't tell much when the line is just a single point
\r
337 const f32 t = v.dotProduct(c);
\r
339 if ( checkOnlySegments )
\r
341 if (t < 0) return start;
\r
342 if (t > d) return end;
\r
350 //! Typedef for an f32 line.
\r
351 typedef line2d<f32> line2df;
\r
352 //! Typedef for an integer line.
\r
353 typedef line2d<s32> line2di;
\r
355 } // end namespace core
\r
356 } // end namespace irr
\r