// Copyright (c) 2000 // Utrecht University (The Netherlands), // ETH Zurich (Switzerland), // INRIA Sophia-Antipolis (France), // Max-Planck-Institute Saarbruecken (Germany), // and Tel-Aviv University (Israel). All rights reserved. // // This file is part of CGAL (www.cgal.org); you can redistribute it and/or // modify it under the terms of the GNU Lesser General Public License as // published by the Free Software Foundation; either version 3 of the License, // or (at your option) any later version. // // Licensees holding a valid commercial license may use this file in // accordance with the commercial license agreement provided with the software. // // This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE // WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. // // $URL$ // $Id$ // // // Author(s) : Geert-Jan Giezeman #ifndef CGAL_SEGMENT_2_SEGMENT_2_INTERSECTION_H #define CGAL_SEGMENT_2_SEGMENT_2_INTERSECTION_H #include #include #include #include #include #include #include #include #include namespace CGAL { namespace internal { template inline bool do_intersect(const typename K::Segment_2 &seg1, const typename K::Segment_2 &seg2); template bool seg_seg_do_intersect_crossing( const typename K::Point_2 &p1, const typename K::Point_2 &p2, const typename K::Point_2 &p3, const typename K::Point_2 &p4, const K& k) { switch (make_certain(k.orientation_2_object()(p1,p2,p3))) { case LEFT_TURN: return ! (k.orientation_2_object()(p3,p4,p2) == RIGHT_TURN); // right_turn(p3,p4,p2); case RIGHT_TURN: return ! (k.orientation_2_object()(p3,p4,p2) == LEFT_TURN); //left_turn(p3,p4,p2); case COLLINEAR: return true; } CGAL_kernel_assertion(false); return false; } template bool seg_seg_do_intersect_contained( const typename K::Point_2 &p1, const typename K::Point_2 &p2, const typename K::Point_2 &p3, const typename K::Point_2 &p4, const K& k) { switch (make_certain(k.orientation_2_object()(p1,p2,p3))) { case LEFT_TURN: return ! (k.orientation_2_object()(p1,p2,p4) == LEFT_TURN); // left_turn(p1,p2,p4); case RIGHT_TURN: return ! (k.orientation_2_object()(p1,p2,p4) == RIGHT_TURN); // right_turn(p1,p2,p4); case COLLINEAR: return true; } CGAL_kernel_assertion(false); return false; } template bool do_intersect(const typename K::Segment_2 &seg1, const typename K::Segment_2 &seg2, const K& k) { typename K::Point_2 const & A1 = seg1.source(); typename K::Point_2 const & A2 = seg1.target(); typename K::Point_2 const & B1 = seg2.source(); typename K::Point_2 const & B2 = seg2.target(); typename K::Less_xy_2 less_xy; typename K::Compare_xy_2 compare_xy; if (less_xy(A1,A2)) { if (less_xy(B1,B2)) { if (less_xy(A2,B1) || less_xy(B2,A1)) return false; } else { if (less_xy(A2,B2) || less_xy(B1,A1)) return false; } } else { if (less_xy(B1,B2)) { if (less_xy(A1,B1) || less_xy(B2,A2)) return false; } else { if (less_xy(A1,B2) || less_xy(B1,A2)) return false; } } if (less_xy(A1,A2)) { if (less_xy(B1,B2)) { switch(make_certain(compare_xy(A1,B1))) { case SMALLER: switch(make_certain(compare_xy(A2,B1))) { case SMALLER: return false; case EQUAL: return true; case LARGER: switch(make_certain(compare_xy(A2,B2))) { case SMALLER: return seg_seg_do_intersect_crossing(A1,A2,B1,B2, k); case EQUAL: return true; case LARGER: return seg_seg_do_intersect_contained(A1,A2,B1,B2, k); } } case EQUAL: return true; case LARGER: switch(make_certain(compare_xy(B2,A1))) { case SMALLER: return false; case EQUAL: return true; case LARGER: switch(make_certain(compare_xy(B2,A2))) { case SMALLER: return seg_seg_do_intersect_crossing(B1,B2,A1,A2, k); case EQUAL: return true; case LARGER: return seg_seg_do_intersect_contained(B1,B2,A1,A2, k); } } } } else { switch(make_certain(compare_xy(A1,B2))) { case SMALLER: switch(make_certain(compare_xy(A2,B2))) { case SMALLER: return false; case EQUAL: return true; case LARGER: switch(make_certain(compare_xy(A2,B1))) { case SMALLER: return seg_seg_do_intersect_crossing(A1,A2,B2,B1, k); case EQUAL: return true; case LARGER: return seg_seg_do_intersect_contained(A1,A2,B2,B1, k); } } case EQUAL: return true; case LARGER: switch(make_certain(compare_xy(B1,A1))) { case SMALLER: return false; case EQUAL: return true; case LARGER: switch(make_certain(compare_xy(B1,A2))) { case SMALLER: return seg_seg_do_intersect_crossing(B2,B1,A1,A2, k); case EQUAL: return true; case LARGER: return seg_seg_do_intersect_contained(B2,B1,A1,A2, k); } } } } } else { if (less_xy(B1,B2)) { switch(make_certain(compare_xy(A2,B1))) { case SMALLER: switch(make_certain(compare_xy(A1,B1))) { case SMALLER: return false; case EQUAL: return true; case LARGER: switch(make_certain(compare_xy(A1,B2))) { case SMALLER: return seg_seg_do_intersect_crossing(A2,A1,B1,B2, k); case EQUAL: return true; case LARGER: return seg_seg_do_intersect_contained(A2,A1,B1,B2, k); } } case EQUAL: return true; case LARGER: switch(make_certain(compare_xy(B2,A2))) { case SMALLER: return false; case EQUAL: return true; case LARGER: switch(make_certain(compare_xy(B2,A1))) { case SMALLER: return seg_seg_do_intersect_crossing(B1,B2,A2,A1, k); case EQUAL: return true; case LARGER: return seg_seg_do_intersect_contained(B1,B2,A2,A1, k); } } } } else { switch(make_certain(compare_xy(A2,B2))) { case SMALLER: switch(make_certain(compare_xy(A1,B2))) { case SMALLER: return false; case EQUAL: return true; case LARGER: switch(make_certain(compare_xy(A1,B1))) { case SMALLER: return seg_seg_do_intersect_crossing(A2,A1,B2,B1, k); case EQUAL: return true; case LARGER: return seg_seg_do_intersect_contained(A2,A1,B2,B1, k); } } case EQUAL: return true; case LARGER: switch(make_certain(compare_xy(B1,A2))) { case SMALLER: return false; case EQUAL: return true; case LARGER: switch(make_certain(compare_xy(B1,A1))) { case SMALLER: return seg_seg_do_intersect_crossing(B2,B1,A2,A1, k); case EQUAL: return true; case LARGER: return seg_seg_do_intersect_contained(B2,B1,A2,A1, k); } } } } } CGAL_kernel_assertion(false); return false; } template class Segment_2_Segment_2_pair { public: enum Intersection_results {NO_INTERSECTION, POINT, SEGMENT}; Segment_2_Segment_2_pair(typename K::Segment_2 const *seg1, typename K::Segment_2 const *seg2) : _seg1(seg1), _seg2(seg2), _known(false) {} Intersection_results intersection_type() const; typename K::Point_2 intersection_point() const; typename K::Segment_2 intersection_segment() const; protected: typename K::Segment_2 const* _seg1; typename K::Segment_2 const * _seg2; mutable bool _known; mutable Intersection_results _result; mutable typename K::Point_2 _intersection_point, _other_point; }; template typename Segment_2_Segment_2_pair::Intersection_results Segment_2_Segment_2_pair::intersection_type() const { typename K::Construct_vector_2 construct_vector; if (_known) return _result; _known = true; if (!internal::do_intersect(*_seg1, *_seg2, K())) { _result = NO_INTERSECTION; return _result; } typename K::Line_2 const &l1 = _seg1->supporting_line(); typename K::Line_2 const &l2 = _seg2->supporting_line(); Line_2_Line_2_pair linepair(&l1, &l2); switch ( linepair.intersection_type()) { case Line_2_Line_2_pair::NO_INTERSECTION: _result = NO_INTERSECTION; break; case Line_2_Line_2_pair::POINT: _intersection_point = linepair.intersection_point(); _result = POINT; break; case Line_2_Line_2_pair::LINE: { //typedef typename K::RT RT; typename K::Point_2 const &start1 = _seg1->source(); typename K::Point_2 const &end1 = _seg1->target(); typename K::Point_2 const &start2 = _seg2->source(); typename K::Point_2 const &end2 = _seg2->target(); typename K::Vector_2 diff1 = construct_vector(start1, end1); typename K::Point_2 const *minpt; typename K::Point_2 const *maxpt; if (CGAL_NTS abs(diff1.x()) > CGAL_NTS abs(diff1.y())) { if (start1.x() < end1.x()) { minpt = &start1; maxpt = &end1; } else { minpt = &end1; maxpt = &start1; } if (start2.x() < end2.x()) { if (start2.x() > minpt->x()) { minpt = &start2; } if (end2.x() < maxpt->x()) { maxpt = &end2; } } else { if (end2.x() > minpt->x()) { minpt = &end2; } if (start2.x() < maxpt->x()) { maxpt = &start2; } } if (maxpt->x() < minpt->x()) { _result = NO_INTERSECTION; return _result; } if (maxpt->x() == minpt->x()) { _intersection_point = *minpt; _result = POINT; return _result; } _intersection_point = *minpt; _other_point = *maxpt; _result = SEGMENT; return _result; } else { if (start1.y() < end1.y()) { minpt = &start1; maxpt = &end1; } else { minpt = &end1; maxpt = &start1; } if (start2.y() < end2.y()) { if (start2.y() > minpt->y()) { minpt = &start2; } if (end2.y() < maxpt->y()) { maxpt = &end2; } } else { if (end2.y() > minpt->y()) { minpt = &end2; } if (start2.y() < maxpt->y()) { maxpt = &start2; } } if (maxpt->y() < minpt->y()) { _result = NO_INTERSECTION; return _result; } if (maxpt->y() == minpt->y()) { _intersection_point = *minpt; _result = POINT; return _result; } _intersection_point = *minpt; _other_point = *maxpt; _result = SEGMENT; return _result; } } } return _result; } template typename K::Point_2 Segment_2_Segment_2_pair::intersection_point() const { if (!_known) intersection_type(); CGAL_kernel_assertion(_result == POINT); return _intersection_point; } template typename K::Segment_2 Segment_2_Segment_2_pair::intersection_segment() const { typedef typename K::Segment_2 Segment_2; if (!_known) intersection_type(); CGAL_kernel_assertion(_result == SEGMENT); return Segment_2(_intersection_point, _other_point); } template typename CGAL::Intersection_traits ::result_type intersection(const typename K::Segment_2 &seg1, const typename K::Segment_2 &seg2, const K&) { typedef Segment_2_Segment_2_pair is_t; is_t ispair(&seg1, &seg2); switch (ispair.intersection_type()) { case is_t::NO_INTERSECTION: default: return intersection_return(); case is_t::POINT: return intersection_return(ispair.intersection_point()); case is_t::SEGMENT: return intersection_return(ispair.intersection_segment()); } } } // namespace internal CGAL_INTERSECTION_FUNCTION_SELF(Segment_2, 2) CGAL_DO_INTERSECT_FUNCTION_SELF(Segment_2, 2) } //namespace CGAL #endif