Home | Namespaces | Hierarchy | Alphabetical List | Class list | Files | Namespace Members | Class members | File members | Tutorials

line2d.h

Go to the documentation of this file.
00001 // Copyright (C) 2002-2010 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 
00075                 bool intersectWith(const line2d<T>& l, vector2d<T>& out) const
00076                 {
00077                         // Uses the method given at:
00078                         // http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/ 
00079                         const f32 commonDenominator = (l.end.Y - l.start.Y)*(end.X - start.X) -
00080                                                                                         (l.end.X - l.start.X)*(end.Y - start.Y);
00081 
00082                         const f32 numeratorA = (l.end.X - l.start.X)*(start.Y - l.start.Y) -
00083                                                                                         (l.end.Y - l.start.Y)*(start.X -l.start.X);
00084 
00085                         const f32 numeratorB = (end.X - start.X)*(start.Y - l.start.Y) -
00086                                                                                         (end.Y - start.Y)*(start.X -l.start.X); 
00087 
00088                         if(equals(commonDenominator, 0.f))
00089                         { 
00090                                 // The lines are either coincident or parallel
00091                                 // if both numerators are 0, the lines are coincident
00092                                 if(equals(numeratorA, 0.f) && equals(numeratorB, 0.f))
00093                                 {
00094                                         // Try and find a common endpoint
00095                                         if(l.start == start || l.end == start)
00096                                                 out = start;
00097                                         else if(l.end == end || l.start == end)
00098                                                 out = end;
00099                                         // now check if the two segments are disjunct
00100                                         else if (l.start.X>start.X && l.end.X>start.X && l.start.X>end.X && l.end.X>end.X)
00101                                                 return false;
00102                                         else if (l.start.Y>start.Y && l.end.Y>start.Y && l.start.Y>end.Y && l.end.Y>end.Y)
00103                                                 return false;
00104                                         else if (l.start.X<start.X && l.end.X<start.X && l.start.X<end.X && l.end.X<end.X)
00105                                                 return false;
00106                                         else if (l.start.Y<start.Y && l.end.Y<start.Y && l.start.Y<end.Y && l.end.Y<end.Y)
00107                                                 return false;
00108                                         // else the lines are overlapping to some extent
00109                                         else
00110                                         {
00111                                                 // find the points which are not contributing to the
00112                                                 // common part
00113                                                 vector2d<T> maxp;
00114                                                 vector2d<T> minp;
00115                                                 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))
00116                                                         maxp=start;
00117                                                 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))
00118                                                         maxp=end;
00119                                                 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))
00120                                                         maxp=l.start;
00121                                                 else
00122                                                         maxp=l.end;
00123                                                 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)))
00124                                                         minp=start;
00125                                                 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)))
00126                                                         minp=end;
00127                                                 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)))
00128                                                         minp=l.start;
00129                                                 else
00130                                                         minp=l.end;
00131 
00132                                                 // one line is contained in the other. Pick the center
00133                                                 // of the remaining points, which overlap for sure
00134                                                 out = core::vector2d<T>();
00135                                                 if (start != maxp && start != minp)
00136                                                         out += start;
00137                                                 if (end != maxp && end != minp)
00138                                                         out += end;
00139                                                 if (l.start != maxp && l.start != minp)
00140                                                         out += l.start;
00141                                                 if (l.end != maxp && l.end != minp)
00142                                                         out += l.end;
00143                                                 out *= 0.5f;
00144                                         }
00145 
00146                                         return true; // coincident
00147                                 }
00148 
00149                                 return false; // parallel
00150                         }
00151 
00152                         // Get the point of intersection on this line, checking that
00153                         // it is within the line segment.
00154                         const f32 uA = numeratorA / commonDenominator;
00155                         if(uA < 0.f || uA > 1.f)
00156                                 return false; // Outside the line segment
00157 
00158                         const f32 uB = numeratorB / commonDenominator;
00159                         if(uB < 0.f || uB > 1.f)
00160                                 return false; // Outside the line segment
00161 
00162                         // Calculate the intersection point.
00163                         out.X = start.X + uA * (end.X - start.X);
00164                         out.Y = start.Y + uA * (end.Y - start.Y);
00165                         return true; 
00166                 }
00167 
00169 
00170                 vector2d<T> getUnitVector() const
00171                 {
00172                         T len = (T)(1.0 / getLength());
00173                         return vector2d<T>((end.X - start.X) * len, (end.Y - start.Y) * len);
00174                 }
00175 
00177 
00179                 f64 getAngleWith(const line2d<T>& l) const
00180                 {
00181                         vector2d<T> vect = getVector();
00182                         vector2d<T> vect2 = l.getVector();
00183                         return vect.getAngleWith(vect2);
00184                 }
00185 
00187 
00189                 T getPointOrientation(const vector2d<T>& point) const
00190                 {
00191                         return ( (end.X - start.X) * (point.Y - start.Y) -
00192                                         (point.X - start.X) * (end.Y - start.Y) );
00193                 }
00194 
00196 
00197                 bool isPointOnLine(const vector2d<T>& point) const
00198                 {
00199                         T d = getPointOrientation(point);
00200                         return (d == 0 && point.isBetweenPoints(start, end));
00201                 }
00202 
00204 
00205                 bool isPointBetweenStartAndEnd(const vector2d<T>& point) const
00206                 {
00207                         return point.isBetweenPoints(start, end);
00208                 }
00209 
00211                 vector2d<T> getClosestPoint(const vector2d<T>& point) const
00212                 {
00213                         vector2d<T> c = point - start;
00214                         vector2d<T> v = end - start;
00215                         T d = (T)v.getLength();
00216                         v /= d;
00217                         T t = v.dotProduct(c);
00218 
00219                         if (t < (T)0.0) return start;
00220                         if (t > d) return end;
00221 
00222                         v *= t;
00223                         return start + v;
00224                 }
00225 
00227                 vector2d<T> start;
00229                 vector2d<T> end;
00230 };
00231 
00233         typedef line2d<f32> line2df;
00235         typedef line2d<s32> line2di;
00236 
00237 } // end namespace core
00238 } // end namespace irr
00239 
00240 #endif
00241 

The Irrlicht Engine
The Irrlicht Engine Documentation © 2003-2010 by Nikolaus Gebhardt. Generated on Sun Oct 24 12:41:57 2010 by Doxygen (1.6.2)