Home | Namespaces | Hierarchy | Alphabetical List | Class list | Files | Namespace Members | Class members | File members | Tutorials
line2d.h
Go to the documentation of this file.
1 // Copyright (C) 2002-2010 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) {}
26  line2d(const vector2d<T>& start, const vector2d<T>& end) : start(start), end(end) {}
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  f64 getLength() const { return start.getDistanceFrom(end); }
54 
56 
57  T getLengthSQ() const { return start.getDistanceFromSQ(end); }
58 
60 
62  {
63  return (start + end) * (T)0.5;
64  }
65 
67 
68  vector2d<T> getVector() const { return vector2d<T>(end.X - start.X, end.Y - start.Y); }
69 
71 
75  bool intersectWith(const line2d<T>& l, vector2d<T>& out) const
76  {
77  // Uses the method given at:
78  // http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/
79  const f32 commonDenominator = (f32)((l.end.Y - l.start.Y)*(end.X - start.X) -
80  (l.end.X - l.start.X)*(end.Y - start.Y));
81 
82  const f32 numeratorA = (f32)((l.end.X - l.start.X)*(start.Y - l.start.Y) -
83  (l.end.Y - l.start.Y)*(start.X -l.start.X));
84 
85  const f32 numeratorB = (f32)((end.X - start.X)*(start.Y - l.start.Y) -
86  (end.Y - start.Y)*(start.X -l.start.X));
87 
88  if(equals(commonDenominator, 0.f))
89  {
90  // The lines are either coincident or parallel
91  // if both numerators are 0, the lines are coincident
92  if(equals(numeratorA, 0.f) && equals(numeratorB, 0.f))
93  {
94  // Try and find a common endpoint
95  if(l.start == start || l.end == start)
96  out = start;
97  else if(l.end == end || l.start == end)
98  out = end;
99  // now check if the two segments are disjunct
100  else if (l.start.X>start.X && l.end.X>start.X && l.start.X>end.X && l.end.X>end.X)
101  return false;
102  else if (l.start.Y>start.Y && l.end.Y>start.Y && l.start.Y>end.Y && l.end.Y>end.Y)
103  return false;
104  else if (l.start.X<start.X && l.end.X<start.X && l.start.X<end.X && l.end.X<end.X)
105  return false;
106  else if (l.start.Y<start.Y && l.end.Y<start.Y && l.start.Y<end.Y && l.end.Y<end.Y)
107  return false;
108  // else the lines are overlapping to some extent
109  else
110  {
111  // find the points which are not contributing to the
112  // common part
113  vector2d<T> maxp;
114  vector2d<T> minp;
115  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))
116  maxp=start;
117  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))
118  maxp=end;
119  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))
120  maxp=l.start;
121  else
122  maxp=l.end;
123  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)))
124  minp=start;
125  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)))
126  minp=end;
127  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)))
128  minp=l.start;
129  else
130  minp=l.end;
131 
132  // one line is contained in the other. Pick the center
133  // of the remaining points, which overlap for sure
134  out = core::vector2d<T>();
135  if (start != maxp && start != minp)
136  out += start;
137  if (end != maxp && end != minp)
138  out += end;
139  if (l.start != maxp && l.start != minp)
140  out += l.start;
141  if (l.end != maxp && l.end != minp)
142  out += l.end;
143  out.X = (T)(out.X*0.5f);
144  out.Y = (T)(out.Y*0.5f);
145  }
146 
147  return true; // coincident
148  }
149 
150  return false; // parallel
151  }
152 
153  // Get the point of intersection on this line, checking that
154  // it is within the line segment.
155  const f32 uA = numeratorA / commonDenominator;
156  if(uA < 0.f || uA > 1.f)
157  return false; // Outside the line segment
158 
159  const f32 uB = numeratorB / commonDenominator;
160  if(uB < 0.f || uB > 1.f)
161  return false; // Outside the line segment
162 
163  // Calculate the intersection point.
164  out.X = (T)(start.X + uA * (end.X - start.X));
165  out.Y = (T)(start.Y + uA * (end.Y - start.Y));
166  return true;
167  }
168 
170 
172  {
173  T len = (T)(1.0 / getLength());
174  return vector2d<T>((end.X - start.X) * len, (end.Y - start.Y) * len);
175  }
176 
178 
180  f64 getAngleWith(const line2d<T>& l) const
181  {
182  vector2d<T> vect = getVector();
183  vector2d<T> vect2 = l.getVector();
184  return vect.getAngleWith(vect2);
185  }
186 
188 
190  T getPointOrientation(const vector2d<T>& point) const
191  {
192  return ( (end.X - start.X) * (point.Y - start.Y) -
193  (point.X - start.X) * (end.Y - start.Y) );
194  }
195 
197 
198  bool isPointOnLine(const vector2d<T>& point) const
199  {
200  T d = getPointOrientation(point);
201  return (d == 0 && point.isBetweenPoints(start, end));
202  }
203 
205 
206  bool isPointBetweenStartAndEnd(const vector2d<T>& point) const
207  {
208  return point.isBetweenPoints(start, end);
209  }
210 
213  {
214  vector2d<T> c = point - start;
215  vector2d<T> v = end - start;
216  T d = (T)v.getLength();
217  v /= d;
218  T t = v.dotProduct(c);
219 
220  if (t < (T)0.0) return start;
221  if (t > d) return end;
222 
223  v *= t;
224  return start + v;
225  }
226 
231 };
232 
237 
238 } // end namespace core
239 } // end namespace irr
240 
241 #endif
242 

The Irrlicht Engine
The Irrlicht Engine Documentation © 2003-2010 by Nikolaus Gebhardt. Generated on Tue Jun 5 2012 17:57:14 by Doxygen (1.8.1)