BWAPI
|
00001 // Copyright (c) 1997 Tel-Aviv University (Israel). 00002 // All rights reserved. 00003 // 00004 // This file is part of CGAL (www.cgal.org); you may redistribute it under 00005 // the terms of the Q Public License version 1.0. 00006 // See the file LICENSE.QPL distributed with CGAL. 00007 // 00008 // Licensees holding a valid commercial license may use this file in 00009 // accordance with the commercial license agreement provided with the software. 00010 // 00011 // This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE 00012 // WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. 00013 // 00014 // $URL: svn+ssh://scm.gforge.inria.fr/svn/cgal/branches/CGAL-3.5-branch/Arrangement_on_surface_2/include/CGAL/Sweep_line_2/Arr_basic_insertion_traits_2.h $ 00015 // $Id: Arr_basic_insertion_traits_2.h 50366 2009-07-05 12:56:48Z efif $ 00016 // 00017 // 00018 // Author(s) : Baruch Zukerman <baruchzu@post.tau.ac.il> 00019 // Ron Wein <wein@post.tau.ac.il> 00020 // Efi Fogel <efif@post.tau.ac.il> 00021 00022 #ifndef CGAL_ARR_BASIC_INSERTION_TRAITS_2_H 00023 #define CGAL_ARR_BASIC_INSERTION_TRAITS_2_H 00024 00029 #include <CGAL/Object.h> 00030 #include <CGAL/Arr_tags.h> 00031 00032 #include <list> 00033 #include <iterator> 00034 00035 CGAL_BEGIN_NAMESPACE 00036 00042 template <typename Traits_, typename Arrangement_> 00043 class Arr_basic_insertion_traits_2 00044 { 00045 public: 00046 00047 typedef Traits_ Traits_2; 00048 typedef Arrangement_ Arrangement_2; 00049 00050 typedef typename Arrangement_2::Halfedge_handle Halfedge_handle; 00051 typedef typename Arrangement_2::Vertex_handle Vertex_handle; 00052 typedef typename Traits_2::X_monotone_curve_2 Base_x_monotone_curve_2; 00053 typedef typename Traits_2::Point_2 Base_point_2; 00054 typedef typename Traits_2::Construct_min_vertex_2 Base_construct_min_vertex_2; 00055 typedef typename Traits_2::Construct_max_vertex_2 Base_construct_max_vertex_2; 00056 typedef typename Traits_2::Compare_x_2 Base_compare_x_2; 00057 typedef typename Traits_2::Compare_xy_2 Base_compare_xy_2; 00058 typedef typename Traits_2::Compare_y_at_x_2 Base_compare_y_at_x_2; 00059 typedef typename Traits_2::Compare_y_at_x_right_2 Base_compare_y_at_x_right_2; 00060 typedef typename Traits_2::Equal_2 Base_equal_2; 00061 typedef typename Traits_2::Is_vertical_2 Base_is_vertical_2; 00062 00063 00064 typedef typename CGALi::Arr_complete_left_side_tag< Traits_2 >::Tag 00065 Arr_left_side_tag; 00066 typedef typename CGALi::Arr_complete_bottom_side_tag< Traits_2 >::Tag 00067 Arr_bottom_side_tag; 00068 typedef typename CGALi::Arr_complete_top_side_tag< Traits_2 >::Tag 00069 Arr_top_side_tag; 00070 typedef typename CGALi::Arr_complete_right_side_tag< Traits_2 >::Tag 00071 Arr_right_side_tag; 00072 00073 /* Insertion is implemented as sweep-line visitor. The sweep-line algorithm 00074 * never uses Compare_y_at_x_left_2. 00075 */ 00076 typedef Tag_false Has_left_category; 00077 00078 protected: 00079 00081 const Traits_2 * m_base_traits; 00082 00083 public: 00084 00086 Arr_basic_insertion_traits_2 (const Traits_2 & tr): 00087 m_base_traits (&tr) 00088 {} 00089 00093 class Ex_x_monotone_curve_2 00094 { 00095 public: 00096 00097 typedef Base_x_monotone_curve_2 Base; 00098 00099 protected: 00100 00101 Base m_base_xcv; // The base x-monotone curve. 00102 Halfedge_handle m_he_handle; // The corresponding arrangement edge 00103 // (may be invalid). 00104 bool m_overlap; // Does this curve represent and overlap 00105 // of two other curves. 00106 00107 public: 00108 00109 Ex_x_monotone_curve_2(): 00110 m_base_xcv(), 00111 m_he_handle(), 00112 m_overlap(false) 00113 {} 00114 00115 Ex_x_monotone_curve_2(const Base& xcv): 00116 m_base_xcv (xcv), 00117 m_he_handle(), 00118 m_overlap(false) 00119 {} 00120 00121 Ex_x_monotone_curve_2(const Base& xcv, Halfedge_handle he) : 00122 m_base_xcv (xcv), 00123 m_he_handle (he), 00124 m_overlap(false) 00125 { 00126 CGAL_precondition (he == Halfedge_handle() || 00127 he->direction() == ARR_RIGHT_TO_LEFT); 00128 } 00129 00130 const Base& base() const 00131 { 00132 return (m_base_xcv); 00133 } 00134 00135 Base& base() 00136 { 00137 return (m_base_xcv); 00138 } 00139 00140 operator const Base& () const 00141 { 00142 return (m_base_xcv); 00143 } 00144 00145 Ex_x_monotone_curve_2& operator= (const Base& xcv) 00146 { 00147 m_base_xcv = xcv; 00148 m_he_handle = Halfedge_handle(); 00149 return (*this); 00150 } 00151 00152 Halfedge_handle halfedge_handle() const 00153 { 00154 return (m_he_handle); 00155 } 00156 00157 void set_halfedge_handle(Halfedge_handle he) 00158 { 00159 CGAL_precondition (he == Halfedge_handle() || 00160 he->direction() == ARR_RIGHT_TO_LEFT); 00161 m_he_handle = he; 00162 } 00163 00164 bool is_overlapping () const 00165 { 00166 return (m_overlap); 00167 } 00168 00169 void set_overlapping () 00170 { 00171 m_overlap = true; 00172 } 00173 }; 00174 00175 typedef Ex_x_monotone_curve_2 X_monotone_curve_2; 00176 00177 #ifdef CGAL_SL_VERBOSE 00178 // For debugging purposes: 00179 friend std::ostream& operator<< (std::ostream& os, 00180 const X_monotone_curve_2& xcv) 00181 { 00182 os << xcv.base(); 00183 return (os); 00184 } 00185 #endif 00186 00190 class Ex_point_2 00191 { 00192 public: 00193 00194 typedef Base_point_2 Base; 00195 00196 protected: 00197 00198 Base m_base_pt; // The base point. 00199 Vertex_handle m_v; // The corresponding arrangement vertex 00200 // (may be invalid). 00201 00202 public: 00203 00204 Ex_point_2() : 00205 m_base_pt(), 00206 m_v() 00207 {} 00208 00209 Ex_point_2 (const Base& pt) : 00210 m_base_pt (pt), 00211 m_v() 00212 {} 00213 00214 Ex_point_2 (const Base& pt, Vertex_handle v) : 00215 m_base_pt (pt), 00216 m_v (v) 00217 {} 00218 00219 const Base& base() const 00220 { 00221 return (m_base_pt); 00222 } 00223 00224 operator const Base& () const 00225 { 00226 return (m_base_pt); 00227 } 00228 00229 Vertex_handle vertex_handle() const 00230 { 00231 return m_v; 00232 } 00233 00234 void set_vertex_handle(Vertex_handle v) 00235 { 00236 m_v = v; 00237 } 00238 }; 00239 00240 typedef Ex_point_2 Point_2; 00241 00242 #ifdef CGAL_SL_VERBOSE 00243 // For debugging purposes: 00244 friend std::ostream& operator<< (std::ostream& os, 00245 const Point_2& pt) 00246 { 00247 os << pt.base(); 00248 return (os); 00249 } 00250 #endif 00251 00253 class Construct_min_vertex_2 { 00254 protected: 00255 Base_construct_min_vertex_2 m_base_min_v; 00256 Base_equal_2 m_base_equal; 00257 Halfedge_handle invalid_he; 00258 00264 Construct_min_vertex_2 (const Base_construct_min_vertex_2& base_min_v, 00265 const Base_equal_2& base_equal) : 00266 m_base_min_v (base_min_v), 00267 m_base_equal (base_equal), 00268 invalid_he() 00269 {} 00270 00272 friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>; 00273 00274 public: 00275 Point_2 operator() (const X_monotone_curve_2 & xcv) 00276 { 00277 // If there is not halfedge associated with the curve, just return 00278 // a point with invalid halfedge handle. 00279 const Base_point_2& base_p = m_base_min_v(xcv.base()); 00280 00281 if (xcv.halfedge_handle() == invalid_he) 00282 return (Point_2 (base_p)); 00283 00284 // Note that the halfedge associated with the curve is always directed 00285 // from right to left, so its target is the leftmost vertex. 00286 // We probably have to associate the point with the target vertex of 00287 // the halfedge associated with the curve. 00288 Vertex_handle vh = xcv.halfedge_handle()->target(); 00289 00290 if (! xcv.is_overlapping()) 00291 return (Point_2(base_p, vh)); 00292 00293 // In case of an overlapping curve, make sure the curve endpoint equals 00294 // the point associated with the vertex. If not, we attach an invalid 00295 // vertex to the extended point. 00296 if (! vh->is_at_open_boundary() && m_base_equal (base_p, vh->point())) 00297 return (Point_2(base_p, vh)); 00298 else 00299 return (Point_2 (base_p)); 00300 } 00301 }; 00302 00304 Construct_min_vertex_2 construct_min_vertex_2_object () const 00305 { 00306 return (Construct_min_vertex_2 00307 (m_base_traits->construct_min_vertex_2_object(), 00308 m_base_traits->equal_2_object())); 00309 } 00310 00312 class Construct_max_vertex_2 { 00313 protected: 00314 Base_construct_max_vertex_2 m_base_max_v; 00315 Base_equal_2 m_base_equal; 00316 Halfedge_handle invalid_he; 00317 00323 Construct_max_vertex_2 (const Base_construct_max_vertex_2& base_max_v, 00324 const Base_equal_2& base_equal) : 00325 m_base_max_v (base_max_v), 00326 m_base_equal (base_equal), 00327 invalid_he() 00328 {} 00329 00330 00332 friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>; 00333 00334 public: 00335 Point_2 operator() (const X_monotone_curve_2 & xcv) 00336 { 00337 // If there is not halfedge associated with the curve, just return 00338 // a point with invalid halfedge handle. 00339 const Base_point_2& base_p = m_base_max_v(xcv.base()); 00340 00341 if (xcv.halfedge_handle() == invalid_he) 00342 return (Point_2 (base_p)); 00343 00344 // Note that the halfedge associated with the curve is always directed 00345 // from right to left, so its source is the rightmost vertex. 00346 // We probably have to associate the point with the source vertex of 00347 // the halfedge associated with the curve. 00348 Vertex_handle vh = xcv.halfedge_handle()->source(); 00349 00350 if (! xcv.is_overlapping()) 00351 return (Point_2(base_p, vh)); 00352 00353 // In case of an overlapping curve, make sure the curve endpoint equals 00354 // the point associated with the vertex. If not, we attach an invalid 00355 // vertex to the extended point. 00356 if (! vh->is_at_open_boundary() && m_base_equal (base_p, vh->point())) 00357 return (Point_2(base_p, vh)); 00358 else 00359 return (Point_2 (base_p)); 00360 } 00361 }; 00362 00364 Construct_max_vertex_2 construct_max_vertex_2_object () const 00365 { 00366 return (Construct_max_vertex_2 00367 (m_base_traits->construct_max_vertex_2_object(), 00368 m_base_traits->equal_2_object())); 00369 } 00370 00372 class Compare_xy_2 { 00373 protected: 00374 Base_compare_xy_2 m_base_cmp_xy; 00375 00381 Compare_xy_2(const Base_compare_xy_2 & base) : m_base_cmp_xy(base) {} 00382 00384 friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>; 00385 00386 public: 00387 Comparison_result operator() (const Point_2& p1, const Point_2& p2) const 00388 { 00389 if(p1.vertex_handle() == p2.vertex_handle() && 00390 p1.vertex_handle() != Vertex_handle()) 00391 return (EQUAL); 00392 00393 return (m_base_cmp_xy(p1.base(), p2.base())); 00394 } 00395 }; 00396 00398 Compare_xy_2 compare_xy_2_object () const 00399 { 00400 return (Compare_xy_2 (m_base_traits->compare_xy_2_object())); 00401 } 00402 00406 class Compare_y_at_x_2 { 00407 protected: 00408 Base_compare_y_at_x_2 m_base_cmp_y_at_x; 00409 00415 Compare_y_at_x_2(const Base_compare_y_at_x_2& base) : 00416 m_base_cmp_y_at_x(base) 00417 {} 00418 00420 friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>; 00421 00422 public: 00423 Comparison_result operator() (const Point_2& p, 00424 const X_monotone_curve_2& xcv) const 00425 { 00426 return (m_base_cmp_y_at_x (p.base(), xcv.base())); 00427 } 00428 }; 00429 00431 Compare_y_at_x_2 compare_y_at_x_2_object () const 00432 { 00433 return (Compare_y_at_x_2 (m_base_traits->compare_y_at_x_2_object())); 00434 } 00435 00439 class Compare_y_at_x_right_2 { 00440 protected: 00441 Base_compare_y_at_x_right_2 m_base_cmp_y_at_x_right; 00442 00448 Compare_y_at_x_right_2(const Base_compare_y_at_x_right_2& base) : 00449 m_base_cmp_y_at_x_right(base) 00450 {} 00451 00453 friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>; 00454 00455 public: 00456 Comparison_result operator() (const X_monotone_curve_2& xcv1, 00457 const X_monotone_curve_2& xcv2, 00458 const Point_2& p) const 00459 { 00460 return (m_base_cmp_y_at_x_right(xcv1.base(), 00461 xcv2.base(), 00462 p.base())); 00463 } 00464 }; 00465 00467 Compare_y_at_x_right_2 compare_y_at_x_right_2_object () const 00468 { 00469 return (Compare_y_at_x_right_2 00470 (m_base_traits->compare_y_at_x_right_2_object())); 00471 } 00472 00476 class Equal_2 { 00477 protected: 00478 Base_equal_2 m_base_eq; 00479 00485 Equal_2(const Base_equal_2& base) : m_base_eq(base) {} 00486 00488 friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>; 00489 00490 public: 00492 bool operator() (const X_monotone_curve_2& xcv1, 00493 const X_monotone_curve_2& xcv2) const 00494 { 00495 return (m_base_eq(xcv1.base(), xcv2.base())); 00496 } 00497 00499 bool operator() (const Point_2& p1, const Point_2& p2) const 00500 { 00501 return (m_base_eq(p1.base(), p2.base())); 00502 } 00503 }; 00504 00506 Equal_2 equal_2_object () const 00507 { 00508 return (Equal_2 (m_base_traits->equal_2_object())); 00509 } 00510 00512 class Compare_x_2 { 00513 protected: 00514 Base_compare_x_2 m_base_cmp_x; 00515 00521 Compare_x_2(const Base_compare_x_2& base) : m_base_cmp_x(base) {} 00522 00524 friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>; 00525 00526 public: 00527 Comparison_result operator() (const Point_2& p1, const Point_2& p2) const 00528 { 00529 return (m_base_cmp_x(p1.base(), p2.base())); 00530 } 00531 }; 00532 00534 Compare_x_2 compare_x_2_object () const 00535 { 00536 return (Compare_x_2 (m_base_traits->compare_x_2_object())); 00537 } 00538 00540 class Is_vertical_2 { 00541 protected: 00542 Base_is_vertical_2 m_base_is_vert; 00543 00549 Is_vertical_2(const Base_is_vertical_2& base) : m_base_is_vert(base) {} 00550 00552 friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>; 00553 00554 public: 00555 bool operator() (const X_monotone_curve_2& xcv) const 00556 { 00557 return (m_base_is_vert(xcv.base())); 00558 } 00559 }; 00560 00562 Is_vertical_2 is_vertical_2_object() const 00563 { 00564 return (Is_vertical_2(m_base_traits->is_vertical_2_object())); 00565 } 00566 00567 // left-right 00568 00572 class Parameter_space_in_x_2 { 00573 protected: 00575 const Traits_2 * m_base; 00576 00584 Parameter_space_in_x_2 (const Traits_2 * tr) : m_base(tr) {} 00585 00587 friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>; 00588 00589 public: 00590 Arr_parameter_space operator() (const X_monotone_curve_2 & xcv, 00591 Arr_curve_end ce) const 00592 { 00593 return (m_base->parameter_space_in_x_2_object() (xcv.base(), ce)); 00594 } 00595 00596 Arr_parameter_space operator()(const Point_2 & p) const 00597 { 00598 return m_base->parameter_space_in_x_2_object() (p.base()); 00599 } 00600 00601 Arr_parameter_space operator()(const X_monotone_curve_2 & xcv) const 00602 { 00603 return m_base->parameter_space_in_x_2_object() (xcv.base()); 00604 } 00605 00606 }; 00607 00609 Parameter_space_in_x_2 parameter_space_in_x_2_object () const 00610 { 00611 return Parameter_space_in_x_2 (m_base_traits); 00612 } 00613 00617 class Compare_y_near_boundary_2 { 00618 protected: 00620 const Traits_2 * m_base; 00621 00629 Compare_y_near_boundary_2(const Traits_2 * base) : m_base(base) {} 00630 00632 friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>; 00633 00634 public: 00638 Comparison_result operator() (const X_monotone_curve_2 & xcv1, 00639 const X_monotone_curve_2 & xcv2, 00640 Arr_curve_end ce) const 00641 { 00642 return m_base->compare_y_near_boundary_2_object() (xcv1.base(), 00643 xcv2.base(), ce); 00644 } 00645 00646 }; 00647 00650 Compare_y_near_boundary_2 compare_y_near_boundary_2_object() const 00651 { 00652 return Compare_y_near_boundary_2 (m_base_traits); 00653 } 00654 00658 class Compare_y_on_boundary_2 00659 { 00660 protected: 00662 const Traits_2 * m_base; 00663 00671 Compare_y_on_boundary_2 (const Traits_2 * base) : m_base(base) {} 00672 00674 friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>; 00675 00676 public: 00680 Comparison_result operator() (const Point_2 & p1, 00681 const Point_2 & p2) const 00682 { 00683 return m_base->compare_y_on_boundary_2_object()(p1.base(), p2.base()); 00684 } 00685 00686 }; 00687 00690 Compare_y_on_boundary_2 compare_y_on_boundary_2_object() const 00691 { 00692 return Compare_y_on_boundary_2(m_base_traits); 00693 } 00694 00695 // TODO Is_on_x_identification_2 00696 00697 00698 // bottom-top 00699 00703 class Parameter_space_in_y_2 { 00704 protected: 00706 const Traits_2 * m_base; 00707 00715 Parameter_space_in_y_2(const Traits_2 * tr) : m_base(tr) {} 00716 00718 friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>; 00719 00720 public: 00721 Arr_parameter_space operator() (const X_monotone_curve_2& xcv, 00722 Arr_curve_end ce) const 00723 { 00724 return m_base->parameter_space_in_y_2_object() (xcv.base(), ce); 00725 } 00726 00727 Arr_parameter_space operator()(const Point_2 & p) const 00728 { 00729 return m_base->parameter_space_in_y_2_object() (p.base()); 00730 } 00731 00732 Arr_parameter_space operator()(const X_monotone_curve_2 & xcv) const 00733 { 00734 return m_base->parameter_space_in_y_2_object() (xcv.base()); 00735 } 00736 00737 }; 00738 00740 Parameter_space_in_y_2 parameter_space_in_y_2_object () const 00741 { 00742 return Parameter_space_in_y_2 (m_base_traits); 00743 } 00744 00748 class Compare_x_near_boundary_2 { 00749 protected: 00751 const Traits_2 * m_base; 00752 00760 Compare_x_near_boundary_2 (const Traits_2 * base) : m_base(base) {} 00761 00763 friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>; 00764 00765 public: 00769 Comparison_result operator() (const Point_2 & p, 00770 const X_monotone_curve_2 & xcv, 00771 Arr_curve_end ce) const 00772 { 00773 00774 return m_base->compare_x_near_boundary_2_object() (p.base(), 00775 xcv.base(), ce); 00776 } 00777 00781 Comparison_result operator() (const X_monotone_curve_2 & xcv1, 00782 Arr_curve_end ce1, 00783 const X_monotone_curve_2 & xcv2, 00784 Arr_curve_end ce2) const 00785 { 00786 return m_base->compare_x_near_boundary_2_object() (xcv1.base(), ce1, 00787 xcv2.base(), ce2); 00788 } 00789 00790 }; 00791 00794 Compare_x_near_boundary_2 compare_x_near_boundary_2_object() const 00795 { 00796 return Compare_x_near_boundary_2(m_base_traits); 00797 } 00798 00802 class Compare_x_on_boundary_2 00803 { 00804 protected: 00806 const Traits_2 * m_base; 00807 00815 Compare_x_on_boundary_2 (const Traits_2 * base) : m_base(base) {} 00816 00818 friend class Arr_basic_insertion_traits_2<Traits_, Arrangement_>; 00819 00820 public: 00824 Comparison_result operator() (const Point_2 & p1, 00825 const Point_2 & p2) const 00826 { 00827 return m_base->compare_x_on_boundary_2_object()(p1.base(), p2.base()); 00828 } 00829 00830 }; 00831 00834 Compare_x_on_boundary_2 compare_x_on_boundary_2_object() const 00835 { 00836 return Compare_x_on_boundary_2(m_base_traits); 00837 } 00838 00839 // TODO Is_on_y_identification_2 00840 00841 }; 00842 00843 CGAL_END_NAMESPACE 00844 00845 #endif