Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
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