Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
src/geometry/two_d/intersect.h
Go to the documentation of this file.
00001 #ifndef H_GEOMETRY_TWO_D_INTERSECT
00002 #define H_GEOMETRY_TWO_D_INTERSECT
00003 #include "utils/preconditions/preconditions.h"
00004 #include "signum.h"
00005 #include <algorithm>
00006 #include "linesegment.h"
00007 
00008 namespace geometry {
00009 namespace two_d {
00010 
00018 template<typename T>
00019 bool pointOnLine(Point<T> p, LineSegment<T> s) {
00020   Preconditions::check(s.begin != s.end,
00021       "Line ends can't be same!");
00022   return (s.end - s.begin).cross(p - s.begin) == 0; 
00023 }
00024 
00032 template<typename T>
00033 bool pointOnLineSegment(Point<T> p, LineSegment<T> s, bool
00034     acceptCorners) {
00035   if (s.begin == s.end) {
00036     return acceptCorners && (s.begin == p);
00037   }
00038   if (!pointOnLine(p, s)) {
00039     return false;
00040   }
00041   // and now check we are really in segment
00042   Point<T> lineVector = s.end - s.begin;
00043   T t = lineVector.dot(p - s.begin);
00044   T l = lineVector.dot(lineVector);
00045   if (acceptCorners) {
00046     return (t>=0 && t<= l);
00047   } else {
00048     return (t>0 && t<l);
00049   }
00050 }
00051 
00052 enum IntersectType {
00053   NO_INTERSECT, // no intersection
00054   INTERSECT, // single intersection inside objects
00055   TANGENCY, // objects are touching
00056   OVERLAY, // line/area intersection of objects
00057 };
00058 
00063 template<typename T>
00064 IntersectType intervalIntersect(T a1, T a2, T b1, T b2) {
00065   if (a1 > a2) std::swap(a1,a2);
00066   if (b1 > b2) std::swap(b1,b2);
00067 
00068   if (a2 < b1 || b2 < a1) return NO_INTERSECT;
00069 
00070   // we have interval and point or two points and they are in
00071   // overlay
00072   if (a1 == a2 || b1 == b2) return INTERSECT;
00073   if (a2 == b1 || b2 == a1) return TANGENCY;
00074   return OVERLAY;
00075 }
00076 
00082 template<typename T>
00083 IntersectType intersectLineLineSegment(const LineSegment<T>& line,
00084     const LineSegment<T>& segment) {
00085   Preconditions::check(line.begin != line.end);
00086   Preconditions::check(segment.begin != segment.end);
00087 
00088   Point<T> lineVector = line.end - line.begin;
00089   int t1 = signum(lineVector.cross(segment.begin - line.begin));
00090   int t2 = signum(lineVector.cross(segment.end - line.begin));
00091   if (t1 == 0 && t2 == 0) {
00092     return OVERLAY;
00093   }
00094   if (t1 == 0 || t2 == 0) {
00095     return TANGENCY;
00096   }
00097   if (t1 * t2 < 0) {
00098     return INTERSECT;
00099   }
00100   return NO_INTERSECT;
00101 }
00102 
00108 template<typename T>
00109 IntersectType intersectLineSegmentLineSegment(const LineSegment<T>& segment1,
00110     const LineSegment<T>& segment2) {
00111   Preconditions::check(segment1.begin != segment1.end);
00112   Preconditions::check(segment2.begin != segment2.end);
00113 
00114   IntersectType i1 = intersectLineLineSegment(segment1, segment2);
00115   IntersectType i2 = intersectLineLineSegment(segment2, segment1);
00116 
00117   if (i1 == NO_INTERSECT || i2 == NO_INTERSECT) {
00118     return NO_INTERSECT;
00119   }
00120   // i1,i2 can be INTERSECT, OVERLAY, TANGENCY
00121   if ((i1 == INTERSECT && i2 == TANGENCY) ||
00122       (i2 == INTERSECT && i1 == TANGENCY)) {
00123     return TANGENCY;
00124   }
00125   // now we expect only same values
00126   assert(i1 == i2);
00127 
00128   if (i1 == INTERSECT) {
00129     return INTERSECT;
00130   }
00131   if (i1 == TANGENCY) {
00132     return TANGENCY;
00133   }
00134 
00135   // The hard case, we have two times overlay, which means
00136   // that both segments are part of the same line
00137   if ((segment1.end - segment1.begin).x() == 0) {
00138     return intervalIntersect(
00139         segment1.begin.y(), segment1.end.y(),
00140         segment2.begin.y(), segment2.end.y());
00141   } else {
00142     return intervalIntersect(
00143         segment1.begin.y(), segment1.end.y(),
00144         segment2.begin.y(), segment2.end.y());
00145   }
00146 }
00147 
00148 } // namespace two_d
00149 } // namespace geometry
00150 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines