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 16 //! 2D line between two points with intersection methods. 17 template <class T> 18 class line2d 19 { 20 public: 21 //! Default constructor for line going from (0,0) to (1,1). line2d()22 line2d() : start(0,0), end(1,1) {} 23 //! Constructor for line between the two points. line2d(T xa,T ya,T xb,T yb)24 line2d(T xa, T ya, T xb, T yb) : start(xa, ya), end(xb, yb) {} 25 //! Constructor for line between the two points given as vectors. line2d(const vector2d<T> & start,const vector2d<T> & end)26 line2d(const vector2d<T>& start, const vector2d<T>& end) : start(start), end(end) {} 27 //! Copy constructor. line2d(const line2d<T> & other)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 44 //! Set this line to new line going through the two points. setLine(const T & xa,const T & ya,const T & xb,const T & yb)45 void setLine(const T& xa, const T& ya, const T& xb, const T& yb){start.set(xa, ya); end.set(xb, yb);} 46 //! Set this line to new line going through the two points. setLine(const vector2d<T> & nstart,const vector2d<T> & nend)47 void setLine(const vector2d<T>& nstart, const vector2d<T>& nend){start.set(nstart); end.set(nend);} 48 //! Set this line to new line given as parameter. setLine(const line2d<T> & line)49 void setLine(const line2d<T>& line){start.set(line.start); end.set(line.end);} 50 51 //! Get length of line 52 /** \return Length of the line. */ getLength()53 T getLength() const { return start.getDistanceFrom(end); } 54 55 //! Get squared length of the line 56 /** \return Squared length of line. */ getLengthSQ()57 T getLengthSQ() const { return start.getDistanceFromSQ(end); } 58 59 //! Get middle of the line 60 /** \return center of the line. */ getMiddle()61 vector2d<T> getMiddle() const 62 { 63 return (start + end)/(T)2; 64 } 65 66 //! Get the vector of the line. 67 /** \return The vector of the line. */ getVector()68 vector2d<T> getVector() const { return vector2d<T>(end.X - start.X, end.Y - start.Y); } 69 70 //! Tests if this line intersects with another line. 71 /** \param l: Other line to test intersection with. 72 \param checkOnlySegments: Default is to check intersection between the begin and endpoints. 73 When set to false the function will check for the first intersection point when extending the lines. 74 \param out: If there is an intersection, the location of the 75 intersection will be stored in this vector. 76 \return True if there is an intersection, false if not. */ 77 bool intersectWith(const line2d<T>& l, vector2d<T>& out, bool checkOnlySegments=true) const 78 { 79 // Uses the method given at: 80 // http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/ 81 const f32 commonDenominator = (f32)(l.end.Y - l.start.Y)*(end.X - start.X) - 82 (l.end.X - l.start.X)*(end.Y - start.Y); 83 84 const f32 numeratorA = (f32)(l.end.X - l.start.X)*(start.Y - l.start.Y) - 85 (l.end.Y - l.start.Y)*(start.X -l.start.X); 86 87 const f32 numeratorB = (f32)(end.X - start.X)*(start.Y - l.start.Y) - 88 (end.Y - start.Y)*(start.X -l.start.X); 89 90 if(equals(commonDenominator, 0.f)) 91 { 92 // The lines are either coincident or parallel 93 // if both numerators are 0, the lines are coincident 94 if(equals(numeratorA, 0.f) && equals(numeratorB, 0.f)) 95 { 96 // Try and find a common endpoint 97 if(l.start == start || l.end == start) 98 out = start; 99 else if(l.end == end || l.start == end) 100 out = end; 101 // now check if the two segments are disjunct 102 else if (l.start.X>start.X && l.end.X>start.X && l.start.X>end.X && l.end.X>end.X) 103 return false; 104 else if (l.start.Y>start.Y && l.end.Y>start.Y && l.start.Y>end.Y && l.end.Y>end.Y) 105 return false; 106 else if (l.start.X<start.X && l.end.X<start.X && l.start.X<end.X && l.end.X<end.X) 107 return false; 108 else if (l.start.Y<start.Y && l.end.Y<start.Y && l.start.Y<end.Y && l.end.Y<end.Y) 109 return false; 110 // else the lines are overlapping to some extent 111 else 112 { 113 // find the points which are not contributing to the 114 // common part 115 vector2d<T> maxp; 116 vector2d<T> minp; 117 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)) 118 maxp=start; 119 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)) 120 maxp=end; 121 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)) 122 maxp=l.start; 123 else 124 maxp=l.end; 125 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))) 126 minp=start; 127 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))) 128 minp=end; 129 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))) 130 minp=l.start; 131 else 132 minp=l.end; 133 134 // one line is contained in the other. Pick the center 135 // of the remaining points, which overlap for sure 136 out = core::vector2d<T>(); 137 if (start != maxp && start != minp) 138 out += start; 139 if (end != maxp && end != minp) 140 out += end; 141 if (l.start != maxp && l.start != minp) 142 out += l.start; 143 if (l.end != maxp && l.end != minp) 144 out += l.end; 145 out.X = (T)(out.X/2); 146 out.Y = (T)(out.Y/2); 147 } 148 149 return true; // coincident 150 } 151 152 return false; // parallel 153 } 154 155 // Get the point of intersection on this line, checking that 156 // it is within the line segment. 157 const f32 uA = numeratorA / commonDenominator; 158 if(checkOnlySegments && (uA < 0.f || uA > 1.f) ) 159 return false; // Outside the line segment 160 161 const f32 uB = numeratorB / commonDenominator; 162 if(checkOnlySegments && (uB < 0.f || uB > 1.f)) 163 return false; // Outside the line segment 164 165 // Calculate the intersection point. 166 out.X = (T)(start.X + uA * (end.X - start.X)); 167 out.Y = (T)(start.Y + uA * (end.Y - start.Y)); 168 return true; 169 } 170 171 //! Get unit vector of the line. 172 /** \return Unit vector of this line. */ getUnitVector()173 vector2d<T> getUnitVector() const 174 { 175 T len = (T)(1.0 / getLength()); 176 return vector2d<T>((end.X - start.X) * len, (end.Y - start.Y) * len); 177 } 178 179 //! Get angle between this line and given line. 180 /** \param l Other line for test. 181 \return Angle in degrees. */ getAngleWith(const line2d<T> & l)182 f64 getAngleWith(const line2d<T>& l) const 183 { 184 vector2d<T> vect = getVector(); 185 vector2d<T> vect2 = l.getVector(); 186 return vect.getAngleWith(vect2); 187 } 188 189 //! Tells us if the given point lies to the left, right, or on the line. 190 /** \return 0 if the point is on the line 191 <0 if to the left, or >0 if to the right. */ getPointOrientation(const vector2d<T> & point)192 T getPointOrientation(const vector2d<T>& point) const 193 { 194 return ( (end.X - start.X) * (point.Y - start.Y) - 195 (point.X - start.X) * (end.Y - start.Y) ); 196 } 197 198 //! Check if the given point is a member of the line 199 /** \return True if point is between start and end, else false. */ isPointOnLine(const vector2d<T> & point)200 bool isPointOnLine(const vector2d<T>& point) const 201 { 202 T d = getPointOrientation(point); 203 return (d == 0 && point.isBetweenPoints(start, end)); 204 } 205 206 //! Check if the given point is between start and end of the line. 207 /** Assumes that the point is already somewhere on the line. */ isPointBetweenStartAndEnd(const vector2d<T> & point)208 bool isPointBetweenStartAndEnd(const vector2d<T>& point) const 209 { 210 return point.isBetweenPoints(start, end); 211 } 212 213 //! Get the closest point on this line to a point 214 /** \param point: Starting search at this point 215 \param checkOnlySegments: Default (true) is to return a point on the line-segment (between begin and end) of the line. 216 When set to false the function will check for the first the closest point on the the line even when outside the segment. */ 217 vector2d<T> getClosestPoint(const vector2d<T>& point, bool checkOnlySegments=true) const 218 { 219 vector2d<f64> c((f64)(point.X-start.X), (f64)(point.Y- start.Y)); 220 vector2d<f64> v((f64)(end.X-start.X), (f64)(end.Y-start.Y)); 221 f64 d = v.getLength(); 222 if ( d == 0 ) // can't tell much when the line is just a single point 223 return start; 224 v /= d; 225 f64 t = v.dotProduct(c); 226 227 if ( checkOnlySegments ) 228 { 229 if (t < 0) return vector2d<T>((T)start.X, (T)start.Y); 230 if (t > d) return vector2d<T>((T)end.X, (T)end.Y); 231 } 232 233 v *= t; 234 return vector2d<T>((T)(start.X + v.X), (T)(start.Y + v.Y)); 235 } 236 237 //! Start point of the line. 238 vector2d<T> start; 239 //! End point of the line. 240 vector2d<T> end; 241 }; 242 243 // partial specialization to optimize <f32> lines (avoiding casts) 244 template <> getClosestPoint(const vector2df & point,bool checkOnlySegments)245 inline vector2df line2d<irr::f32>::getClosestPoint(const vector2df& point, bool checkOnlySegments) const 246 { 247 vector2df c = point - start; 248 vector2df v = end - start; 249 f32 d = (f32)v.getLength(); 250 if ( d == 0 ) // can't tell much when the line is just a single point 251 return start; 252 v /= d; 253 f32 t = v.dotProduct(c); 254 255 if ( checkOnlySegments ) 256 { 257 if (t < 0) return start; 258 if (t > d) return end; 259 } 260 261 v *= t; 262 return start + v; 263 } 264 265 266 //! Typedef for an f32 line. 267 typedef line2d<f32> line2df; 268 //! Typedef for an integer line. 269 typedef line2d<s32> line2di; 270 271 } // end namespace core 272 } // end namespace irr 273 274 #endif 275 276