2
0

line2d.h 13 KB

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