include/line2d.h

   1 // Copyright (C) 2002-2012 Nikolaus Gebhardt\r
   2 // This file is part of the "Irrlicht Engine".\r
   3 // For conditions of distribution and use, see copyright notice in irrlicht.h\r
   4 \r
   5 #ifndef __IRR_LINE_2D_H_INCLUDED__\r
   6 #define __IRR_LINE_2D_H_INCLUDED__\r
   7 \r
   8 #include "irrTypes.h"\r
   9 #include "vector2d.h"\r
  10 \r
  11 namespace irr\r
  12 {\r
  13 namespace core\r
  14 {\r
  15 \r
  16 //! 2D line between two points with intersection methods.\r
  17 template <class T>\r
  18 class line2d\r
  19 {\r
  20         public:\r
  21                 //! Default constructor for line going from (0,0) to (1,1).\r
  22                 line2d() : start(0,0), end(1,1) {}\r
  23                 //! Constructor for line between the two points.\r
  24                 line2d(T xa, T ya, T xb, T yb) : start(xa, ya), end(xb, yb) {}\r
  25                 //! Constructor for line between the two points given as vectors.\r
  26                 line2d(const vector2d<T>& start, const vector2d<T>& end) : start(start), end(end) {}\r
  27 \r
  28                 // operators\r
  29 \r
  30                 line2d<T> operator+(const vector2d<T>& point) const { return line2d<T>(start + point, end + point); }\r
  31                 line2d<T>& operator+=(const vector2d<T>& point) { start += point; end += point; return *this; }\r
  32 \r
  33                 line2d<T> operator-(const vector2d<T>& point) const { return line2d<T>(start - point, end - point); }\r
  34                 line2d<T>& operator-=(const vector2d<T>& point) { start -= point; end -= point; return *this; }\r
  35 \r
  36                 bool operator==(const line2d<T>& other) const\r
  37                 { return (start==other.start && end==other.end) || (end==other.start && start==other.end);}\r
  38                 bool operator!=(const line2d<T>& other) const\r
  39                 { return !(start==other.start && end==other.end) || (end==other.start && start==other.end);}\r
  40 \r
  41                 // functions\r
  42                 //! Set this line to new line going through the two points.\r
  43                 void setLine(const T& xa, const T& ya, const T& xb, const T& yb){start.set(xa, ya); end.set(xb, yb);}\r
  44                 //! Set this line to new line going through the two points.\r
  45                 void setLine(const vector2d<T>& nstart, const vector2d<T>& nend){start.set(nstart); end.set(nend);}\r
  46                 //! Set this line to new line given as parameter.\r
  47                 void setLine(const line2d<T>& line){start.set(line.start); end.set(line.end);}\r
  48 \r
  49                 //! Get length of line\r
  50                 /** \return Length of the line. */\r
  51                 T getLength() const { return start.getDistanceFrom(end); }\r
  52 \r
  53                 //! Get squared length of the line\r
  54                 /** \return Squared length of line. */\r
  55                 T getLengthSQ() const { return start.getDistanceFromSQ(end); }\r
  56 \r
  57                 //! Get middle of the line\r
  58                 /** \return center of the line. */\r
  59                 vector2d<T> getMiddle() const\r
  60                 {\r
  61                         return (start + end)/(T)2;\r
  62                 }\r
  63 \r
  64                 //! Get the vector of the line.\r
  65                 /** \return The vector of the line. */\r
  66                 vector2d<T> getVector() const { return vector2d<T>( end.X - start.X, end.Y - start.Y); }\r
  67 \r
  68                 /*! Check if this segment intersects another segment,\r
  69                         or if segments are coincindent (colinear). */\r
  70                 bool intersectAsSegments( const line2d<T>& other) const\r
  71                 {\r
  72                         // Taken from:\r
  73                         // http://www.geeksforgeeks.org/check-if-two-given-line-segments-intersect/\r
  74 \r
  75                         // Find the four orientations needed for general and\r
  76                         // special cases\r
  77                         s32 o1 = start.checkOrientation( end, other.start);\r
  78                         s32 o2 = start.checkOrientation( end, other.end);\r
  79                         s32 o3 = other.start.checkOrientation( other.end, start);\r
  80                         s32 o4 = other.start.checkOrientation( other.end, end);\r
  81 \r
  82                         // General case\r
  83                         if (o1 != o2 && o3 != o4)\r
  84                                 return true;\r
  85 \r
  86                         // Special Cases to check if segments are coolinear\r
  87                         if (o1 == 0 && other.start.isBetweenPoints( start, end)) return true;\r
  88                         if (o2 == 0 && other.end.isBetweenPoints( start, end)) return true;\r
  89                         if (o3 == 0 && start.isBetweenPoints( other.start, other.end)) return true;\r
  90                         if (o4 == 0 && end.isBetweenPoints( other.start, other.end)) return true;\r
  91 \r
  92                         return false; // Doesn't fall in any of the above cases\r
  93                 }\r
  94 \r
  95                 /*! Check if 2 segments are incident (intersects in exactly 1 point).*/\r
  96                 bool incidentSegments( const line2d<T>& other) const\r
  97                 {\r
  98                         return \r
  99                                 start.checkOrientation( end, other.start) != start.checkOrientation( end, other.end)\r
 100                         &&  other.start.checkOrientation( other.end, start) != other.start.checkOrientation( other.end, end);\r
 101                 }\r
 102 \r
 103                 /*! Check if 2 lines/segments are parallel or nearly parallel.*/ \r
 104                 bool nearlyParallel( const line2d<T>& line, const T factor = relativeErrorFactor<T>()) const\r
 105                 {\r
 106                         const vector2d<T> a = getVector();\r
 107                         const vector2d<T> b = line.getVector();\r
 108 \r
 109                         return a.nearlyParallel( b, factor);\r
 110                 }\r
 111 \r
 112                 /*! returns a intersection point of 2 lines (if lines are not parallel). Behaviour\r
 113                 undefined if lines are parallel or coincident. \r
 114                 It's on optimized intersectWith with checkOnlySegments=false and ignoreCoincidentLines=true\r
 115                 */\r
 116                 vector2d<T> fastLinesIntersection( const line2d<T>& l) const\r
 117                 {\r
 118                         const f32 commonDenominator = (f32)((l.end.Y - l.start.Y)*(end.X - start.X) -\r
 119                                 (l.end.X - l.start.X)*(end.Y - start.Y));\r
 120                         \r
 121                         if ( commonDenominator != 0.f )\r
 122                         {\r
 123                                 const f32 numeratorA = (f32)((l.end.X - l.start.X)*(start.Y - l.start.Y) -\r
 124                                         (l.end.Y - l.start.Y)*(start.X - l.start.X));\r
 125 \r
 126                                 const f32 uA = numeratorA / commonDenominator;\r
 127 \r
 128                                 // Calculate the intersection point.\r
 129                                 return vector2d<T> (\r
 130                                         (T)(start.X + uA * (end.X - start.X)), \r
 131                                         (T)(start.Y + uA * (end.Y - start.Y))\r
 132                                         );\r
 133                         }\r
 134                         else\r
 135                                 return l.start;\r
 136                 }\r
 137 \r
 138                 /*! Check if this line intersect a segment. The eventual intersection point is returned in "out".*/\r
 139                 bool lineIntersectSegment( const line2d<T>& segment, vector2d<T> & out) const\r
 140                 {\r
 141                         if (nearlyParallel( segment))\r
 142                                 return false;\r
 143 \r
 144                         out = fastLinesIntersection( segment);\r
 145 \r
 146                         return out.isBetweenPoints( segment.start, segment.end);\r
 147                 }\r
 148 \r
 149                 //! Tests if this line intersects with another line.\r
 150                 /** \param l: Other line to test intersection with.\r
 151                 \param checkOnlySegments: Default is to check intersection between the begin and endpoints.\r
 152                 When set to false the function will check for the first intersection point when extending the lines.\r
 153                 \param out: If there is an intersection, the location of the\r
 154                 intersection will be stored in this vector.\r
 155                 \param ignoreCoincidentLines: When true coincident lines (lines above each other) are never considered as intersecting.\r
 156                 When false the center of the overlapping part is returned.\r
 157                 \return True if there is an intersection, false if not. */\r
 158                 bool intersectWith(const line2d<T>& l, vector2d<T>& out, bool checkOnlySegments=true, bool ignoreCoincidentLines=false) const\r
 159                 {\r
 160                         // Uses the method given at:\r
 161                         // http://local.wasp.uwa.edu.au/~pbourke/geometry/lineline2d/\r
 162                         const f32 commonDenominator = (f32)((l.end.Y - l.start.Y)*(end.X - start.X) -\r
 163                                                                                         (l.end.X - l.start.X)*(end.Y - start.Y));\r
 164 \r
 165                         const f32 numeratorA = (f32)((l.end.X - l.start.X)*(start.Y - l.start.Y) -\r
 166                                                                                         (l.end.Y - l.start.Y)*(start.X -l.start.X));\r
 167 \r
 168                         const f32 numeratorB = (f32)((end.X - start.X)*(start.Y - l.start.Y) -\r
 169                                                                                         (end.Y - start.Y)*(start.X -l.start.X));\r
 170 \r
 171                         if(equals(commonDenominator, 0.f))\r
 172                         {\r
 173                                 // The lines are either coincident or parallel\r
 174                                 // if both numerators are 0, the lines are coincident\r
 175                                 if(!ignoreCoincidentLines && equals(numeratorA, 0.f) && equals(numeratorB, 0.f))\r
 176                                 {\r
 177                                         // Try and find a common endpoint\r
 178                                         if(l.start == start || l.end == start)\r
 179                                                 out = start;\r
 180                                         else if(l.end == end || l.start == end)\r
 181                                                 out = end;\r
 182                                         // now check if the two segments are disjunct\r
 183                                         else if (l.start.X>start.X && l.end.X>start.X && l.start.X>end.X && l.end.X>end.X)\r
 184                                                 return false;\r
 185                                         else if (l.start.Y>start.Y && l.end.Y>start.Y && l.start.Y>end.Y && l.end.Y>end.Y)\r
 186                                                 return false;\r
 187                                         else if (l.start.X<start.X && l.end.X<start.X && l.start.X<end.X && l.end.X<end.X)\r
 188                                                 return false;\r
 189                                         else if (l.start.Y<start.Y && l.end.Y<start.Y && l.start.Y<end.Y && l.end.Y<end.Y)\r
 190                                                 return false;\r
 191                                         // else the lines are overlapping to some extent\r
 192                                         else\r
 193                                         {\r
 194                                                 // find the points which are not contributing to the\r
 195                                                 // common part\r
 196                                                 vector2d<T> maxp;\r
 197                                                 vector2d<T> minp;\r
 198                                                 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))\r
 199                                                         maxp=start;\r
 200                                                 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))\r
 201                                                         maxp=end;\r
 202                                                 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))\r
 203                                                         maxp=l.start;\r
 204                                                 else\r
 205                                                         maxp=l.end;\r
 206                                                 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)))\r
 207                                                         minp=start;\r
 208                                                 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)))\r
 209                                                         minp=end;\r
 210                                                 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)))\r
 211                                                         minp=l.start;\r
 212                                                 else\r
 213                                                         minp=l.end;\r
 214 \r
 215                                                 // one line is contained in the other. Pick the center\r
 216                                                 // of the remaining points, which overlap for sure\r
 217                                                 out = core::vector2d<T>();\r
 218                                                 if (start != maxp && start != minp)\r
 219                                                         out += start;\r
 220                                                 if (end != maxp && end != minp)\r
 221                                                         out += end;\r
 222                                                 if (l.start != maxp && l.start != minp)\r
 223                                                         out += l.start;\r
 224                                                 if (l.end != maxp && l.end != minp)\r
 225                                                         out += l.end;\r
 226                                                 out.X = (T)(out.X/2);\r
 227                                                 out.Y = (T)(out.Y/2);\r
 228                                         }\r
 229 \r
 230                                         return true; // coincident\r
 231                                 }\r
 232 \r
 233                                 return false; // parallel\r
 234                         }\r
 235 \r
 236                         // Get the point of intersection on this line, checking that\r
 237                         // it is within the line segment.\r
 238                         const f32 uA = numeratorA / commonDenominator;\r
 239                         if (checkOnlySegments)\r
 240                         {\r
 241                                 if(uA < 0.f || uA > 1.f)\r
 242                                         return false; // Outside the line segment\r
 243 \r
 244                                 const f32 uB = numeratorB / commonDenominator;\r
 245                                 if(uB < 0.f || uB > 1.f)\r
 246                                         return false; // Outside the line segment\r
 247                         }\r
 248 \r
 249                         // Calculate the intersection point.\r
 250                         out.X = (T)(start.X + uA * (end.X - start.X));\r
 251                         out.Y = (T)(start.Y + uA * (end.Y - start.Y));\r
 252                         return true;\r
 253                 }\r
 254 \r
 255                 //! Get unit vector of the line.\r
 256                 /** \return Unit vector of this line. */\r
 257                 vector2d<T> getUnitVector() const\r
 258                 {\r
 259                         T len = (T)(1.0 / getLength());\r
 260                         return vector2d<T>((end.X - start.X) * len, (end.Y - start.Y) * len);\r
 261                 }\r
 262 \r
 263                 //! Get angle between this line and given line.\r
 264                 /** \param l Other line for test.\r
 265                 \return Angle in degrees. */\r
 266                 f64 getAngleWith(const line2d<T>& l) const\r
 267                 {\r
 268                         vector2d<T> vect = getVector();\r
 269                         vector2d<T> vect2 = l.getVector();\r
 270                         return vect.getAngleWith(vect2);\r
 271                 }\r
 272 \r
 273                 //! Tells us if the given point lies to the left, right, or on the line.\r
 274                 /** \return 0 if the point is on the line\r
 275                 <0 if to the left, or >0 if to the right. */\r
 276                 T getPointOrientation(const vector2d<T>& point) const\r
 277                 {\r
 278                         return ( (end.X - start.X) * (point.Y - start.Y) -\r
 279                                         (point.X - start.X) * (end.Y - start.Y) );\r
 280                 }\r
 281 \r
 282                 //! Check if the given point is a member of the line\r
 283                 /** \return True if point is between start and end, else false. */\r
 284                 bool isPointOnLine(const vector2d<T>& point) const\r
 285                 {\r
 286                         T d = getPointOrientation(point);\r
 287                         return (d == 0 && point.isBetweenPoints(start, end));\r
 288                 }\r
 289 \r
 290                 //! Check if the given point is between start and end of the line.\r
 291                 /** Assumes that the point is already somewhere on the line. */\r
 292                 bool isPointBetweenStartAndEnd(const vector2d<T>& point) const\r
 293                 {\r
 294                         return point.isBetweenPoints(start, end); \r
 295                 }\r
 296 \r
 297                 //! Get the closest point on this line to a point\r
 298                 /** \param point: Starting search at this point\r
 299                 \param checkOnlySegments: Default (true) is to return a point on the line-segment (between begin and end) of the line.\r
 300                 When set to false the function will check for the first the closest point on the the line even when outside the segment. */\r
 301                 vector2d<T> getClosestPoint(const vector2d<T>& point, bool checkOnlySegments=true) const\r
 302                 {\r
 303                         vector2d<f64> c((f64)(point.X-start.X), (f64)(point.Y- start.Y));\r
 304                         vector2d<f64> v((f64)(end.X-start.X), (f64)(end.Y-start.Y));\r
 305                         f64 d = v.getLength();\r
 306                         if ( d == 0 ) // can't tell much when the line is just a single point\r
 307                                 return start;\r
 308                         v /= d;\r
 309                         f64 t = v.dotProduct(c);\r
 310 \r
 311                         if ( checkOnlySegments )\r
 312                         {\r
 313                                 if (t < 0) return vector2d<T>((T)start.X, (T)start.Y);\r
 314                                 if (t > d) return vector2d<T>((T)end.X, (T)end.Y);\r
 315                         }\r
 316 \r
 317                         v *= t;\r
 318                         return vector2d<T>((T)(start.X + v.X), (T)(start.Y + v.Y));\r
 319                 }\r
 320 \r
 321                 //! Start point of the line.\r
 322                 vector2d<T> start;\r
 323                 //! End point of the line.\r
 324                 vector2d<T> end;\r
 325 };\r
 326 \r
 327         // partial specialization to optimize <f32> lines (avoiding casts)\r
 328         template <>\r
 329         inline vector2df line2d<irr::f32>::getClosestPoint(const vector2df& point, bool checkOnlySegments) const\r
 330         {\r
 331                 const vector2df c = point - start;\r
 332                 vector2df v = end - start;\r
 333                 const f32 d = (f32)v.getLength();\r
 334                 if ( d == 0 ) // can't tell much when the line is just a single point\r
 335                         return start;\r
 336                 v /= d;\r
 337                 const f32 t = v.dotProduct(c);\r
 338 \r
 339                 if ( checkOnlySegments )\r
 340                 {\r
 341                         if (t < 0) return start;\r
 342                         if (t > d) return end;\r
 343                 }\r
 344 \r
 345                 v *= t;\r
 346                 return start + v;\r
 347         }\r
 348 \r
 349 \r
 350         //! Typedef for an f32 line.\r
 351         typedef line2d<f32> line2df;\r
 352         //! Typedef for an integer line.\r
 353         typedef line2d<s32> line2di;\r
 354 \r
 355 } // end namespace core\r
 356 } // end namespace irr\r
 357 \r
 358 #endif\r
 359 \r