 |
+
+
+
+ Irrlicht 3D Engine
+
+
+
+ |
+
+
+
+
+
+
+
+
+
+
+ 
+
+ |
+
+
+
00001 // Copyright (C) 2002-2012 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 T 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)2; +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 = (f32)(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 = (f32)(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 = (f32)(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.X = (T)(out.X/2); +00146 out.Y = (T)(out.Y/2); +00147 } +00148 +00149 return true; // coincident +00150 } +00151 +00152 return false; // parallel +00153 } +00154 +00155 // Get the point of intersection on this line, checking that +00156 // it is within the line segment. +00157 const f32 uA = numeratorA / commonDenominator; +00158 if(checkOnlySegments && (uA < 0.f || uA > 1.f) ) +00159 return false; // Outside the line segment +00160 +00161 const f32 uB = numeratorB / commonDenominator; +00162 if(checkOnlySegments && (uB < 0.f || uB > 1.f)) +00163 return false; // Outside the line segment +00164 +00165 // Calculate the intersection point. +00166 out.X = (T)(start.X + uA * (end.X - start.X)); +00167 out.Y = (T)(start.Y + uA * (end.Y - start.Y)); +00168 return true; +00169 } +00170 +00172 +00173 vector2d<T> getUnitVector() const +00174 { +00175 T len = (T)(1.0 / getLength()); +00176 return vector2d<T>((end.X - start.X) * len, (end.Y - start.Y) * len); +00177 } +00178 +00180 +00182 f64 getAngleWith(const line2d<T>& l) const +00183 { +00184 vector2d<T> vect = getVector(); +00185 vector2d<T> vect2 = l.getVector(); +00186 return vect.getAngleWith(vect2); +00187 } +00188 +00190 +00192 T getPointOrientation(const vector2d<T>& point) const +00193 { +00194 return ( (end.X - start.X) * (point.Y - start.Y) - +00195 (point.X - start.X) * (end.Y - start.Y) ); +00196 } +00197 +00199 +00200 bool isPointOnLine(const vector2d<T>& point) const +00201 { +00202 T d = getPointOrientation(point); +00203 return (d == 0 && point.isBetweenPoints(start, end)); +00204 } +00205 +00207 +00208 bool isPointBetweenStartAndEnd(const vector2d<T>& point) const +00209 { +00210 return point.isBetweenPoints(start, end); +00211 } +00212 +00214 +00216 vector2d<T> getClosestPoint(const vector2d<T>& point, bool checkOnlySegments=true) const +00217 { +00218 vector2d<f64> c((f64)(point.X-start.X), (f64)(point.Y- start.Y)); +00219 vector2d<f64> v((f64)(end.X-start.X), (f64)(end.Y-start.Y)); +00220 f64 d = v.getLength(); +00221 if ( d == 0 ) // can't tell much when the line is just a single point +00222 return start; +00223 v /= d; +00224 f64 t = v.dotProduct(c); +00225 +00226 if ( checkOnlySegments ) +00227 { +00228 if (t < 0) return vector2d<T>((T)start.X, (T)start.Y); +00229 if (t > d) return vector2d<T>((T)end.X, (T)end.Y); +00230 } +00231 +00232 v *= t; +00233 return vector2d<T>((T)(start.X + v.X), (T)(start.Y + v.Y)); +00234 } +00235 +00237 vector2d<T> start; +00239 vector2d<T> end; +00240 }; +00241 +00242 // partial specialization to optimize <f32> lines (avoiding casts) +00243 template <> +00244 inline vector2df line2d<irr::f32>::getClosestPoint(const vector2df& point, bool checkOnlySegments) const +00245 { +00246 vector2df c = point - start; +00247 vector2df v = end - start; +00248 f32 d = (f32)v.getLength(); +00249 if ( d == 0 ) // can't tell much when the line is just a single point +00250 return start; +00251 v /= d; +00252 f32 t = v.dotProduct(c); +00253 +00254 if ( checkOnlySegments ) +00255 { +00256 if (t < 0) return start; +00257 if (t > d) return end; +00258 } +00259 +00260 v *= t; +00261 return start + v; +00262 } +00263 +00264 +00266 typedef line2d<f32> line2df; +00268 typedef line2d<s32> line2di; +00269 +00270 } // end namespace core +00271 } // end namespace irr +00272 +00273 #endif +00274 +