|
BWAPI
|
00001 // Copyright (c) 2006, 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/Arr_spherical_topology_traits_2.h $ 00015 // $Id: Arr_spherical_topology_traits_2.h 50366 2009-07-05 12:56:48Z efif $ 00016 // 00017 // Author(s) : Efi Fogel <efif@post.tau.ac.il> 00018 // Eric Berberich <ericb@post.tau.ac.il> 00019 00020 #ifndef CGAL_ARR_SPHERICAL_TOPOLOGY_TRAITS_2_H 00021 #define CGAL_ARR_SPHERICAL_TOPOLOGY_TRAITS_2_H 00022 00028 #include <CGAL/Arr_enums.h> 00029 #include <CGAL/Arr_tags.h> 00030 #include <CGAL/Arr_default_dcel.h> 00031 #include <CGAL/Arr_naive_point_location.h> 00032 #include <CGAL/Arrangement_2/Arr_traits_adaptor_2.h> 00033 #include <CGAL/Sweep_line_2/Arr_construction_event.h> 00034 #include <CGAL/Sweep_line_2/Arr_construction_subcurve.h> 00035 #include <CGAL/Sweep_line_2/Arr_construction_sl_visitor.h> 00036 #include <CGAL/Sweep_line_2/Arr_basic_insertion_traits_2.h> 00037 #include <CGAL/Sweep_line_2/Arr_basic_insertion_sl_visitor.h> 00038 #include <CGAL/Sweep_line_2/Arr_insertion_traits_2.h> 00039 #include <CGAL/Sweep_line_2/Arr_insertion_sl_visitor.h> 00040 #include <CGAL/Sweep_line_2/Arr_overlay_subcurve.h> 00041 #include <CGAL/Sweep_line_2/Arr_overlay_traits_2.h> 00042 #include <CGAL/Sweep_line_2/Arr_overlay_sl_visitor.h> 00043 #include <CGAL/Sweep_line_2/Arr_batched_pl_sl_visitor.h> 00044 #include <CGAL/Sweep_line_2/Arr_vert_decomp_sl_visitor.h> 00045 #include <CGAL/Arr_point_location/Arr_batched_point_location_traits_2.h> 00046 00047 #include <CGAL/Arr_topology_traits/Arr_spherical_construction_helper.h> 00048 #include <CGAL/Arr_topology_traits/Arr_spherical_insertion_helper.h> 00049 #include <CGAL/Arr_topology_traits/Arr_spherical_overlay_helper.h> 00050 #include <CGAL/Arr_topology_traits/Arr_spherical_batched_pl_helper.h> 00051 #include <CGAL/Arr_topology_traits/Arr_spherical_vert_decomp_helper.h> 00052 #include <CGAL/Arr_topology_traits/Arr_inc_insertion_zone_visitor.h> 00053 00054 #include <map> 00055 00056 CGAL_BEGIN_NAMESPACE 00057 00058 // Forward declaration: 00059 template <class GeomTraits, class TopTraits> 00060 class Arrangement_on_surface_2; 00061 00065 template <class GeomTraits, class T_Dcel = Arr_default_dcel<GeomTraits> > 00066 class Arr_spherical_topology_traits_2 { 00067 public: 00068 00070 00071 typedef GeomTraits Geometry_traits_2; 00072 typedef typename Geometry_traits_2::Point_2 Point_2; 00073 typedef typename Geometry_traits_2::X_monotone_curve_2 X_monotone_curve_2; 00075 00077 00078 typedef T_Dcel Dcel; 00079 typedef typename Dcel::Size Size; 00080 typedef typename Dcel::Vertex Vertex; 00081 typedef typename Dcel::Halfedge Halfedge; 00082 typedef typename Dcel::Face Face; 00083 typedef typename Dcel::Outer_ccb Outer_ccb; 00084 typedef typename Dcel::Inner_ccb Inner_ccb; 00085 typedef typename Dcel::Isolated_vertex Isolated_vertex; 00087 00088 // TODO remove adaptor as top-traits might be instantiated by Aos_2 itself 00089 typedef Arr_traits_basic_adaptor_2<Geometry_traits_2> Traits_adaptor_2; 00090 00091 typedef Arr_spherical_topology_traits_2<Geometry_traits_2, Dcel> 00092 Self; 00093 00095 00096 // are inherited from the geometry traits 00097 typedef typename Traits_adaptor_2::Arr_left_side_tag Arr_left_side_tag; 00098 typedef typename Traits_adaptor_2::Arr_bottom_side_tag Arr_bottom_side_tag; 00099 typedef typename Traits_adaptor_2::Arr_top_side_tag Arr_top_side_tag; 00100 typedef typename Traits_adaptor_2::Arr_right_side_tag Arr_right_side_tag; 00101 00102 BOOST_MPL_ASSERT 00103 ( 00104 (boost::mpl::or_< 00105 boost::is_same< Arr_left_side_tag, Arr_oblivious_side_tag >, 00106 boost::is_same< Arr_left_side_tag, Arr_identified_side_tag > >) 00107 ); 00108 BOOST_MPL_ASSERT 00109 ( 00110 (boost::mpl::or_< 00111 boost::is_same< Arr_bottom_side_tag, Arr_oblivious_side_tag >, 00112 boost::is_same< Arr_bottom_side_tag, Arr_contracted_side_tag > >) 00113 ); 00114 BOOST_MPL_ASSERT 00115 ( 00116 (boost::mpl::or_< 00117 boost::is_same< Arr_top_side_tag, Arr_oblivious_side_tag >, 00118 boost::is_same< Arr_top_side_tag, Arr_contracted_side_tag > >) 00119 ); 00120 BOOST_MPL_ASSERT 00121 ( 00122 (boost::mpl::or_< 00123 boost::is_same< Arr_right_side_tag, Arr_oblivious_side_tag >, 00124 boost::is_same< Arr_right_side_tag, Arr_identified_side_tag > >) 00125 ); 00127 00132 template<typename T, typename D> 00133 struct rebind 00134 { 00135 typedef Arr_spherical_topology_traits_2<T,D> other; 00136 }; 00137 00138 private: 00139 00141 struct Vertex_key_comparer { 00143 Vertex_key_comparer() : m_traits(NULL) {} 00144 00146 Vertex_key_comparer(const Traits_adaptor_2 * traits) : m_traits(traits) {} 00147 const Traits_adaptor_2 * m_traits; 00148 bool operator()(const Point_2 & p1, const Point_2 & p2) const 00149 { 00150 return (m_traits->compare_y_on_boundary_2_object()(p1, p2) == 00151 SMALLER); 00152 } 00153 }; 00154 00156 typedef std::map<Point_2,Vertex*,Vertex_key_comparer> Vertex_map; 00157 typedef std::pair<Point_2,Vertex*> Vertex_value; 00158 00159 protected: 00160 // Data members: 00162 Dcel m_dcel; 00163 00165 Face * m_spherical_face; 00166 00168 Vertex * m_north_pole; 00169 00171 Vertex * m_south_pole; 00172 00174 Vertex_map m_boundary_vertices; 00175 00177 const Traits_adaptor_2 * m_traits; 00178 00179 // Inidicates whether the traits object should evetually be freed. 00180 bool m_own_traits; 00181 00182 // Copy constructor and assignment operator - not supported. 00183 Arr_spherical_topology_traits_2(const Self &); 00184 Self & operator=(const Self &); 00185 00186 public: 00188 00189 00191 Arr_spherical_topology_traits_2(); 00192 00196 Arr_spherical_topology_traits_2(const Geometry_traits_2 * traits); 00197 00201 void assign(const Self & other); 00203 00205 00206 00208 const Dcel & dcel() const 00209 { 00210 return (m_dcel); 00211 } 00212 00214 Dcel & dcel() 00215 { 00216 return m_dcel; 00217 } 00218 00222 bool is_empty_dcel() const 00223 { 00224 return (m_dcel.size_of_vertices() == 0); 00225 } 00226 00228 void init_dcel(); 00229 00231 void dcel_updated(); 00232 00238 bool is_concrete_vertex(const Vertex * /* v */) const 00239 { 00240 return true; 00241 } 00242 00246 Size number_of_concrete_vertices() const 00247 { 00248 return (m_dcel.size_of_vertices()); 00249 } 00250 00255 bool is_valid_vertex (const Vertex * /* v */) const 00256 { 00257 return true; 00258 } 00259 00261 Size number_of_valid_vertices() const 00262 { 00263 return (m_dcel.size_of_vertices()); 00264 } 00265 00267 bool is_valid_halfedge (const Halfedge * /* he */) const 00268 { 00269 return true; 00270 } 00271 00273 Size number_of_valid_halfedges() const 00274 { 00275 return (m_dcel.size_of_halfedges()); 00276 } 00277 00279 bool is_valid_face(const Face * /* f */) const 00280 { 00281 return true; 00282 } 00283 00285 Size number_of_valid_faces() const 00286 { 00287 return m_dcel.size_of_faces(); 00288 } 00289 00291 const Face * spherical_face() const 00292 { 00293 return m_spherical_face; 00294 } 00295 00297 Face * spherical_face() 00298 { 00299 return m_spherical_face; 00300 } 00301 00303 const Face * south_face() const 00304 { 00305 if (m_boundary_vertices.empty()) return m_spherical_face; 00306 typename Vertex_map::const_iterator it = m_boundary_vertices.begin(); 00307 return _face_below_vertex_on_discontinuity(it->second); 00308 } 00309 00311 Face * south_face() 00312 { 00313 if (m_boundary_vertices.empty()) return m_spherical_face; 00314 typename Vertex_map::iterator it = m_boundary_vertices.begin(); 00315 return _face_below_vertex_on_discontinuity(it->second); 00316 } 00317 00319 const Vertex * south_pole() const 00320 { 00321 return m_south_pole; 00322 } 00323 00325 Vertex * south_pole() 00326 { 00327 return m_south_pole; 00328 } 00329 00331 const Vertex * north_pole() const 00332 { 00333 return m_north_pole; 00334 } 00335 00337 Vertex * north_pole() 00338 { 00339 return m_north_pole; 00340 } 00341 00345 Vertex * discontinuity_vertex (const X_monotone_curve_2 xc, Arr_curve_end ind) 00346 { 00347 Point_2 key; 00348 if (ind == ARR_MIN_END) 00349 key = m_traits->construct_min_vertex_2_object() (xc); 00350 else 00351 key = m_traits->construct_max_vertex_2_object() (xc); 00352 00353 typename Vertex_map::iterator it = m_boundary_vertices.find(key); 00354 return (it != m_boundary_vertices.end()) ? it->second : NULL; 00355 } 00356 00358 00359 private: 00361 00362 typedef Arrangement_on_surface_2<Geometry_traits_2, Self> Arr; 00363 00364 // Type definition for the constuction sweep-line visitor. 00365 typedef Arr_construction_subcurve<Geometry_traits_2> CSubcurve; 00366 typedef Arr_construction_event<Geometry_traits_2,CSubcurve,Arr> 00367 CEvent; 00368 typedef Arr_spherical_construction_helper<Geometry_traits_2,Arr, 00369 CEvent,CSubcurve> CHelper; 00370 00371 // Type definition for the basic insertion sweep-line visitor. 00372 typedef Arr_basic_insertion_traits_2<Geometry_traits_2, Arr> BInsTraits; 00373 typedef Arr_construction_subcurve<BInsTraits> BISubcurve; 00374 typedef Arr_construction_event<BInsTraits,BISubcurve,Arr> BIEvent; 00375 typedef Arr_spherical_insertion_helper<BInsTraits,Arr,BIEvent,BISubcurve> 00376 BIHelper; 00377 00378 // Type definition for the insertion sweep-line visitor. 00379 typedef Arr_insertion_traits_2<Geometry_traits_2, Arr> InsTraits; 00380 typedef Arr_construction_subcurve<InsTraits> ISubcurve; 00381 typedef Arr_construction_event<InsTraits,ISubcurve,Arr> IEvent; 00382 typedef Arr_spherical_insertion_helper<InsTraits,Arr,IEvent,ISubcurve> 00383 IHelper; 00384 00385 // Type definition for the batched point-location sweep-line visitor. 00386 typedef Arr_batched_point_location_traits_2<Arr> BplTraits; 00387 typedef Arr_spherical_batched_pl_helper<BplTraits, Arr> BplHelper; 00388 00389 // Type definition for the vertical decomposition sweep-line visitor. 00390 typedef Arr_batched_point_location_traits_2<Arr> VdTraits; 00391 typedef Arr_spherical_vert_decomp_helper<VdTraits, Arr> VdHelper; 00392 00393 // Type definition for the overlay sweep-line visitor. 00394 template <class ExGeomTraits_, class ArrangementA_, class ArrangementB_> 00395 struct _Overlay_helper : 00396 public Arr_spherical_overlay_helper<ExGeomTraits_, ArrangementA_, 00397 ArrangementB_, Arr, Arr_construction_event<ExGeomTraits_, 00398 Arr_overlay_subcurve<ExGeomTraits_>, Arr>, 00399 Arr_overlay_subcurve<ExGeomTraits_> > 00400 { 00401 typedef Arr_spherical_overlay_helper<ExGeomTraits_, ArrangementA_, 00402 ArrangementB_, Arr, Arr_construction_event<ExGeomTraits_, 00403 Arr_overlay_subcurve<ExGeomTraits_>, Arr>, 00404 Arr_overlay_subcurve<ExGeomTraits_> > Base; 00405 00406 typedef typename Base::Traits_2 Traits_2; 00407 typedef typename Base::Arrangement_red_2 Arrangement_red_2; 00408 typedef typename Base::Arrangement_blue_2 Arrangement_blue_2; 00409 typedef typename Base::Arrangement_2 Arrangement_2; 00410 typedef typename Base::Event Event; 00411 typedef typename Base::Subcurve Subcurve; 00412 typedef typename Base::Construction_helper Construction_helper; 00413 00414 _Overlay_helper(const ArrangementA_ * arrA, const ArrangementB_ * arrB) : 00415 Base(arrA, arrB) {} 00416 }; 00418 00419 public: 00421 00422 00423 typedef Arr_construction_sl_visitor<CHelper> 00424 Sweep_line_construction_visitor; 00425 00426 typedef Arr_insertion_sl_visitor<IHelper> 00427 Sweep_line_insertion_visitor; 00428 00429 typedef Sweep_line_construction_visitor 00430 Sweep_line_non_intersecting_construction_visitor; 00431 00432 typedef Arr_basic_insertion_sl_visitor<BIHelper> 00433 Sweep_line_non_intersecting_insertion_visitor; 00434 00435 template <class OutputIterator_> 00436 struct Sweep_line_bacthed_point_location_visitor : 00437 public Arr_batched_pl_sl_visitor<BplHelper, OutputIterator_> 00438 { 00439 typedef OutputIterator_ Output_iterator; 00440 typedef Arr_batched_pl_sl_visitor<BplHelper,Output_iterator> Base; 00441 00442 typedef typename Base::Traits_2 Traits_2; 00443 typedef typename Base::Event Event; 00444 typedef typename Base::Subcurve Subcurve; 00445 00446 Sweep_line_bacthed_point_location_visitor(const Arr * arr, 00447 Output_iterator * oi) : 00448 Base(arr, oi) 00449 {} 00450 }; 00451 00452 template <class OutputIterator_> 00453 struct Sweep_line_vertical_decomposition_visitor : 00454 public Arr_vert_decomp_sl_visitor<VdHelper, OutputIterator_> 00455 { 00456 typedef OutputIterator_ Output_iterator; 00457 typedef Arr_vert_decomp_sl_visitor<VdHelper,Output_iterator> Base; 00458 00459 typedef typename Base::Traits_2 Traits_2; 00460 typedef typename Base::Event Event; 00461 typedef typename Base::Subcurve Subcurve; 00462 00463 Sweep_line_vertical_decomposition_visitor(const Arr * arr, 00464 Output_iterator * oi) : 00465 Base(arr, oi) 00466 {} 00467 }; 00468 00469 template <class ArrangementA_, class ArrangementB_, class OverlayTraits_> 00470 struct Sweep_line_overlay_visitor : 00471 public Arr_overlay_sl_visitor 00472 <_Overlay_helper<Arr_overlay_traits_2<Geometry_traits_2,ArrangementA_, 00473 ArrangementB_>, 00474 ArrangementA_, ArrangementB_>, OverlayTraits_> 00475 { 00476 typedef ArrangementA_ ArrangementA_2; 00477 typedef ArrangementB_ ArrangementB_2; 00478 typedef Arr Arrangement_result_2; 00479 typedef OverlayTraits_ Overlay_traits; 00480 00481 typedef Arr_overlay_traits_2<Geometry_traits_2,ArrangementA_2, 00482 ArrangementB_2> Geom_ovl_traits_2; 00483 00484 typedef _Overlay_helper<Geom_ovl_traits_2,ArrangementA_2,ArrangementB_2> 00485 Ovl_helper; 00486 00487 typedef Arr_overlay_sl_visitor<Ovl_helper,Overlay_traits> Base; 00488 00489 typedef typename Base::Traits_2 Traits_2; 00490 typedef typename Base::Event Event; 00491 typedef typename Base::Subcurve Subcurve; 00492 00493 Sweep_line_overlay_visitor(const ArrangementA_2 * arrA, 00494 const ArrangementB_2 * arrB, 00495 Arrangement_result_2 * arr_res, 00496 Overlay_traits * overlay_tr) : 00497 Base(arrA, arrB, arr_res, overlay_tr) 00498 {} 00499 }; 00500 00501 typedef Arr_inc_insertion_zone_visitor<Arr> Zone_insertion_visitor; 00502 00503 typedef Arr_naive_point_location<Arr> Default_point_location_strategy; 00505 00507 00508 00517 void notify_on_boundary_vertex_creation(Vertex * v, 00518 const X_monotone_curve_2 & xc, 00519 Arr_curve_end ind, 00520 Arr_parameter_space ps_x, 00521 Arr_parameter_space ps_y); 00522 00534 std::pair<bool, bool> 00535 face_split_after_edge_insertion(const Halfedge * prev1, 00536 const Halfedge * prev2, 00537 const X_monotone_curve_2 & /*cv*/) const 00538 { 00539 CGAL_precondition(prev1->is_on_inner_ccb()); 00540 CGAL_precondition(prev2->is_on_inner_ccb()); 00541 CGAL_precondition(prev1->inner_ccb() == prev2->inner_ccb()); 00542 00543 // In case of a planar topology, connecting two vertices on the same 00544 // inner CCB closes a new face that becomes a hole in the original face: 00545 return (std::make_pair(true, true)); 00546 } 00547 00554 bool hole_creation_after_edge_removal(const Halfedge * he) const 00555 { 00556 CGAL_precondition(!he->is_on_inner_ccb()); 00557 CGAL_precondition(!he->opposite()->is_on_inner_ccb()); 00558 00559 /* Check whether the halfedge and its twin belong to the same outer CCB 00560 * (and are therefore incident to the same face). 00561 * If they do, cut an antenna. That is, seperate a new hole from the outer 00562 * CCB of the face (return true). 00563 * Otherwise, the edge separates two faces. When removed, these two faces 00564 * will be merged, but no new hole will be created (return false). 00565 */ 00566 return (he->outer_ccb() == he->opposite()->outer_ccb()); 00567 } 00568 00589 bool is_on_new_perimetric_face_boundary(const Halfedge * prev1, 00590 const Halfedge * prev2, 00591 const X_monotone_curve_2 & xc, 00592 bool try_other_way = true) const; 00593 00601 bool boundaries_of_same_face(const Halfedge * /* e1 */, 00602 const Halfedge * /* e2 */) const 00603 { 00604 // This function is never called in case of an arrangement on a sphere: 00605 CGAL_error(); 00606 return false; 00607 } 00608 00616 bool is_in_face(const Face * f, const Point_2 & p, const Vertex * v) const; 00617 00624 Comparison_result compare_y_at_x(const Point_2 & p, 00625 const Halfedge * he) const; 00626 00636 bool are_equal(const Vertex * v, 00637 const X_monotone_curve_2 & xc, Arr_curve_end ind, 00638 Arr_parameter_space ps_x, Arr_parameter_space ps_y) const; 00639 00651 CGAL::Object place_boundary_vertex(Face * f, 00652 const X_monotone_curve_2 & xc, 00653 Arr_curve_end ind, 00654 Arr_parameter_space ps_x, 00655 Arr_parameter_space ps_y); 00656 00669 Halfedge * locate_around_boundary_vertex(Vertex * v, 00670 const X_monotone_curve_2 & cv, 00671 Arr_curve_end ind, 00672 Arr_parameter_space ps_x, 00673 Arr_parameter_space ps_y) const; 00674 00683 CGAL::Object locate_curve_end(const X_monotone_curve_2 & xc, Arr_curve_end ce, 00684 Arr_parameter_space ps_x, 00685 Arr_parameter_space ps_y); 00686 00694 Halfedge * split_fictitious_edge(Halfedge * /* e */, Vertex * /* v */) 00695 { 00696 // There are no fictitious halfedges: 00697 CGAL_error(); 00698 return NULL; 00699 } 00700 00705 bool is_unbounded(const Face * /* f */) const 00706 { 00707 // All faces on a sphere are bounded: 00708 return false; 00709 } 00710 00715 bool is_redundant(const Vertex * v) const; 00716 00723 Halfedge * erase_redundant_vertex(Vertex * v); 00724 00726 00731 const Face* reference_face() const 00732 { 00733 return spherical_face(); 00734 } 00735 00737 00742 Face* reference_face() 00743 { 00744 return spherical_face(); 00745 } 00746 00748 00749 protected: 00750 00752 00753 00761 const X_monotone_curve_2 & _curve(const Vertex * v, 00762 Arr_curve_end & ind) const; 00763 00768 Halfedge * 00769 _locate_around_vertex_on_discontinuity(Vertex * v, 00770 const X_monotone_curve_2 & xc, 00771 Arr_curve_end ind) const; 00772 00777 Halfedge * _locate_around_pole(Vertex * v, const X_monotone_curve_2 & xc, 00778 Arr_curve_end ind) const; 00779 00780 00784 Face * _face_below_vertex_on_discontinuity(Vertex * v) const; 00785 00787 }; 00788 00789 CGAL_END_NAMESPACE 00790 00791 #include <CGAL/Arr_topology_traits/Arr_spherical_topology_traits_2_impl.h> 00792 00793 #endif
1.7.6.1
