|
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_unb_planar_topology_traits_2.h $ 00015 // $Id: Arr_unb_planar_topology_traits_2.h 50366 2009-07-05 12:56:48Z efif $ 00016 // 00017 // 00018 // Author(s) : Ron Wein <wein@post.tau.ac.il> 00019 // Efi Fogel <efif@post.tau.ac.il> 00020 00021 #ifndef CGAL_ARR_UNB_PLANAR_TOPOLOGY_TRAITS_2_H 00022 #define CGAL_ARR_UNB_PLANAR_TOPOLOGY_TRAITS_2_H 00023 00028 #include <CGAL/Arr_tags.h> 00029 #include <CGAL/Arr_topology_traits/Arr_planar_topology_traits_base_2.h> 00030 #include <CGAL/Arr_topology_traits/Arr_unb_planar_construction_helper.h> 00031 #include <CGAL/Arr_topology_traits/Arr_unb_planar_insertion_helper.h> 00032 #include <CGAL/Arr_topology_traits/Arr_unb_planar_overlay_helper.h> 00033 #include <CGAL/Arr_topology_traits/Arr_unb_planar_batched_pl_helper.h> 00034 #include <CGAL/Arr_topology_traits/Arr_unb_planar_vert_decomp_helper.h> 00035 #include <CGAL/Arr_topology_traits/Arr_inc_insertion_zone_visitor.h> 00036 00037 CGAL_BEGIN_NAMESPACE 00038 00039 // Forward declaration: 00040 template <class GeomTraits_, class TopTraits_> 00041 class Arrangement_on_surface_2; 00042 00047 template <class GeomTraits_, 00048 class Dcel_ = Arr_default_dcel<GeomTraits_> > 00049 class Arr_unb_planar_topology_traits_2 : 00050 public Arr_planar_topology_traits_base_2<GeomTraits_, Dcel_> 00051 { 00052 private: 00053 00054 typedef Arr_planar_topology_traits_base_2<GeomTraits_, 00055 Dcel_> Base; 00056 00057 public: 00058 00060 00061 typedef GeomTraits_ Geometry_traits_2; 00062 typedef typename Base::Point_2 Point_2; 00063 typedef typename Base::X_monotone_curve_2 X_monotone_curve_2; 00065 00067 00068 typedef Dcel_ Dcel; 00069 typedef typename Base::Size Size; 00070 typedef typename Base::Vertex Vertex; 00071 typedef typename Base::Halfedge Halfedge; 00072 typedef typename Base::Face Face; 00073 typedef typename Base::Outer_ccb Outer_ccb; 00074 typedef typename Base::Inner_ccb Inner_ccb; 00075 typedef typename Base::Isolated_vertex Isolated_vertex; 00077 00078 // TODO remove adaptor as top-traits might be instantiated by Aos_2 itself 00079 typedef Arr_traits_basic_adaptor_2<Geometry_traits_2> Traits_adaptor_2; 00080 00081 typedef Arr_unb_planar_topology_traits_2<Geometry_traits_2, 00082 Dcel> Self; 00083 00085 00086 // are inherited from the geometry traits 00087 typedef typename Traits_adaptor_2::Arr_left_side_tag Arr_left_side_tag; 00088 typedef typename Traits_adaptor_2::Arr_bottom_side_tag Arr_bottom_side_tag; 00089 typedef typename Traits_adaptor_2::Arr_top_side_tag Arr_top_side_tag; 00090 typedef typename Traits_adaptor_2::Arr_right_side_tag Arr_right_side_tag; 00091 00092 BOOST_MPL_ASSERT( 00093 (boost::mpl::or_< 00094 boost::is_same< Arr_left_side_tag, Arr_oblivious_side_tag >, 00095 boost::is_same< Arr_left_side_tag, Arr_open_side_tag > > 00096 ) 00097 ); 00098 BOOST_MPL_ASSERT( 00099 (boost::mpl::or_< 00100 boost::is_same< Arr_bottom_side_tag, Arr_oblivious_side_tag >, 00101 boost::is_same< Arr_bottom_side_tag, Arr_open_side_tag > > 00102 ) 00103 ); 00104 BOOST_MPL_ASSERT( 00105 (boost::mpl::or_< 00106 boost::is_same< Arr_top_side_tag, Arr_oblivious_side_tag >, 00107 boost::is_same< Arr_top_side_tag, Arr_open_side_tag > > 00108 ) 00109 ); 00110 BOOST_MPL_ASSERT( 00111 (boost::mpl::or_< 00112 boost::is_same< Arr_right_side_tag, Arr_oblivious_side_tag >, 00113 boost::is_same< Arr_right_side_tag, Arr_open_side_tag > > 00114 ) 00115 ); 00117 00122 template<typename T, typename D> 00123 struct rebind 00124 { 00125 typedef Arr_unb_planar_topology_traits_2<T,D> other; 00126 }; 00127 00128 protected: 00129 00130 // Data members: 00131 Vertex *v_bl; // A fictitious vertex at (-oo,-oo). 00132 Vertex *v_tl; // A fictitious vertex at (-oo,+oo). 00133 Vertex *v_br; // A fictitious vertex at (-oo,+oo). 00134 Vertex *v_tr; // A fictitious vertex at (+oo,+oo). 00135 Size n_inf_verts; // Number of vertices at infinity. 00136 Face *fict_face; // The fictitious DCEL face. 00137 00138 // Copy constructor and assignment operator - not supported. 00139 Arr_unb_planar_topology_traits_2 (const Self& ); 00140 Self& operator= (const Self& ); 00141 00142 public: 00143 00145 00146 00148 Arr_unb_planar_topology_traits_2 (); 00149 00151 Arr_unb_planar_topology_traits_2 (const Geometry_traits_2 *tr); 00152 00154 void assign (const Self& other); 00156 00158 00159 00161 bool is_empty_dcel () const 00162 { 00163 // An empty arrangement contains just two four vertices at infinity 00164 // and eight fictitious halfedges connecting them. 00165 return (this->m_dcel.size_of_vertices() == 4 && 00166 this->m_dcel.size_of_halfedges() == 8); 00167 } 00168 00170 bool is_concrete_vertex (const Vertex *v) const 00171 { 00172 return (! v->has_null_point()); 00173 } 00174 00176 Size number_of_concrete_vertices () const 00177 { 00178 // All vertices not lying at infinity are concrete. 00179 return (this->m_dcel.size_of_vertices() - n_inf_verts); 00180 } 00181 00183 bool is_valid_vertex (const Vertex *v) const 00184 { 00185 return (! v->has_null_point() || 00186 (v != v_bl && v != v_tl && v != v_br && v != v_tr)); 00187 } 00188 00190 Size number_of_valid_vertices () const 00191 { 00192 // All vertices, except the four fictitious one, are valid. 00193 return (this->m_dcel.size_of_vertices() - 4); 00194 } 00195 00197 bool is_valid_halfedge (const Halfedge *he) const 00198 { 00199 return (! he->has_null_curve()); 00200 } 00201 00203 Size number_of_valid_halfedges () const 00204 { 00205 // Note that we do not count fictitious halfedges (each vertex at infinity 00206 // induces two fictitious halfedges). 00207 return (this->m_dcel.size_of_halfedges() - 2*n_inf_verts); 00208 } 00209 00211 bool is_valid_face (const Face *f) const 00212 { 00213 return (! f->is_fictitious()); 00214 } 00215 00217 Size number_of_valid_faces () const 00218 { 00219 // We do not count the ficitious DCEL face. 00220 return (this->m_dcel.size_of_faces() - 1); 00221 } 00223 00224 private: 00225 00227 00228 typedef Arrangement_on_surface_2<Geometry_traits_2, Self> Arr; 00229 00230 // Type definition for the constuction sweep-line visitor. 00231 typedef Arr_construction_subcurve<Geometry_traits_2> CSubcurve; 00232 typedef Arr_construction_event<Geometry_traits_2, 00233 CSubcurve, 00234 Arr> CEvent; 00235 typedef Arr_unb_planar_construction_helper<Geometry_traits_2, 00236 Arr, 00237 CEvent, 00238 CSubcurve> CHelper; 00239 00240 // Type definition for the basic insertion sweep-line visitor. 00241 typedef Arr_basic_insertion_traits_2<Geometry_traits_2, Arr> BInsTraits; 00242 typedef Arr_construction_subcurve<BInsTraits> BISubcurve; 00243 typedef Arr_construction_event<BInsTraits, 00244 BISubcurve, 00245 Arr> BIEvent; 00246 typedef Arr_unb_planar_insertion_helper<BInsTraits, 00247 Arr, 00248 BIEvent, 00249 BISubcurve> BIHelper; 00250 00251 // Type definition for the insertion sweep-line visitor. 00252 typedef Arr_insertion_traits_2<Geometry_traits_2, Arr> InsTraits; 00253 typedef Arr_construction_subcurve<InsTraits> ISubcurve; 00254 typedef Arr_construction_event<InsTraits, 00255 ISubcurve, 00256 Arr> IEvent; 00257 typedef Arr_unb_planar_insertion_helper<InsTraits, 00258 Arr, 00259 IEvent, 00260 ISubcurve> IHelper; 00261 00262 // Type definition for the batched point-location sweep-line visitor. 00263 typedef Arr_batched_point_location_traits_2<Arr> BplTraits; 00264 typedef Arr_unb_planar_batched_pl_helper<BplTraits, Arr> BplHelper; 00265 00266 // Type definition for the vertical decomposition sweep-line visitor. 00267 typedef Arr_batched_point_location_traits_2<Arr> VdTraits; 00268 typedef Arr_unb_planar_vert_decomp_helper<VdTraits, Arr> VdHelper; 00269 00270 // Type definition for the overlay sweep-line visitor. 00271 template <class ExGeomTraits_, class ArrangementA_, class ArrangementB_> 00272 struct _Overlay_helper : public Arr_unb_planar_overlay_helper 00273 <ExGeomTraits_, ArrangementA_, ArrangementB_, Arr, 00274 Arr_construction_event<ExGeomTraits_, 00275 Arr_overlay_subcurve<ExGeomTraits_>, 00276 Arr>, 00277 Arr_overlay_subcurve<ExGeomTraits_> > 00278 { 00279 typedef Arr_unb_planar_overlay_helper 00280 <ExGeomTraits_, ArrangementA_, ArrangementB_, Arr, 00281 Arr_construction_event<ExGeomTraits_, 00282 Arr_overlay_subcurve<ExGeomTraits_>, 00283 Arr>, 00284 Arr_overlay_subcurve<ExGeomTraits_> > Base; 00285 00286 typedef typename Base::Traits_2 Traits_2; 00287 typedef typename Base::Arrangement_red_2 Arrangement_red_2; 00288 typedef typename Base::Arrangement_blue_2 Arrangement_blue_2; 00289 typedef typename Base::Arrangement_2 Arrangement_2; 00290 typedef typename Base::Event Event; 00291 typedef typename Base::Subcurve Subcurve; 00292 typedef typename Base::Construction_helper Construction_helper; 00293 00294 _Overlay_helper (const ArrangementA_ *arrA, 00295 const ArrangementB_ *arrB) : 00296 Base (arrA, arrB) 00297 {} 00298 }; 00300 00301 public: 00302 00304 00305 00306 typedef Arr_construction_sl_visitor<CHelper> 00307 Sweep_line_construction_visitor; 00308 00309 typedef Arr_insertion_sl_visitor<IHelper> 00310 Sweep_line_insertion_visitor; 00311 00312 typedef Sweep_line_construction_visitor 00313 Sweep_line_non_intersecting_construction_visitor; 00314 00315 typedef Arr_basic_insertion_sl_visitor<BIHelper> 00316 Sweep_line_non_intersecting_insertion_visitor; 00317 00318 template <class OutputIterator_> 00319 struct Sweep_line_bacthed_point_location_visitor : 00320 public Arr_batched_pl_sl_visitor<BplHelper, OutputIterator_> 00321 { 00322 typedef OutputIterator_ Output_iterator; 00323 typedef Arr_batched_pl_sl_visitor<BplHelper, 00324 Output_iterator> Base; 00325 00326 typedef typename Base::Traits_2 Traits_2; 00327 typedef typename Base::Event Event; 00328 typedef typename Base::Subcurve Subcurve; 00329 00330 Sweep_line_bacthed_point_location_visitor (const Arr *arr, 00331 Output_iterator *oi) : 00332 Base (arr, oi) 00333 {} 00334 }; 00335 00336 template <class OutputIterator_> 00337 struct Sweep_line_vertical_decomposition_visitor : 00338 public Arr_vert_decomp_sl_visitor<VdHelper, OutputIterator_> 00339 { 00340 typedef OutputIterator_ Output_iterator; 00341 typedef Arr_vert_decomp_sl_visitor<VdHelper, 00342 Output_iterator> Base; 00343 00344 typedef typename Base::Traits_2 Traits_2; 00345 typedef typename Base::Event Event; 00346 typedef typename Base::Subcurve Subcurve; 00347 00348 Sweep_line_vertical_decomposition_visitor (const Arr *arr, 00349 Output_iterator *oi) : 00350 Base (arr, oi) 00351 {} 00352 }; 00353 00354 template <class ArrangementA_, class ArrangementB_, class OverlayTraits_> 00355 struct Sweep_line_overlay_visitor : 00356 public Arr_overlay_sl_visitor 00357 <_Overlay_helper<Arr_overlay_traits_2<Geometry_traits_2, 00358 ArrangementA_, 00359 ArrangementB_>, 00360 ArrangementA_, 00361 ArrangementB_>, 00362 OverlayTraits_> 00363 { 00364 typedef ArrangementA_ ArrangementA_2; 00365 typedef ArrangementB_ ArrangementB_2; 00366 typedef Arr Arrangement_result_2; 00367 typedef OverlayTraits_ Overlay_traits; 00368 00369 typedef Arr_overlay_traits_2<Geometry_traits_2, 00370 ArrangementA_2, 00371 ArrangementB_2> Geom_ovl_traits_2; 00372 00373 typedef _Overlay_helper<Geom_ovl_traits_2, 00374 ArrangementA_2, 00375 ArrangementB_2> Ovl_helper; 00376 00377 typedef Arr_overlay_sl_visitor<Ovl_helper, 00378 Overlay_traits> Base; 00379 00380 typedef typename Base::Traits_2 Traits_2; 00381 typedef typename Base::Event Event; 00382 typedef typename Base::Subcurve Subcurve; 00383 00384 Sweep_line_overlay_visitor (const ArrangementA_2 *arrA, 00385 const ArrangementB_2 *arrB, 00386 Arrangement_result_2 *arr_res, 00387 Overlay_traits *overlay_tr) : 00388 Base (arrA, arrB, arr_res, overlay_tr) 00389 {} 00390 }; 00391 00392 typedef Arr_inc_insertion_zone_visitor<Arr> 00393 Zone_insertion_visitor; 00394 00395 typedef Arr_walk_along_line_point_location<Arr> 00396 Default_point_location_strategy; 00398 00400 00401 00405 void init_dcel (); 00406 00410 void dcel_updated (); 00411 00422 bool are_equal (const Vertex *v, 00423 const X_monotone_curve_2& cv, Arr_curve_end ind, 00424 Arr_parameter_space ps_x, Arr_parameter_space ps_y) const; 00425 00439 CGAL::Object place_boundary_vertex (Face *f, 00440 const X_monotone_curve_2& cv, 00441 Arr_curve_end ind, 00442 Arr_parameter_space ps_x, 00443 Arr_parameter_space ps_y); 00444 00457 Halfedge* 00458 locate_around_boundary_vertex (Vertex* /* v */, 00459 const X_monotone_curve_2& /* cv */, 00460 Arr_curve_end /* ind */, 00461 Arr_parameter_space /* ps_x */, 00462 Arr_parameter_space /* ps_y */) const 00463 { 00464 CGAL_error(); 00465 return (NULL); 00466 } 00467 00479 CGAL::Object locate_curve_end (const X_monotone_curve_2& cv, 00480 Arr_curve_end ind, 00481 Arr_parameter_space ps_x, 00482 Arr_parameter_space ps_y); 00483 00484 00485 00486 00487 #if CGAL_NEW_FACE_SPLIT_STRATEGY 00488 00500 std::pair<bool, bool> 00501 face_update_upon_edge_insertion(const Halfedge * 00502 CGAL_precondition_code(prev1), 00503 const Halfedge * 00504 CGAL_precondition_code(prev2), 00505 const X_monotone_curve_2 & cv) const 00506 { 00507 // In case of a planar topology, connecting two vertices on the same 00508 // inner CCB closes a new face that becomes a hole in the original face: 00509 bool prev2_outer = 00510 (cv.location(CGAL::ARR_MAX_END) == CGAL::ARR_TOP_BOUNDARY); 00511 00512 return (std::make_pair (true, prev2_outer)); 00513 } 00514 #endif 00515 00524 Halfedge* split_fictitious_edge (Halfedge *e, Vertex *v); 00525 00531 bool is_unbounded (const Face *f) const; 00532 00538 bool is_redundant (const Vertex *v) const; 00539 00547 Halfedge* erase_redundant_vertex (Vertex *v); 00548 00550 00555 const Face* reference_face() const 00556 { 00557 assert(v_tr->halfedge()->direction() == ARR_LEFT_TO_RIGHT); 00558 return v_tr->halfedge()->outer_ccb()->face(); 00559 } 00560 00562 00567 Face* reference_face() 00568 { 00569 assert(v_tr->halfedge()->direction() == ARR_LEFT_TO_RIGHT); 00570 return v_tr->halfedge()->outer_ccb()->face(); 00571 } 00572 00574 00576 00577 00579 const Face* initial_face () const 00580 { 00581 return (fict_face); 00582 } 00583 00585 const Face* fictitious_face () const 00586 { 00587 return (fict_face); 00588 } 00589 00591 Face* fictitious_face () 00592 { 00593 return (fict_face); 00594 } 00595 00597 const Vertex* bottom_left_vertex () const 00598 { 00599 return (v_bl); 00600 } 00601 00603 Vertex* bottom_left_vertex () 00604 { 00605 return (v_bl); 00606 } 00607 00609 const Vertex* top_left_vertex () const 00610 { 00611 return (v_tl); 00612 } 00613 00615 Vertex* top_left_vertex () 00616 { 00617 return (v_tl); 00618 } 00619 00621 const Vertex* bottom_right_vertex () const 00622 { 00623 return (v_br); 00624 } 00625 00627 Vertex* bottom_right_vertex () 00628 { 00629 return (v_br); 00630 } 00631 00633 const Vertex* top_right_vertex () const 00634 { 00635 return (v_tr); 00636 } 00637 00639 Vertex* top_right_vertex () 00640 { 00641 return (v_tr); 00642 } 00644 00646 00647 00654 virtual Comparison_result compare_x (const Point_2& p, 00655 const Vertex* v) const; 00656 00663 virtual Comparison_result compare_xy (const Point_2& p, 00664 const Vertex* v) const; 00665 00674 virtual Comparison_result compare_y_at_x (const Point_2& p, 00675 const Halfedge* he) const; 00677 00678 protected: 00679 00681 00682 00691 const X_monotone_curve_2* _curve (const Vertex *v, Arr_curve_end& ind) const; 00692 00705 bool _is_on_fictitious_edge (const X_monotone_curve_2& cv, Arr_curve_end ind, 00706 Arr_parameter_space ps_x, 00707 Arr_parameter_space ps_y, 00708 const Halfedge *he, 00709 bool& eq_source, bool& eq_target); 00711 }; 00712 00713 CGAL_END_NAMESPACE 00714 00715 #include <CGAL/Arr_topology_traits/Arr_unb_planar_topology_traits_2_impl.h> 00716 00717 #endif
1.7.6.1
