|
IrrlichtEngine
|
00001 // Copyright (C) 2002-2011 Nikolaus Gebhardt 00002 // This file is part of the "Irrlicht Engine". 00003 // For conditions of distribution and use, see copyright notice in irrlicht.h 00004 00005 #ifndef __IRR_LINE_2D_H_INCLUDED__ 00006 #define __IRR_LINE_2D_H_INCLUDED__ 00007 00008 #include "irrTypes.h" 00009 #include "vector2d.h" 00010 00011 namespace irr 00012 { 00013 namespace core 00014 { 00015 00017 template <class T> 00018 class line2d 00019 { 00020 public: 00022 line2d() : start(0,0), end(1,1) {} 00024 line2d(T xa, T ya, T xb, T yb) : start(xa, ya), end(xb, yb) {} 00026 line2d(const vector2d<T>& start, const vector2d<T>& end) : start(start), end(end) {} 00028 line2d(const line2d<T>& other) : start(other.start), end(other.end) {} 00029 00030 // operators 00031 00032 line2d<T> operator+(const vector2d<T>& point) const { return line2d<T>(start + point, end + point); } 00033 line2d<T>& operator+=(const vector2d<T>& point) { start += point; end += point; return *this; } 00034 00035 line2d<T> operator-(const vector2d<T>& point) const { return line2d<T>(start - point, end - point); } 00036 line2d<T>& operator-=(const vector2d<T>& point) { start -= point; end -= point; return *this; } 00037 00038 bool operator==(const line2d<T>& other) const 00039 { return (start==other.start && end==other.end) || (end==other.start && start==other.end);} 00040 bool operator!=(const line2d<T>& other) const 00041 { return !(start==other.start && end==other.end) || (end==other.start && start==other.end);} 00042 00043 // functions 00045 void setLine(const T& xa, const T& ya, const T& xb, const T& yb){start.set(xa, ya); end.set(xb, yb);} 00047 void setLine(const vector2d<T>& nstart, const vector2d<T>& nend){start.set(nstart); end.set(nend);} 00049 void setLine(const line2d<T>& line){start.set(line.start); end.set(line.end);} 00050 00052 00053 f64 getLength() const { return start.getDistanceFrom(end); } 00054 00056 00057 T getLengthSQ() const { return start.getDistanceFromSQ(end); } 00058 00060 00061 vector2d<T> getMiddle() const 00062 { 00063 return (start + end) * (T)0.5; 00064 } 00065 00067 00068 vector2d<T> getVector() const { return vector2d<T>(end.X - start.X, end.Y - start.Y); } 00069 00071 00077 bool intersectWith(const line2d<T>& l, vector2d<T>& out, bool checkOnlySegments=true) const 00078 { 00079 // Uses the method given at: 00080 // http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/ 00081 const f32 commonDenominator = (l.end.Y - l.start.Y)*(end.X - start.X) - 00082 (l.end.X - l.start.X)*(end.Y - start.Y); 00083 00084 const f32 numeratorA = (l.end.X - l.start.X)*(start.Y - l.start.Y) - 00085 (l.end.Y - l.start.Y)*(start.X -l.start.X); 00086 00087 const f32 numeratorB = (end.X - start.X)*(start.Y - l.start.Y) - 00088 (end.Y - start.Y)*(start.X -l.start.X); 00089 00090 if(equals(commonDenominator, 0.f)) 00091 { 00092 // The lines are either coincident or parallel 00093 // if both numerators are 0, the lines are coincident 00094 if(equals(numeratorA, 0.f) && equals(numeratorB, 0.f)) 00095 { 00096 // Try and find a common endpoint 00097 if(l.start == start || l.end == start) 00098 out = start; 00099 else if(l.end == end || l.start == end) 00100 out = end; 00101 // now check if the two segments are disjunct 00102 else if (l.start.X>start.X && l.end.X>start.X && l.start.X>end.X && l.end.X>end.X) 00103 return false; 00104 else if (l.start.Y>start.Y && l.end.Y>start.Y && l.start.Y>end.Y && l.end.Y>end.Y) 00105 return false; 00106 else if (l.start.X<start.X && l.end.X<start.X && l.start.X<end.X && l.end.X<end.X) 00107 return false; 00108 else if (l.start.Y<start.Y && l.end.Y<start.Y && l.start.Y<end.Y && l.end.Y<end.Y) 00109 return false; 00110 // else the lines are overlapping to some extent 00111 else 00112 { 00113 // find the points which are not contributing to the 00114 // common part 00115 vector2d<T> maxp; 00116 vector2d<T> minp; 00117 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)) 00118 maxp=start; 00119 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)) 00120 maxp=end; 00121 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)) 00122 maxp=l.start; 00123 else 00124 maxp=l.end; 00125 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))) 00126 minp=start; 00127 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))) 00128 minp=end; 00129 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))) 00130 minp=l.start; 00131 else 00132 minp=l.end; 00133 00134 // one line is contained in the other. Pick the center 00135 // of the remaining points, which overlap for sure 00136 out = core::vector2d<T>(); 00137 if (start != maxp && start != minp) 00138 out += start; 00139 if (end != maxp && end != minp) 00140 out += end; 00141 if (l.start != maxp && l.start != minp) 00142 out += l.start; 00143 if (l.end != maxp && l.end != minp) 00144 out += l.end; 00145 out *= 0.5f; 00146 } 00147 00148 return true; // coincident 00149 } 00150 00151 return false; // parallel 00152 } 00153 00154 // Get the point of intersection on this line, checking that 00155 // it is within the line segment. 00156 const f32 uA = numeratorA / commonDenominator; 00157 if(checkOnlySegments && (uA < 0.f || uA > 1.f) ) 00158 return false; // Outside the line segment 00159 00160 const f32 uB = numeratorB / commonDenominator; 00161 if(checkOnlySegments && (uB < 0.f || uB > 1.f)) 00162 return false; // Outside the line segment 00163 00164 // Calculate the intersection point. 00165 out.X = start.X + uA * (end.X - start.X); 00166 out.Y = start.Y + uA * (end.Y - start.Y); 00167 return true; 00168 } 00169 00171 00172 vector2d<T> getUnitVector() const 00173 { 00174 T len = (T)(1.0 / getLength()); 00175 return vector2d<T>((end.X - start.X) * len, (end.Y - start.Y) * len); 00176 } 00177 00179 00181 f64 getAngleWith(const line2d<T>& l) const 00182 { 00183 vector2d<T> vect = getVector(); 00184 vector2d<T> vect2 = l.getVector(); 00185 return vect.getAngleWith(vect2); 00186 } 00187 00189 00191 T getPointOrientation(const vector2d<T>& point) const 00192 { 00193 return ( (end.X - start.X) * (point.Y - start.Y) - 00194 (point.X - start.X) * (end.Y - start.Y) ); 00195 } 00196 00198 00199 bool isPointOnLine(const vector2d<T>& point) const 00200 { 00201 T d = getPointOrientation(point); 00202 return (d == 0 && point.isBetweenPoints(start, end)); 00203 } 00204 00206 00207 bool isPointBetweenStartAndEnd(const vector2d<T>& point) const 00208 { 00209 return point.isBetweenPoints(start, end); 00210 } 00211 00213 vector2d<T> getClosestPoint(const vector2d<T>& point) const 00214 { 00215 vector2d<T> c = point - start; 00216 vector2d<T> v = end - start; 00217 T d = (T)v.getLength(); 00218 v /= d; 00219 T t = v.dotProduct(c); 00220 00221 if (t < (T)0.0) return start; 00222 if (t > d) return end; 00223 00224 v *= t; 00225 return start + v; 00226 } 00227 00229 vector2d<T> start; 00231 vector2d<T> end; 00232 }; 00233 00235 typedef line2d<f32> line2df; 00237 typedef line2d<s32> line2di; 00238 00239 } // end namespace core 00240 } // end namespace irr 00241 00242 #endif 00243