|
BWAPI
|
00001 // Copyright (c) 2000 Utrecht University (The Netherlands), 00002 // ETH Zurich (Switzerland), Freie Universitaet Berlin (Germany), 00003 // INRIA Sophia-Antipolis (France), Martin-Luther-University Halle-Wittenberg 00004 // (Germany), Max-Planck-Institute Saarbruecken (Germany), RISC Linz (Austria), 00005 // and Tel-Aviv University (Israel). All rights reserved. 00006 // 00007 // This file is part of CGAL (www.cgal.org); you can redistribute it and/or 00008 // modify it under the terms of the GNU Lesser General Public License as 00009 // published by the Free Software Foundation; version 2.1 of the License. 00010 // See the file LICENSE.LGPL distributed with CGAL. 00011 // 00012 // Licensees holding a valid commercial license may use this file in 00013 // accordance with the commercial license agreement provided with the software. 00014 // 00015 // This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE 00016 // WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 00017 // 00018 // $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/Intersections_2/include/CGAL/Segment_2_Segment_2_intersection.h $ 00019 // $Id: Segment_2_Segment_2_intersection.h 45075 2008-08-21 12:50:41Z spion $ 00020 // 00021 // 00022 // Author(s) : Geert-Jan Giezeman 00023 00024 00025 #ifndef CGAL_SEGMENT_2_SEGMENT_2_INTERSECTION_H 00026 #define CGAL_SEGMENT_2_SEGMENT_2_INTERSECTION_H 00027 00028 #include <CGAL/Segment_2.h> 00029 #include <CGAL/Point_2.h> 00030 #include <CGAL/kernel_assertions.h> 00031 #include <CGAL/number_utils.h> 00032 #include <CGAL/predicates_on_points_2.h> 00033 #include <CGAL/Line_2.h> 00034 #include <CGAL/Line_2_Line_2_intersection.h> 00035 #include <CGAL/Object.h> 00036 #include <CGAL/Uncertain.h> 00037 00038 CGAL_BEGIN_NAMESPACE 00039 00040 namespace CGALi { 00041 00042 template <class K> 00043 inline bool 00044 do_intersect(const typename K::Segment_2 &seg1, const typename K::Segment_2 &seg2); 00045 00046 00047 00048 00049 template <class K> 00050 bool seg_seg_do_intersect_crossing( 00051 const typename K::Point_2 &p1, const typename K::Point_2 &p2, 00052 const typename K::Point_2 &p3, const typename K::Point_2 &p4, 00053 const K& k) 00054 { 00055 switch (make_certain(k.orientation_2_object()(p1,p2,p3))) { 00056 case LEFT_TURN: 00057 return ! (k.orientation_2_object()(p3,p4,p2) == RIGHT_TURN); // right_turn(p3,p4,p2); 00058 case RIGHT_TURN: 00059 return ! (k.orientation_2_object()(p3,p4,p2) == LEFT_TURN); //left_turn(p3,p4,p2); 00060 case COLLINEAR: 00061 return true; 00062 } 00063 CGAL_kernel_assertion(false); 00064 return false; 00065 } 00066 00067 00068 template <class K> 00069 bool seg_seg_do_intersect_contained( 00070 const typename K::Point_2 &p1, const typename K::Point_2 &p2, 00071 const typename K::Point_2 &p3, const typename K::Point_2 &p4, 00072 const K& k) 00073 { 00074 switch (make_certain(k.orientation_2_object()(p1,p2,p3))) { 00075 case LEFT_TURN: 00076 return ! (k.orientation_2_object()(p1,p2,p4) == LEFT_TURN); // left_turn(p1,p2,p4); 00077 case RIGHT_TURN: 00078 return ! (k.orientation_2_object()(p1,p2,p4) == RIGHT_TURN); // right_turn(p1,p2,p4); 00079 case COLLINEAR: 00080 return true; 00081 } 00082 CGAL_kernel_assertion(false); 00083 return false; 00084 } 00085 00086 00087 template <class K> 00088 bool 00089 do_intersect(const typename K::Segment_2 &seg1, 00090 const typename K::Segment_2 &seg2, 00091 const K& k) 00092 { 00093 typename K::Point_2 const & A1 = seg1.source(); 00094 typename K::Point_2 const & A2 = seg1.target(); 00095 typename K::Point_2 const & B1 = seg2.source(); 00096 typename K::Point_2 const & B2 = seg2.target(); 00097 typename K::Less_xy_2 less_xy; 00098 typename K::Compare_xy_2 compare_xy; 00099 00100 if (less_xy(A1,A2)) { 00101 if (less_xy(B1,B2)) { 00102 if (less_xy(A2,B1) 00103 || less_xy(B2,A1)) 00104 return false; 00105 } else { 00106 if (less_xy(A2,B2) 00107 || less_xy(B1,A1)) 00108 return false; 00109 } 00110 } else { 00111 if (less_xy(B1,B2)) { 00112 if (less_xy(A1,B1) 00113 || less_xy(B2,A2)) 00114 return false; 00115 } else { 00116 if (less_xy(A1,B2) 00117 || less_xy(B1,A2)) 00118 return false; 00119 } 00120 } 00121 if (less_xy(A1,A2)) { 00122 if (less_xy(B1,B2)) { 00123 switch(make_certain(compare_xy(A1,B1))) { 00124 case SMALLER: 00125 switch(make_certain(compare_xy(A2,B1))) { 00126 case SMALLER: 00127 return false; 00128 case EQUAL: 00129 return true; 00130 case LARGER: 00131 switch(make_certain(compare_xy(A2,B2))) { 00132 case SMALLER: 00133 return seg_seg_do_intersect_crossing(A1,A2,B1,B2, k); 00134 case EQUAL: 00135 return true; 00136 case LARGER: 00137 return seg_seg_do_intersect_contained(A1,A2,B1,B2, k); 00138 } 00139 } 00140 case EQUAL: 00141 return true; 00142 case LARGER: 00143 switch(make_certain(compare_xy(B2,A1))) { 00144 case SMALLER: 00145 return false; 00146 case EQUAL: 00147 return true; 00148 case LARGER: 00149 switch(make_certain(compare_xy(B2,A2))) { 00150 case SMALLER: 00151 return seg_seg_do_intersect_crossing(B1,B2,A1,A2, k); 00152 case EQUAL: 00153 return true; 00154 case LARGER: 00155 return seg_seg_do_intersect_contained(B1,B2,A1,A2, k); 00156 } 00157 } 00158 } 00159 } else { 00160 switch(make_certain(compare_xy(A1,B2))) { 00161 case SMALLER: 00162 switch(make_certain(compare_xy(A2,B2))) { 00163 case SMALLER: 00164 return false; 00165 case EQUAL: 00166 return true; 00167 case LARGER: 00168 switch(make_certain(compare_xy(A2,B1))) { 00169 case SMALLER: 00170 return seg_seg_do_intersect_crossing(A1,A2,B2,B1, k); 00171 case EQUAL: 00172 return true; 00173 case LARGER: 00174 return seg_seg_do_intersect_contained(A1,A2,B2,B1, k); 00175 } 00176 } 00177 case EQUAL: 00178 return true; 00179 case LARGER: 00180 switch(make_certain(compare_xy(B1,A1))) { 00181 case SMALLER: 00182 return false; 00183 case EQUAL: 00184 return true; 00185 case LARGER: 00186 switch(make_certain(compare_xy(B1,A2))) { 00187 case SMALLER: 00188 return seg_seg_do_intersect_crossing(B2,B1,A1,A2, k); 00189 case EQUAL: 00190 return true; 00191 case LARGER: 00192 return seg_seg_do_intersect_contained(B2,B1,A1,A2, k); 00193 } 00194 } 00195 } 00196 } 00197 } else { 00198 if (less_xy(B1,B2)) { 00199 switch(make_certain(compare_xy(A2,B1))) { 00200 case SMALLER: 00201 switch(make_certain(compare_xy(A1,B1))) { 00202 case SMALLER: 00203 return false; 00204 case EQUAL: 00205 return true; 00206 case LARGER: 00207 switch(make_certain(compare_xy(A1,B2))) { 00208 case SMALLER: 00209 return seg_seg_do_intersect_crossing(A2,A1,B1,B2, k); 00210 case EQUAL: 00211 return true; 00212 case LARGER: 00213 return seg_seg_do_intersect_contained(A2,A1,B1,B2, k); 00214 } 00215 } 00216 case EQUAL: 00217 return true; 00218 case LARGER: 00219 switch(make_certain(compare_xy(B2,A2))) { 00220 case SMALLER: 00221 return false; 00222 case EQUAL: 00223 return true; 00224 case LARGER: 00225 switch(make_certain(compare_xy(B2,A1))) { 00226 case SMALLER: 00227 return seg_seg_do_intersect_crossing(B1,B2,A2,A1, k); 00228 case EQUAL: 00229 return true; 00230 case LARGER: 00231 return seg_seg_do_intersect_contained(B1,B2,A2,A1, k); 00232 } 00233 } 00234 } 00235 } else { 00236 switch(make_certain(compare_xy(A2,B2))) { 00237 case SMALLER: 00238 switch(make_certain(compare_xy(A1,B2))) { 00239 case SMALLER: 00240 return false; 00241 case EQUAL: 00242 return true; 00243 case LARGER: 00244 switch(make_certain(compare_xy(A1,B1))) { 00245 case SMALLER: 00246 return seg_seg_do_intersect_crossing(A2,A1,B2,B1, k); 00247 case EQUAL: 00248 return true; 00249 case LARGER: 00250 return seg_seg_do_intersect_contained(A2,A1,B2,B1, k); 00251 } 00252 } 00253 case EQUAL: 00254 return true; 00255 case LARGER: 00256 switch(make_certain(compare_xy(B1,A2))) { 00257 case SMALLER: 00258 return false; 00259 case EQUAL: 00260 return true; 00261 case LARGER: 00262 switch(make_certain(compare_xy(B1,A1))) { 00263 case SMALLER: 00264 return seg_seg_do_intersect_crossing(B2,B1,A2,A1, k); 00265 case EQUAL: 00266 return true; 00267 case LARGER: 00268 return seg_seg_do_intersect_contained(B2,B1,A2,A1, k); 00269 } 00270 } 00271 } 00272 } 00273 } 00274 CGAL_kernel_assertion(false); 00275 return false; 00276 } 00277 00278 00279 template <class K> 00280 class Segment_2_Segment_2_pair { 00281 public: 00282 enum Intersection_results {NO_INTERSECTION, POINT, SEGMENT}; 00283 Segment_2_Segment_2_pair(typename K::Segment_2 const *seg1, 00284 typename K::Segment_2 const *seg2) 00285 : _seg1(seg1), _seg2(seg2), _known(false) {} 00286 00287 Intersection_results intersection_type() const; 00288 00289 typename K::Point_2 intersection_point() const; 00290 typename K::Segment_2 intersection_segment() const; 00291 protected: 00292 typename K::Segment_2 const* _seg1; 00293 typename K::Segment_2 const * _seg2; 00294 mutable bool _known; 00295 mutable Intersection_results _result; 00296 mutable typename K::Point_2 _intersection_point, _other_point; 00297 }; 00298 00299 template <class K> 00300 typename Segment_2_Segment_2_pair<K>::Intersection_results 00301 Segment_2_Segment_2_pair<K>::intersection_type() const 00302 { 00303 typename K::Construct_vector_2 construct_vector; 00304 if (_known) 00305 return _result; 00306 _known = true; 00307 if (!CGALi::do_intersect(*_seg1, *_seg2, K())) { 00308 _result = NO_INTERSECTION; 00309 return _result; 00310 } 00311 typename K::Line_2 const &l1 = _seg1->supporting_line(); 00312 typename K::Line_2 const &l2 = _seg2->supporting_line(); 00313 Line_2_Line_2_pair<K> linepair(&l1, &l2); 00314 switch ( linepair.intersection_type()) { 00315 case Line_2_Line_2_pair<K>::NO_INTERSECTION: 00316 _result = NO_INTERSECTION; 00317 break; 00318 case Line_2_Line_2_pair<K>::POINT: 00319 _intersection_point = linepair.intersection_point(); 00320 _result = POINT; 00321 break; 00322 case Line_2_Line_2_pair<K>::LINE: 00323 { 00324 typedef typename K::RT RT; 00325 typename K::Point_2 const &start1 = _seg1->source(); 00326 typename K::Point_2 const &end1 = _seg1->target(); 00327 typename K::Point_2 const &start2 = _seg2->source(); 00328 typename K::Point_2 const &end2 = _seg2->target(); 00329 typename K::Vector_2 diff1 = construct_vector(start1, end1); 00330 typename K::Point_2 const *minpt; 00331 typename K::Point_2 const *maxpt; 00332 if (CGAL_NTS abs(diff1.x()) > CGAL_NTS abs(diff1.y())) { 00333 if (start1.x() < end1.x()) { 00334 minpt = &start1; 00335 maxpt = &end1; 00336 } else { 00337 minpt = &end1; 00338 maxpt = &start1; 00339 } 00340 if (start2.x() < end2.x()) { 00341 if (start2.x() > minpt->x()) { 00342 minpt = &start2; 00343 } 00344 if (end2.x() < maxpt->x()) { 00345 maxpt = &end2; 00346 } 00347 } else { 00348 if (end2.x() > minpt->x()) { 00349 minpt = &end2; 00350 } 00351 if (start2.x() < maxpt->x()) { 00352 maxpt = &start2; 00353 } 00354 } 00355 if (maxpt->x() < minpt->x()) { 00356 _result = NO_INTERSECTION; 00357 return _result; 00358 } 00359 if (maxpt->x() == minpt->x()) { 00360 _intersection_point = *minpt; 00361 _result = POINT; 00362 return _result; 00363 } 00364 _intersection_point = *minpt; 00365 _other_point = *maxpt; 00366 _result = SEGMENT; 00367 return _result; 00368 } else { 00369 if (start1.y() < end1.y()) { 00370 minpt = &start1; 00371 maxpt = &end1; 00372 } else { 00373 minpt = &end1; 00374 maxpt = &start1; 00375 } 00376 if (start2.y() < end2.y()) { 00377 if (start2.y() > minpt->y()) { 00378 minpt = &start2; 00379 } 00380 if (end2.y() < maxpt->y()) { 00381 maxpt = &end2; 00382 } 00383 } else { 00384 if (end2.y() > minpt->y()) { 00385 minpt = &end2; 00386 } 00387 if (start2.y() < maxpt->y()) { 00388 maxpt = &start2; 00389 } 00390 } 00391 if (maxpt->y() < minpt->y()) { 00392 _result = NO_INTERSECTION; 00393 return _result; 00394 } 00395 if (maxpt->y() == minpt->y()) { 00396 _intersection_point = *minpt; 00397 _result = POINT; 00398 return _result; 00399 } 00400 _intersection_point = *minpt; 00401 _other_point = *maxpt; 00402 _result = SEGMENT; 00403 return _result; 00404 } 00405 } 00406 } 00407 return _result; 00408 } 00409 00410 00411 template <class K> 00412 typename K::Point_2 00413 Segment_2_Segment_2_pair<K>::intersection_point() const 00414 { 00415 if (!_known) 00416 intersection_type(); 00417 CGAL_kernel_assertion(_result == POINT); 00418 return _intersection_point; 00419 } 00420 00421 template <class K> 00422 typename K::Segment_2 00423 Segment_2_Segment_2_pair<K>::intersection_segment() const 00424 { 00425 typedef typename K::Segment_2 Segment_2; 00426 if (!_known) 00427 intersection_type(); 00428 CGAL_kernel_assertion(_result == SEGMENT); 00429 return Segment_2(_intersection_point, _other_point); 00430 } 00431 00432 00433 00434 00435 template <class K> 00436 Object 00437 intersection(const typename K::Segment_2 &seg1, 00438 const typename K::Segment_2 &seg2, 00439 const K&) 00440 { 00441 typedef Segment_2_Segment_2_pair<K> is_t; 00442 is_t ispair(&seg1, &seg2); 00443 switch (ispair.intersection_type()) { 00444 case is_t::NO_INTERSECTION: 00445 default: 00446 return Object(); 00447 case is_t::POINT: 00448 return make_object(ispair.intersection_point()); 00449 case is_t::SEGMENT: 00450 return make_object(ispair.intersection_segment()); 00451 } 00452 } 00453 00454 } // namespace CGALi 00455 00456 template <class K> 00457 inline 00458 bool 00459 do_intersect(const Segment_2<K> &seg1, 00460 const Segment_2<K> &seg2) 00461 { 00462 typedef typename K::Do_intersect_2 Do_intersect; 00463 return Do_intersect()(seg1, seg2); 00464 } 00465 00466 00467 template <class K> 00468 Object 00469 intersection(const Segment_2<K> &seg1, 00470 const Segment_2<K> &seg2) 00471 { 00472 typedef typename K::Intersect_2 Intersect; 00473 return Intersect()(seg1, seg2); 00474 } 00475 00476 CGAL_END_NAMESPACE 00477 00478 #endif
1.7.6.1
