Irrlicht 3D Engine
line2d.h
Go to the documentation of this file.
1 // Copyright (C) 2002-2012 Nikolaus Gebhardt
2 // This file is part of the "Irrlicht Engine".
3 // For conditions of distribution and use, see copyright notice in irrlicht.h
4 
5 #ifndef __IRR_LINE_2D_H_INCLUDED__
6 #define __IRR_LINE_2D_H_INCLUDED__
7 
8 #include "irrTypes.h"
9 #include "vector2d.h"
10 
11 namespace irr
12 {
13 namespace core
14 {
15 
17 template <class T>
18 class line2d
19 {
20  public:
22  line2d() : start(0,0), end(1,1) {}
24  line2d(T xa, T ya, T xb, T yb) : start(xa, ya), end(xb, yb) {}
28  line2d(const line2d<T>& other) : start(other.start), end(other.end) {}
29 
30  // operators
31 
32  line2d<T> operator+(const vector2d<T>& point) const { return line2d<T>(start + point, end + point); }
33  line2d<T>& operator+=(const vector2d<T>& point) { start += point; end += point; return *this; }
34 
35  line2d<T> operator-(const vector2d<T>& point) const { return line2d<T>(start - point, end - point); }
36  line2d<T>& operator-=(const vector2d<T>& point) { start -= point; end -= point; return *this; }
37 
38  bool operator==(const line2d<T>& other) const
39  { return (start==other.start && end==other.end) || (end==other.start && start==other.end);}
40  bool operator!=(const line2d<T>& other) const
41  { return !(start==other.start && end==other.end) || (end==other.start && start==other.end);}
42 
43  // functions
45  void setLine(const T& xa, const T& ya, const T& xb, const T& yb){start.set(xa, ya); end.set(xb, yb);}
47  void setLine(const vector2d<T>& nstart, const vector2d<T>& nend){start.set(nstart); end.set(nend);}
49  void setLine(const line2d<T>& line){start.set(line.start); end.set(line.end);}
50 
52 
53  T getLength() const { return start.getDistanceFrom(end); }
54 
56 
57  T getLengthSQ() const { return start.getDistanceFromSQ(end); }
58 
60 
62  {
63  return (start + end)/(T)2;
64  }
65 
67 
68  vector2d<T> getVector() const { return vector2d<T>( end.X - start.X, end.Y - start.Y); }
69 
72  bool intersectAsSegments( const line2d<T>& other) const
73  {
74  // Taken from:
75  // http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/
76 
77  // Find the four orientations needed for general and
78  // special cases
79  s32 o1 = start.checkOrientation( end, other.start);
80  s32 o2 = start.checkOrientation( end, other.end);
81  s32 o3 = other.start.checkOrientation( other.end, start);
82  s32 o4 = other.start.checkOrientation( other.end, end);
83 
84  // General case
85  if (o1 != o2 && o3 != o4)
86  return true;
87 
88  // Special Cases to check if segments are coolinear
89  if (o1 == 0 && other.start.isBetweenPoints( start, end)) return true;
90  if (o2 == 0 && other.end.isBetweenPoints( start, end)) return true;
91  if (o3 == 0 && start.isBetweenPoints( other.start, other.end)) return true;
92  if (o4 == 0 && end.isBetweenPoints( other.start, other.end)) return true;
93 
94  return false; // Doesn't fall in any of the above cases
95  }
96 
98  bool incidentSegments( const line2d<T>& other) const
99  {
100  return
101  start.checkOrientation( end, other.start) != start.checkOrientation( end, other.end)
102  && other.start.checkOrientation( other.end, start) != other.start.checkOrientation( other.end, end);
103  }
104 
106  bool nearlyParallel( const line2d<T>& line, const T factor = relativeErrorFactor<T>()) const
107  {
108  const vector2d<T> a = getVector();
109  const vector2d<T> b = line.getVector();
110 
111  return a.nearlyParallel( b, factor);
112  }
113 
119  {
120  const f32 commonDenominator = (f32)((l.end.Y - l.start.Y)*(end.X - start.X) -
121  (l.end.X - l.start.X)*(end.Y - start.Y));
122 
123  if ( commonDenominator != 0.f )
124  {
125  const f32 numeratorA = (f32)((l.end.X - l.start.X)*(start.Y - l.start.Y) -
126  (l.end.Y - l.start.Y)*(start.X - l.start.X));
127 
128  const f32 uA = numeratorA / commonDenominator;
129 
130  // Calculate the intersection point.
131  return vector2d<T> (
132  (T)(start.X + uA * (end.X - start.X)),
133  (T)(start.Y + uA * (end.Y - start.Y))
134  );
135  }
136  else
137  return l.start;
138  }
139 
141  bool lineIntersectSegment( const line2d<T>& segment, vector2d<T> & out) const
142  {
143  if (nearlyParallel( segment))
144  return false;
145 
146  out = fastLinesIntersection( segment);
147 
148  return out.isBetweenPoints( segment.start, segment.end);
149  }
150 
152 
160  bool intersectWith(const line2d<T>& l, vector2d<T>& out, bool checkOnlySegments=true, bool ignoreCoincidentLines=false) const
161  {
162  // Uses the method given at:
163  // http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
164  const f32 commonDenominator = (f32)((l.end.Y - l.start.Y)*(end.X - start.X) -
165  (l.end.X - l.start.X)*(end.Y - start.Y));
166 
167  const f32 numeratorA = (f32)((l.end.X - l.start.X)*(start.Y - l.start.Y) -
168  (l.end.Y - l.start.Y)*(start.X -l.start.X));
169 
170  const f32 numeratorB = (f32)((end.X - start.X)*(start.Y - l.start.Y) -
171  (end.Y - start.Y)*(start.X -l.start.X));
172 
173  if(equals(commonDenominator, 0.f))
174  {
175  // The lines are either coincident or parallel
176  // if both numerators are 0, the lines are coincident
177  if(!ignoreCoincidentLines && equals(numeratorA, 0.f) && equals(numeratorB, 0.f))
178  {
179  // Try and find a common endpoint
180  if(l.start == start || l.end == start)
181  out = start;
182  else if(l.end == end || l.start == end)
183  out = end;
184  // now check if the two segments are disjunct
185  else if (l.start.X>start.X && l.end.X>start.X && l.start.X>end.X && l.end.X>end.X)
186  return false;
187  else if (l.start.Y>start.Y && l.end.Y>start.Y && l.start.Y>end.Y && l.end.Y>end.Y)
188  return false;
189  else if (l.start.X<start.X && l.end.X<start.X && l.start.X<end.X && l.end.X<end.X)
190  return false;
191  else if (l.start.Y<start.Y && l.end.Y<start.Y && l.start.Y<end.Y && l.end.Y<end.Y)
192  return false;
193  // else the lines are overlapping to some extent
194  else
195  {
196  // find the points which are not contributing to the
197  // common part
198  vector2d<T> maxp;
199  vector2d<T> minp;
200  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))
201  maxp=start;
202  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))
203  maxp=end;
204  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))
205  maxp=l.start;
206  else
207  maxp=l.end;
208  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)))
209  minp=start;
210  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)))
211  minp=end;
212  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)))
213  minp=l.start;
214  else
215  minp=l.end;
216 
217  // one line is contained in the other. Pick the center
218  // of the remaining points, which overlap for sure
219  out = core::vector2d<T>();
220  if (start != maxp && start != minp)
221  out += start;
222  if (end != maxp && end != minp)
223  out += end;
224  if (l.start != maxp && l.start != minp)
225  out += l.start;
226  if (l.end != maxp && l.end != minp)
227  out += l.end;
228  out.X = (T)(out.X/2);
229  out.Y = (T)(out.Y/2);
230  }
231 
232  return true; // coincident
233  }
234 
235  return false; // parallel
236  }
237 
238  // Get the point of intersection on this line, checking that
239  // it is within the line segment.
240  const f32 uA = numeratorA / commonDenominator;
241  if (checkOnlySegments)
242  {
243  if(uA < 0.f || uA > 1.f)
244  return false; // Outside the line segment
245 
246  const f32 uB = numeratorB / commonDenominator;
247  if(uB < 0.f || uB > 1.f)
248  return false; // Outside the line segment
249  }
250 
251  // Calculate the intersection point.
252  out.X = (T)(start.X + uA * (end.X - start.X));
253  out.Y = (T)(start.Y + uA * (end.Y - start.Y));
254  return true;
255  }
256 
258 
260  {
261  T len = (T)(1.0 / getLength());
262  return vector2d<T>((end.X - start.X) * len, (end.Y - start.Y) * len);
263  }
264 
266 
268  f64 getAngleWith(const line2d<T>& l) const
269  {
270  vector2d<T> vect = getVector();
271  vector2d<T> vect2 = l.getVector();
272  return vect.getAngleWith(vect2);
273  }
274 
276 
278  T getPointOrientation(const vector2d<T>& point) const
279  {
280  return ( (end.X - start.X) * (point.Y - start.Y) -
281  (point.X - start.X) * (end.Y - start.Y) );
282  }
283 
285 
286  bool isPointOnLine(const vector2d<T>& point) const
287  {
288  T d = getPointOrientation(point);
289  return (d == 0 && point.isBetweenPoints(start, end));
290  }
291 
293 
294  bool isPointBetweenStartAndEnd(const vector2d<T>& point) const
295  {
296  return point.isBetweenPoints(start, end);
297  }
298 
300 
302  vector2d<T> getClosestPoint(const vector2d<T>& point, bool checkOnlySegments=true) const
303  {
304  vector2d<f64> c((f64)(point.X-start.X), (f64)(point.Y- start.Y));
305  vector2d<f64> v((f64)(end.X-start.X), (f64)(end.Y-start.Y));
306  f64 d = v.getLength();
307  if ( d == 0 ) // can't tell much when the line is just a single point
308  return start;
309  v /= d;
310  f64 t = v.dotProduct(c);
311 
312  if ( checkOnlySegments )
313  {
314  if (t < 0) return vector2d<T>((T)start.X, (T)start.Y);
315  if (t > d) return vector2d<T>((T)end.X, (T)end.Y);
316  }
317 
318  v *= t;
319  return vector2d<T>((T)(start.X + v.X), (T)(start.Y + v.Y));
320  }
321 
326 };
327 
328  // partial specialization to optimize <f32> lines (avoiding casts)
329  template <>
330  inline vector2df line2d<irr::f32>::getClosestPoint(const vector2df& point, bool checkOnlySegments) const
331  {
332  vector2df c = point - start;
333  vector2df v = end - start;
334  f32 d = (f32)v.getLength();
335  if ( d == 0 ) // can't tell much when the line is just a single point
336  return start;
337  v /= d;
338  f32 t = v.dotProduct(c);
339 
340  if ( checkOnlySegments )
341  {
342  if (t < 0) return start;
343  if (t > d) return end;
344  }
345 
346  v *= t;
347  return start + v;
348  }
349 
350 
355 
356 } // end namespace core
357 } // end namespace irr
358 
359 #endif
360 
line2d(T xa, T ya, T xb, T yb)
Constructor for line between the two points.
Definition: line2d.h:24
line2d< T > operator-(const vector2d< T > &point) const
Definition: line2d.h:35
vector2d< T > start
Start point of the line.
Definition: line2d.h:323
float f32
32 bit floating point variable.
Definition: irrTypes.h:108
vector2d< T > getClosestPoint(const vector2d< T > &point, bool checkOnlySegments=true) const
Get the closest point on this line to a point.
Definition: line2d.h:302
T Y
Y coordinate of vector.
Definition: vector2d.h:385
bool lineIntersectSegment(const line2d< T > &segment, vector2d< T > &out) const
Definition: line2d.h:141
Everything in the Irrlicht Engine can be found in this namespace.
Definition: aabbox3d.h:12
line2d< s32 > line2di
Typedef for an integer line.
Definition: line2d.h:354
f64 getAngleWith(const vector2d< T > &b) const
Calculates the angle between this vector and another one in degree.
Definition: vector2d.h:253
bool incidentSegments(const line2d< T > &other) const
Definition: line2d.h:98
bool nearlyParallel(const vector2d< T > &other, const T factor=relativeErrorFactor< T >()) const
check if this vector is parallel to another vector
Definition: vector2d.h:131
bool operator!=(const line2d< T > &other) const
Definition: line2d.h:40
double f64
64 bit floating point variable.
Definition: irrTypes.h:112
void setLine(const line2d< T > &line)
Set this line to new line given as parameter.
Definition: line2d.h:49
vector2d< T > getUnitVector() const
Get unit vector of the line.
Definition: line2d.h:259
bool isPointBetweenStartAndEnd(const vector2d< T > &point) const
Check if the given point is between start and end of the line.
Definition: line2d.h:294
vector2d< T > getVector() const
Get the vector of the line.
Definition: line2d.h:68
line2d< T > & operator-=(const vector2d< T > &point)
Definition: line2d.h:36
bool equals(const T a, const T b, const T tolerance=roundingError< T >())
returns if a equals b, taking possible rounding errors into account
Definition: irrMath.h:246
signed int s32
32 bit signed variable.
Definition: irrTypes.h:70
T getPointOrientation(const vector2d< T > &point) const
Tells us if the given point lies to the left, right, or on the line.
Definition: line2d.h:278
void setLine(const vector2d< T > &nstart, const vector2d< T > &nend)
Set this line to new line going through the two points.
Definition: line2d.h:47
T getLength() const
Get length of line.
Definition: line2d.h:53
T getLength() const
Gets the length of the vector.
Definition: vector2d.h:115
line2d< T > operator+(const vector2d< T > &point) const
Definition: line2d.h:32
bool nearlyParallel(const line2d< T > &line, const T factor=relativeErrorFactor< T >()) const
Definition: line2d.h:106
T dotProduct(const vector2d< T > &other) const
Get the dot product of this vector with another.
Definition: vector2d.h:125
line2d< f32 > line2df
Typedef for an f32 line.
Definition: line2d.h:352
bool isPointOnLine(const vector2d< T > &point) const
Check if the given point is a member of the line.
Definition: line2d.h:286
line2d(const vector2d< T > &start, const vector2d< T > &end)
Constructor for line between the two points given as vectors.
Definition: line2d.h:26
bool operator==(const line2d< T > &other) const
Definition: line2d.h:38
line2d()
Default constructor for line going from (0,0) to (1,1).
Definition: line2d.h:22
vector2d< T > fastLinesIntersection(const line2d< T > &l) const
Definition: line2d.h:118
2d vector template class with lots of operators and methods.
Definition: dimension2d.h:16
bool isBetweenPoints(const vector2d< T > &begin, const vector2d< T > &end) const
Returns if this vector interpreted as a point is on a line between two other points.
Definition: vector2d.h:274
f64 getAngleWith(const line2d< T > &l) const
Get angle between this line and given line.
Definition: line2d.h:268
line2d< T > & operator+=(const vector2d< T > &point)
Definition: line2d.h:33
bool intersectWith(const line2d< T > &l, vector2d< T > &out, bool checkOnlySegments=true, bool ignoreCoincidentLines=false) const
Tests if this line intersects with another line.
Definition: line2d.h:160
line2d(const line2d< T > &other)
Copy constructor.
Definition: line2d.h:28
vector2d< T > end
End point of the line.
Definition: line2d.h:325
vector2d< T > getMiddle() const
Get middle of the line.
Definition: line2d.h:61
2D line between two points with intersection methods.
Definition: line2d.h:18
T getLengthSQ() const
Get squared length of the line.
Definition: line2d.h:57
bool intersectAsSegments(const line2d< T > &other) const
Definition: line2d.h:72
void setLine(const T &xa, const T &ya, const T &xb, const T &yb)
Set this line to new line going through the two points.
Definition: line2d.h:45
T X
X coordinate of vector.
Definition: vector2d.h:382