1 // Copyright (c) 2005,2006,2007,2008,2009,2010,2011 Tel-Aviv University (Israel). 2 // All rights reserved. 3 // 4 // This file is part of CGAL (www.cgal.org). 5 // 6 // $URL: https://github.com/CGAL/cgal/blob/v5.3/Arrangement_on_surface_2/include/CGAL/Arrangement_on_surface_2.h $ 7 // $Id: Arrangement_on_surface_2.h dc36cee 2021-03-10T11:53:16+01:00 Laurent Rineau 8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // 11 // Author(s): Ron Wein <wein@post.tau.ac.il> 12 // Efi Fogel <efif@post.tau.ac.il> 13 // Eric Berberich <ericb@post.tau.ac.il> 14 // (based on old version by: Iddo Hanniel, 15 // Eyal Flato, 16 // Oren Nechushtan, 17 // Ester Ezra, 18 // Shai Hirsch, 19 // and Eugene Lipovetsky) 20 #ifndef CGAL_ARRANGEMENT_ON_SURFACE_2_H 21 #define CGAL_ARRANGEMENT_ON_SURFACE_2_H 22 23 #include <CGAL/license/Arrangement_on_surface_2.h> 24 25 #include <CGAL/disable_warnings.h> 26 27 /*! \file 28 * The header file for the Arrangement_on_surface_2<Traits,Dcel> class. 29 */ 30 31 #include <map> 32 #include <vector> 33 #include <algorithm> 34 #include <boost/mpl/assert.hpp> 35 36 #include <CGAL/Arr_tags.h> 37 #include <CGAL/Arr_enums.h> 38 #include <CGAL/HalfedgeDS_iterator.h> 39 #include <CGAL/Arrangement_2/Arrangement_2_iterators.h> 40 #include <CGAL/In_place_list.h> 41 #include <CGAL/Arr_default_dcel.h> 42 #include <CGAL/Arr_observer.h> 43 #include <CGAL/Arr_accessor.h> 44 #include <CGAL/Arrangement_2/Arr_traits_adaptor_2.h> 45 #include <CGAL/function_objects.h> 46 #include <CGAL/Iterator_project.h> 47 #include <CGAL/Iterator_transform.h> 48 49 #include <boost/pool/pool_alloc.hpp> 50 51 namespace CGAL { 52 53 /*! \class Arrangement_on_surface_2 54 * The arrangement class, representing 2-dimensional subdivisions induced on 55 * an arbitrary surface by a set of arbitrary planar curves. 56 * The GeomTraits parameter corresponds to a geometry-traits class that 57 * defines the Point_2 and X_monotone_curve_2 types and implements the 58 * geometric predicates and constructions for the family of curves it defines. 59 * The TopTraits parameter corresponds to a topology-traits class that defines 60 * the topological structure of the surface. Note that the geometry traits 61 * class should also be aware of the kind of surface on which its curves and 62 * points are defined. 63 */ 64 template <typename GeomTraits_, typename TopTraits_> 65 class Arrangement_on_surface_2 { 66 public: 67 typedef GeomTraits_ Geometry_traits_2; 68 typedef TopTraits_ Topology_traits; 69 typedef boost::fast_pool_allocator<int> Allocator; 70 71 // first define adaptor ... 72 typedef Arr_traits_basic_adaptor_2<Geometry_traits_2> Traits_adaptor_2; 73 74 // .. as it completes (potentially) missing side tags 75 typedef typename Traits_adaptor_2::Left_side_category Left_side_category; 76 typedef typename Traits_adaptor_2::Bottom_side_category Bottom_side_category; 77 typedef typename Traits_adaptor_2::Top_side_category Top_side_category; 78 typedef typename Traits_adaptor_2::Right_side_category Right_side_category; 79 80 BOOST_MPL_ASSERT( 81 (typename 82 Arr_sane_identified_tagging<Left_side_category, 83 Bottom_side_category, 84 Top_side_category, 85 Right_side_category>::result) 86 ); 87 88 public: 89 typedef Arrangement_on_surface_2<Geometry_traits_2, Topology_traits> 90 Self; 91 92 typedef typename Geometry_traits_2::Point_2 Point_2; 93 typedef typename Geometry_traits_2::X_monotone_curve_2 X_monotone_curve_2; 94 95 // maybe remove this in a future version (that supports complete handling 96 // of all sides) 97 typedef typename Arr_are_all_sides_oblivious_tag<Left_side_category, 98 Bottom_side_category, 99 Top_side_category, 100 Right_side_category>::result 101 Are_all_sides_oblivious_category; 102 103 typedef typename Arr_has_identified_sides<Left_side_category, 104 Bottom_side_category>::result 105 Has_identified_sides_category; 106 107 typedef typename Arr_two_sides_category<Bottom_side_category, 108 Top_side_category>::result 109 Top_or_bottom_sides_category; 110 111 public: 112 typedef typename Topology_traits::Dcel Dcel; 113 typedef typename Dcel::Size Size; 114 115 protected: 116 friend class Arr_observer<Self>; 117 friend class Arr_accessor<Self>; 118 119 // Internal DCEL types: 120 typedef typename Dcel::Vertex DVertex; 121 typedef typename Dcel::Halfedge DHalfedge; 122 typedef typename Dcel::Face DFace; 123 typedef typename Dcel::Outer_ccb DOuter_ccb; 124 typedef typename Dcel::Inner_ccb DInner_ccb; 125 typedef typename Dcel::Isolated_vertex DIso_vertex; 126 127 typedef typename Dcel::difference_type DDifference; 128 typedef typename Dcel::iterator_category DIterator_category; 129 130 typedef typename Dcel::Vertex_iterator DVertex_iter; 131 typedef typename Dcel::Vertex_const_iterator DVertex_const_iter; 132 133 typedef typename Dcel::Halfedge_iterator DHalfedge_iter; 134 typedef typename Dcel::Halfedge_const_iterator DHalfedge_const_iter; 135 136 typedef typename Dcel::Edge_iterator DEdge_iter; 137 typedef typename Dcel::Edge_const_iterator DEdge_const_iter; 138 139 typedef typename Dcel::Face_iterator DFace_iter; 140 typedef typename Dcel::Face_const_iterator DFace_const_iter; 141 142 typedef typename DFace::Outer_ccb_iterator DOuter_ccb_iter; 143 typedef typename DFace::Outer_ccb_const_iterator DOuter_ccb_const_iter; 144 145 typedef typename DFace::Inner_ccb_iterator DInner_ccb_iter; 146 typedef typename DFace::Inner_ccb_const_iterator DInner_ccb_const_iter; 147 148 typedef typename DFace::Isolated_vertex_iterator DIso_vertex_iter; 149 typedef typename DFace::Isolated_vertex_const_iterator 150 DIso_vertex_const_iter; 151 152 protected: 153 /*! \class 154 * A functor for filtering DCEL vertices at infinity. 155 */ 156 class _Is_concrete_vertex { 157 private: 158 const Topology_traits* m_topol_traits; 159 160 public: _Is_concrete_vertex()161 _Is_concrete_vertex() : m_topol_traits(nullptr) {} 162 _Is_concrete_vertex(const Topology_traits * topol_traits)163 _Is_concrete_vertex(const Topology_traits* topol_traits) : 164 m_topol_traits(topol_traits) 165 {} 166 operator()167 bool operator()(const DVertex& v) const 168 { 169 if (m_topol_traits == nullptr) 170 return true; 171 172 return (m_topol_traits->is_concrete_vertex(&v)); 173 } 174 }; 175 176 /*! \class 177 * A functor for filtering fictitious DCEL vertices. 178 */ 179 class _Is_valid_vertex { 180 private: 181 const Topology_traits* m_topol_traits; 182 183 public: _Is_valid_vertex()184 _Is_valid_vertex() : m_topol_traits(nullptr) {} 185 _Is_valid_vertex(const Topology_traits * topol_traits)186 _Is_valid_vertex(const Topology_traits* topol_traits) : 187 m_topol_traits(topol_traits) 188 {} 189 operator()190 bool operator()(const DVertex& v) const 191 { 192 if (m_topol_traits == nullptr) 193 return true; 194 195 return (m_topol_traits->is_valid_vertex(&v)); 196 } 197 }; 198 199 /*! \struct 200 * A functor for filtering fictitious DCEL halfedges. 201 */ 202 class _Is_valid_halfedge { 203 private: 204 const Topology_traits* m_topol_traits; 205 206 public: _Is_valid_halfedge()207 _Is_valid_halfedge() : m_topol_traits(nullptr) {} 208 _Is_valid_halfedge(const Topology_traits * topol_traits)209 _Is_valid_halfedge(const Topology_traits* topol_traits) : 210 m_topol_traits(topol_traits) 211 {} 212 operator()213 bool operator()(const DHalfedge& he) const 214 { 215 if (m_topol_traits == nullptr) 216 return true; 217 218 return (m_topol_traits->is_valid_halfedge(&he)); 219 } 220 }; 221 222 /*! \struct 223 * A functor for filtering the fictitious faces. 224 */ 225 class _Is_valid_face { 226 private: 227 const Topology_traits* m_topol_traits; 228 229 public: _Is_valid_face()230 _Is_valid_face() : m_topol_traits(nullptr) {} 231 _Is_valid_face(const Topology_traits * topol_traits)232 _Is_valid_face(const Topology_traits* topol_traits) : 233 m_topol_traits(topol_traits) 234 {} 235 operator()236 bool operator()(const DFace& f) const 237 { 238 if (m_topol_traits == nullptr) 239 return true; 240 241 return (m_topol_traits->is_valid_face(&f)); 242 } 243 }; 244 245 /*! \struct 246 * A functor for filtering bounded faces. 247 */ 248 class _Is_unbounded_face { 249 private: 250 const Topology_traits* m_topol_traits; 251 252 public: _Is_unbounded_face()253 _Is_unbounded_face() : m_topol_traits(nullptr) {} 254 _Is_unbounded_face(const Topology_traits * topol_traits)255 _Is_unbounded_face(const Topology_traits* topol_traits) : 256 m_topol_traits(topol_traits) 257 {} 258 topology_traits()259 const Topology_traits* topology_traits() const { return m_topol_traits; } 260 operator()261 bool operator()(const DFace& f) const 262 { 263 return (m_topol_traits->is_valid_face(&f) && 264 m_topol_traits->is_unbounded(&f)); 265 } 266 }; 267 268 public: 269 // Forward declerations: 270 class Vertex; 271 class Halfedge; 272 class Face; 273 274 // Definition of the halfedge data-structure itereators and circulators: 275 typedef I_Filtered_iterator<DVertex_iter, _Is_concrete_vertex, 276 Vertex, DDifference, DIterator_category> 277 Vertex_iterator; 278 279 typedef I_Filtered_const_iterator<DVertex_const_iter, _Is_concrete_vertex, 280 DVertex_iter, Vertex, DDifference, 281 DIterator_category> 282 Vertex_const_iterator; 283 284 typedef I_Filtered_iterator<DHalfedge_iter, _Is_valid_halfedge, 285 Halfedge, DDifference, DIterator_category> 286 Halfedge_iterator; 287 288 typedef I_Filtered_const_iterator<DHalfedge_const_iter, _Is_valid_halfedge, 289 DHalfedge_iter, Halfedge, DDifference, 290 DIterator_category> 291 Halfedge_const_iterator; 292 293 /*! \class 294 * Edges iterator - defined as a derived class to make it assignable 295 * to the halfedge iterator type. 296 */ 297 class Edge_iterator : 298 public I_Filtered_iterator<DEdge_iter, _Is_valid_halfedge, 299 Halfedge, DDifference, DIterator_category> 300 { 301 typedef I_Filtered_iterator<DEdge_iter, _Is_valid_halfedge, 302 Halfedge, DDifference, DIterator_category> 303 Base; 304 305 public: Edge_iterator()306 Edge_iterator() {} 307 Edge_iterator(DEdge_iter iter,DEdge_iter iend,const _Is_valid_halfedge & pred)308 Edge_iterator(DEdge_iter iter, DEdge_iter iend, 309 const _Is_valid_halfedge& pred) : 310 Base(iter, iend, pred) 311 {} 312 Edge_iterator(const Base & base)313 Edge_iterator(const Base& base) : 314 Base(base) 315 {} 316 317 // Casting to a halfedge iterator. Halfedge_iterator()318 operator Halfedge_iterator() const 319 { 320 return (Halfedge_iterator(DHalfedge_iter(this->current_iterator()))); 321 } 322 Halfedge_const_iterator()323 operator Halfedge_const_iterator() const 324 { 325 return (Halfedge_const_iterator 326 (DHalfedge_const_iter(this->current_iterator()))); 327 } 328 }; 329 330 class Edge_const_iterator : 331 public I_Filtered_const_iterator<DEdge_const_iter, _Is_valid_halfedge, 332 DEdge_iter, Halfedge, DDifference, 333 DIterator_category> 334 { 335 typedef I_Filtered_const_iterator<DEdge_const_iter, _Is_valid_halfedge, 336 DEdge_iter, Halfedge, DDifference, 337 DIterator_category> Base; 338 339 public: Edge_const_iterator()340 Edge_const_iterator() {} 341 Edge_const_iterator(Edge_iterator iter)342 Edge_const_iterator(Edge_iterator iter) : 343 Base(iter.current_iterator(), iter.past_the_end(), iter.filter()) 344 {} 345 Edge_const_iterator(DEdge_const_iter iter,DEdge_const_iter iend,const _Is_valid_halfedge & pred)346 Edge_const_iterator(DEdge_const_iter iter, DEdge_const_iter iend, 347 const _Is_valid_halfedge& pred) : 348 Base(iter, iend, pred) 349 {} 350 Edge_const_iterator(const Base & base)351 Edge_const_iterator(const Base& base) : 352 Base(base) 353 {} 354 355 // Casting to a halfedge iterator. Halfedge_const_iterator()356 operator Halfedge_const_iterator() const 357 { 358 return (Halfedge_const_iterator 359 (DHalfedge_const_iter(this->current_iterator()))); 360 } 361 }; 362 363 typedef I_Filtered_iterator<DFace_iter, _Is_valid_face, 364 Face, DDifference, 365 DIterator_category> Face_iterator; 366 367 typedef I_Filtered_const_iterator<DFace_const_iter, _Is_valid_face, 368 DFace_iter, Face, 369 DDifference, DIterator_category> 370 Face_const_iterator; 371 372 typedef _HalfedgeDS_vertex_circ<Halfedge, Halfedge_iterator, 373 Bidirectional_circulator_tag> 374 Halfedge_around_vertex_circulator; 375 376 typedef _HalfedgeDS_vertex_const_circ<Halfedge, Halfedge_const_iterator, 377 Bidirectional_circulator_tag> 378 Halfedge_around_vertex_const_circulator; 379 380 typedef _HalfedgeDS_facet_circ<Halfedge, Halfedge_iterator, 381 Bidirectional_circulator_tag> 382 Ccb_halfedge_circulator; 383 384 typedef _HalfedgeDS_facet_const_circ<Halfedge, Halfedge_const_iterator, 385 Bidirectional_circulator_tag> 386 Ccb_halfedge_const_circulator; 387 388 /*! \class 389 * Unbounded faces iterator - defined as a derived class to make it 390 * assignable to the face iterator type. 391 */ 392 class Unbounded_face_iterator : 393 public I_Filtered_iterator<DFace_iter, _Is_unbounded_face, 394 Face, DDifference, DIterator_category> 395 { 396 typedef I_Filtered_iterator<DFace_iter, _Is_unbounded_face, 397 Face, DDifference, DIterator_category> 398 Base; 399 400 public: Unbounded_face_iterator()401 Unbounded_face_iterator() {} 402 Unbounded_face_iterator(DFace_iter iter,DFace_iter iend,const _Is_unbounded_face & is_unbounded)403 Unbounded_face_iterator(DFace_iter iter, DFace_iter iend, 404 const _Is_unbounded_face& is_unbounded) : 405 Base(iter, iend, is_unbounded) 406 {} 407 408 // Casting to a face iterator. Face_iterator()409 operator Face_iterator() const 410 { 411 return (Face_iterator(DFace_iter(this->current_iterator()), 412 DFace_iter(this->past_the_end()), 413 _Is_valid_face(this->filter().topology_traits()))); 414 } 415 Face_const_iterator()416 operator Face_const_iterator() const 417 { 418 return (Face_const_iterator 419 (DFace_const_iter(this->current_iterator()), 420 DFace_const_iter(this->past_the_end()), 421 _Is_valid_face(this->filter().topology_traits()))); 422 } 423 }; 424 425 class Unbounded_face_const_iterator : 426 public I_Filtered_const_iterator<DFace_const_iter, _Is_unbounded_face, 427 DFace_iter, Face, DDifference, 428 DIterator_category> 429 { 430 typedef I_Filtered_const_iterator<DFace_const_iter, _Is_unbounded_face, 431 DFace_iter, Face, DDifference, 432 DIterator_category> Base; 433 434 public: Unbounded_face_const_iterator()435 Unbounded_face_const_iterator() {} 436 Unbounded_face_const_iterator(Unbounded_face_iterator iter)437 Unbounded_face_const_iterator(Unbounded_face_iterator iter) : Base(iter) {} 438 Unbounded_face_const_iterator(DFace_const_iter iter,DFace_const_iter iend,const _Is_unbounded_face & is_unbounded)439 Unbounded_face_const_iterator(DFace_const_iter iter, 440 DFace_const_iter iend, 441 const _Is_unbounded_face& is_unbounded) : 442 Base(iter, iend, is_unbounded) 443 {} 444 Unbounded_face_const_iterator(const Base & base)445 Unbounded_face_const_iterator(const Base& base) : 446 Base(base) 447 {} 448 449 // Casting to a face iterator. Face_const_iterator()450 operator Face_const_iterator() const 451 { 452 return (Face_const_iterator(DFace_const_iter(this->current_iterator()), 453 DFace_const_iter(this->past_the_end()))); 454 } 455 }; 456 457 protected: 458 struct _Halfedge_to_ccb_circulator { 459 typedef DHalfedge* argument_type; 460 typedef Ccb_halfedge_circulator result_type; 461 operator_Halfedge_to_ccb_circulator462 result_type operator()(argument_type s) const 463 { return Ccb_halfedge_circulator(Halfedge_iterator(s)); } 464 }; 465 466 struct _Const_halfedge_to_ccb_circulator { 467 typedef const DHalfedge* argument_type; 468 typedef Ccb_halfedge_const_circulator result_type; 469 operator_Const_halfedge_to_ccb_circulator470 result_type operator()(argument_type s) const 471 { return Ccb_halfedge_const_circulator(Halfedge_const_iterator(s)); } 472 }; 473 474 typedef Cast_function_object<DVertex, Vertex> _Vertex_to_vertex; 475 476 public: 477 typedef Iterator_transform<DOuter_ccb_iter, _Halfedge_to_ccb_circulator> 478 Outer_ccb_iterator; 479 480 typedef Iterator_transform<DOuter_ccb_const_iter, 481 _Const_halfedge_to_ccb_circulator> 482 Outer_ccb_const_iterator; 483 484 typedef Iterator_transform<DInner_ccb_iter, _Halfedge_to_ccb_circulator> 485 Inner_ccb_iterator; 486 487 typedef Iterator_transform<DInner_ccb_const_iter, 488 _Const_halfedge_to_ccb_circulator> 489 Inner_ccb_const_iterator; 490 491 /*! \class 492 * Isolated vertices iterator - defined as a class to make it assignable 493 * to the vertex iterator type. 494 */ 495 class Isolated_vertex_iterator : 496 public Iterator_project<DIso_vertex_iter, _Vertex_to_vertex> 497 { 498 typedef Iterator_project<DIso_vertex_iter, _Vertex_to_vertex> Base; 499 500 public: Isolated_vertex_iterator()501 Isolated_vertex_iterator() {} 502 Isolated_vertex_iterator(DIso_vertex_iter iter)503 Isolated_vertex_iterator(DIso_vertex_iter iter) : Base(iter) {} 504 505 // Casting to a vertex iterator. Vertex_iterator()506 operator Vertex_iterator() const 507 { return (Vertex_iterator(DVertex_iter(this->ptr()))); } 508 Vertex_const_iterator()509 operator Vertex_const_iterator() const 510 { return (Vertex_const_iterator(DVertex_const_iter(this->ptr()))); } 511 }; 512 513 class Isolated_vertex_const_iterator : 514 public Iterator_project<DIso_vertex_const_iter, _Vertex_to_vertex> 515 { 516 typedef Iterator_project<DIso_vertex_const_iter, _Vertex_to_vertex> Base; 517 518 public: Isolated_vertex_const_iterator()519 Isolated_vertex_const_iterator() {} 520 Isolated_vertex_const_iterator(Isolated_vertex_iterator iter)521 Isolated_vertex_const_iterator(Isolated_vertex_iterator iter) : 522 Base(iter) 523 {} 524 Isolated_vertex_const_iterator(DIso_vertex_const_iter iter)525 Isolated_vertex_const_iterator(DIso_vertex_const_iter iter) : 526 Base(iter) 527 {} 528 529 // Casting to a vertex iterator. Vertex_const_iterator()530 operator Vertex_const_iterator() const 531 { return (Vertex_const_iterator(DVertex_const_iter(this->ptr()))); } 532 }; 533 534 protected: 535 class _Valid_vertex_iterator : 536 public I_Filtered_iterator<DVertex_iter, _Is_valid_vertex, Vertex, 537 DDifference, DIterator_category> 538 { 539 typedef I_Filtered_iterator<DVertex_iter, _Is_valid_vertex, Vertex, 540 DDifference, DIterator_category> Base; 541 542 public: _Valid_vertex_iterator()543 _Valid_vertex_iterator() {} 544 _Valid_vertex_iterator(DVertex_iter iter,DVertex_iter iend,const _Is_valid_vertex & pred)545 _Valid_vertex_iterator(DVertex_iter iter, DVertex_iter iend, 546 const _Is_valid_vertex& pred) : 547 Base(iter, iend, pred) 548 {} 549 550 // Casting to a vertex iterator. Vertex_iterator()551 operator Vertex_iterator() const 552 { return (Vertex_iterator(DVertex_iter(this->current_iterator()))); } 553 Vertex_const_iterator()554 operator Vertex_const_iterator() const 555 { 556 return (Vertex_const_iterator(DVertex_const_iter 557 (this->current_iterator()))); 558 } 559 }; 560 561 public: 562 // Definition of handles (equivalent to iterators): 563 typedef Vertex_iterator Vertex_handle; 564 typedef Halfedge_iterator Halfedge_handle; 565 typedef Face_iterator Face_handle; 566 567 typedef Vertex_const_iterator Vertex_const_handle; 568 typedef Halfedge_const_iterator Halfedge_const_handle; 569 typedef Face_const_iterator Face_const_handle; 570 571 /*! \class 572 * The arrangement vertex class. 573 */ 574 class Vertex : public DVertex { 575 typedef DVertex Base; 576 577 public: 578 /*! Default constrcutor. */ Vertex()579 Vertex() {} 580 581 /*! Check whether the vertex lies on an open boundary. */ is_at_open_boundary()582 bool is_at_open_boundary() const { return (Base::has_null_point()); } 583 584 /*! Get the vertex degree (number of incident edges). */ degree()585 Size degree() const 586 { 587 if (this->is_isolated()) 588 return (0); 589 590 // Go around the vertex and count the incident halfedges. 591 const DHalfedge* he_first = Base::halfedge(); 592 const DHalfedge* he_curr = he_first; 593 Size n = 0; 594 595 if (he_curr != nullptr) { 596 do { 597 ++n; 598 he_curr = he_curr->next()->opposite(); 599 } while (he_curr != he_first); 600 } 601 return (n); 602 } 603 604 /*! 605 * Get the incident halfedges (non-const version). 606 * \pre The vertex is not isolated. 607 */ incident_halfedges()608 Halfedge_around_vertex_circulator incident_halfedges() 609 { 610 CGAL_precondition(! this->is_isolated()); 611 return Halfedge_around_vertex_circulator 612 (DHalfedge_iter(Base::halfedge())); 613 } 614 615 /*! 616 * Get the incident halfedges (const version). 617 * \pre The vertex is not isolated. 618 */ incident_halfedges()619 Halfedge_around_vertex_const_circulator incident_halfedges() const 620 { 621 CGAL_precondition(! this->is_isolated()); 622 return Halfedge_around_vertex_const_circulator 623 (DHalfedge_const_iter(Base::halfedge())); 624 } 625 626 /*! 627 * Get the face that contains the vertex (non-const version). 628 * \pre The vertex is isolated. 629 */ face()630 Face_handle face() 631 { 632 CGAL_precondition(this->is_isolated()); 633 return (DFace_iter(Base::isolated_vertex()->face())); 634 } 635 636 /*! 637 * Get the face that contains the vertex (const version). 638 * \pre The vertex is isolated. 639 */ face()640 Face_const_handle face() const 641 { 642 CGAL_precondition(this->is_isolated()); 643 return (DFace_const_iter(Base::isolated_vertex()->face())); 644 } 645 646 647 private: 648 // Blocking access to inherited functions from the Dcel::Vertex. 649 bool has_null_point() const; 650 void set_point(Point_2* ); 651 void set_boundary(Arr_parameter_space , Arr_parameter_space ); 652 const DHalfedge* halfedge() const; 653 DHalfedge* halfedge(); 654 void set_halfedge(DHalfedge* ); 655 const DIso_vertex* isolated_vertex() const; 656 DIso_vertex* isolated_vertex(); 657 void set_isolated_vertex(DIso_vertex* ); 658 }; 659 660 /*! 661 * \class The arrangement halfedge class. 662 */ 663 class Halfedge : public DHalfedge { 664 typedef DHalfedge Base; 665 666 public: 667 /*! Default constrcutor. */ Halfedge()668 Halfedge() {} 669 670 /*! Check whether the halfedge is fictitious. */ is_fictitious()671 bool is_fictitious() const 672 { return (Base::has_null_curve()); } 673 674 /*! Get the source vertex (non-const version). */ source()675 Vertex_handle source() 676 { return (DVertex_iter(Base::opposite()->vertex())); } 677 678 /*! Get the source vertex (const version). */ source()679 Vertex_const_handle source() const 680 { return (DVertex_const_iter(Base::opposite()->vertex())); } 681 682 /*! Get the target vertex (non-const version). */ target()683 Vertex_handle target() 684 { return (DVertex_iter(Base::vertex())); } 685 686 /*! Get the target vertex (const version). */ target()687 Vertex_const_handle target() const 688 { return (DVertex_const_iter(Base::vertex())); } 689 690 /*! Get the incident face (non-const version). */ face()691 Face_handle face() 692 { 693 return (! Base::is_on_inner_ccb()) ? 694 DFace_iter(Base::outer_ccb()->face()) : 695 DFace_iter(Base::inner_ccb()->face()); 696 } 697 698 /*! Get the incident face (const version). */ face()699 Face_const_handle face() const 700 { 701 return (! Base::is_on_inner_ccb()) ? 702 DFace_const_iter(Base::outer_ccb()->face()) : 703 DFace_const_iter(Base::inner_ccb()->face()); 704 } 705 706 /*! Get the twin halfedge (non-const version). */ twin()707 Halfedge_handle twin() 708 { return (DHalfedge_iter(Base::opposite())); } 709 710 /*! Get the twin halfedge (const version). */ twin()711 Halfedge_const_handle twin() const 712 { return (DHalfedge_const_iter(Base::opposite())); } 713 714 /*! Get the previous halfegde in the chain (non-const version). */ prev()715 Halfedge_handle prev() 716 { return (DHalfedge_iter(Base::prev())); } 717 718 /*! Get the previous halfegde in the chain (const version). */ prev()719 Halfedge_const_handle prev() const 720 { return (DHalfedge_const_iter(Base::prev())); } 721 722 /*! Get the next halfegde in the chain (non-const version). */ next()723 Halfedge_handle next() 724 { return (DHalfedge_iter(Base::next())); } 725 726 /*! Get the next halfegde in the chain (const version). */ next()727 Halfedge_const_handle next() const 728 { return (DHalfedge_const_iter(Base::next())); } 729 730 /*! Get the connected component of the halfedge (non-const version). */ ccb()731 Ccb_halfedge_circulator ccb() 732 { return Ccb_halfedge_circulator(DHalfedge_iter(this)); } 733 734 /*! Get the connected component of the halfedge (const version). */ ccb()735 Ccb_halfedge_const_circulator ccb() const 736 { return Ccb_halfedge_const_circulator(DHalfedge_const_iter(this)); } 737 738 private: 739 740 // Blocking access to inherited functions from the Dcel::Halfedge. 741 bool has_null_curve() const; 742 void set_curve(X_monotone_curve_2* ); 743 const DHalfedge* opposite() const; 744 DHalfedge* opposite(); 745 void set_opposite(DHalfedge* ); 746 void set_direction(Arr_halfedge_direction ); 747 void set_prev(DHalfedge* ); 748 void set_next(DHalfedge* ); 749 const DVertex* vertex() const ; 750 DVertex* vertex(); 751 void set_vertex(DVertex* ); 752 const DOuter_ccb* outer_ccb() const; 753 DOuter_ccb* outer_ccb(); 754 void set_outer_ccb(DOuter_ccb* ); 755 const DInner_ccb* inner_ccb() const; 756 DInner_ccb* inner_ccb(); 757 void set_inner_ccb(DInner_ccb* ); 758 }; 759 760 /*! 761 * \class The arrangement face class. 762 */ 763 class Face : public DFace { 764 typedef DFace Base; 765 766 public: 767 /*! Default constrcutor. */ Face()768 Face() {} 769 770 /*! Get an iterator for the outer CCBs of the face (non-const version). */ outer_ccbs_begin()771 Outer_ccb_iterator outer_ccbs_begin() 772 { return (DOuter_ccb_iter(Base::outer_ccbs_begin())); } 773 774 /*! Get an iterator for the outer CCBs the face (const version). */ outer_ccbs_begin()775 Outer_ccb_const_iterator outer_ccbs_begin() const 776 { return (DOuter_ccb_const_iter(Base::outer_ccbs_begin())); } 777 778 /*! Get a past-the-end iterator for the outer CCBs (non-const version). */ outer_ccbs_end()779 Outer_ccb_iterator outer_ccbs_end() 780 { return (DOuter_ccb_iter(Base::outer_ccbs_end())); } 781 782 /*! Get a past-the-end iterator for the outer CCBs (const version). */ outer_ccbs_end()783 Outer_ccb_const_iterator outer_ccbs_end() const 784 { return (DOuter_ccb_const_iter(Base::outer_ccbs_end())); } 785 786 /*! Get an iterator for the inner CCBs of the face (non-const version). */ inner_ccbs_begin()787 Inner_ccb_iterator inner_ccbs_begin() 788 { return (DInner_ccb_iter(Base::inner_ccbs_begin())); } 789 790 /*! Get an iterator for the inner CCBs the face (const version). */ inner_ccbs_begin()791 Inner_ccb_const_iterator inner_ccbs_begin() const 792 { return (DInner_ccb_const_iter(Base::inner_ccbs_begin())); } 793 794 /*! Get a past-the-end iterator for the inner CCBs (non-const version). */ inner_ccbs_end()795 Inner_ccb_iterator inner_ccbs_end() 796 { return (DInner_ccb_iter(Base::inner_ccbs_end())); } 797 798 /*! Get a past-the-end iterator for the inner CCBs (const version). */ inner_ccbs_end()799 Inner_ccb_const_iterator inner_ccbs_end() const 800 { return (DInner_ccb_const_iter(Base::inner_ccbs_end())); } 801 802 /*! Get an iterator for the isolated_vertices inside the face 803 * (non-const version). 804 */ isolated_vertices_begin()805 Isolated_vertex_iterator isolated_vertices_begin() 806 { return (DIso_vertex_iter(Base::isolated_vertices_begin())); } 807 808 /*! Get an iterator for the isolated_vertices inside the face 809 * (const version). 810 */ isolated_vertices_begin()811 Isolated_vertex_const_iterator isolated_vertices_begin() const 812 { return (DIso_vertex_const_iter(Base::isolated_vertices_begin())); } 813 814 /*! Get a past-the-end iterator for the isolated_vertices 815 * (non-const version). 816 */ isolated_vertices_end()817 Isolated_vertex_iterator isolated_vertices_end() 818 { return (DIso_vertex_iter(Base::isolated_vertices_end())); } 819 820 /*! Get a past-the-end iterator for the isolated_vertices 821 * (const version). 822 */ isolated_vertices_end()823 Isolated_vertex_const_iterator isolated_vertices_end() const 824 { return (DIso_vertex_const_iter(Base::isolated_vertices_end())); } 825 826 /// \name These functions are kept for Arrangement_2 compatibility: 827 //@{ 828 829 /*! 830 * Check whether the face has an outer CCB. 831 */ has_outer_ccb()832 bool has_outer_ccb() const 833 { return (Base::number_of_outer_ccbs() > 0); } 834 835 /*! 836 * Get a circulator for the outer boundary (non-const version). 837 * \pre The face has a single outer CCB. 838 */ outer_ccb()839 Ccb_halfedge_circulator outer_ccb() 840 { 841 CGAL_precondition(Base::number_of_outer_ccbs() == 1); 842 843 DOuter_ccb_iter iter = Base::outer_ccbs_begin(); 844 DHalfedge* he = *iter; 845 return Ccb_halfedge_circulator(DHalfedge_iter(he)); 846 } 847 848 /*! 849 * Get a circulator for the outer boundary (const version). 850 * \pre The face has a single outer CCB. 851 */ outer_ccb()852 Ccb_halfedge_const_circulator outer_ccb() const 853 { 854 CGAL_precondition(Base::number_of_outer_ccbs() == 1); 855 856 DOuter_ccb_const_iter iter = Base::outer_ccbs_begin(); 857 const DHalfedge* he = *iter; 858 return Ccb_halfedge_const_circulator(DHalfedge_const_iter(he)); 859 } 860 861 /*! Get the number of holes (inner CCBs) inside the face. */ number_of_holes()862 Size number_of_holes() const 863 { return (Base::number_of_inner_ccbs()); } 864 865 /*! Get an iterator for the holes inside the face (non-const version). */ holes_begin()866 Inner_ccb_iterator holes_begin() 867 { return (this->inner_ccbs_begin()); } 868 869 /*! Get an iterator for the holes inside the face (const version). */ holes_begin()870 Inner_ccb_const_iterator holes_begin() const 871 { return (this->inner_ccbs_begin()); } 872 873 /*! Get a past-the-end iterator for the holes (non-const version). */ holes_end()874 Inner_ccb_iterator holes_end() 875 { return (this->inner_ccbs_end()); } 876 877 /*! Get a past-the-end iterator for the holes (const version). */ holes_end()878 Inner_ccb_const_iterator holes_end() const 879 { return (this->inner_ccbs_end()); } 880 //@} 881 882 private: 883 // Blocking access to inherited functions from the Dcel::Face. 884 void set_unbounded(bool); 885 void set_fictitious(bool); 886 void add_outer_ccb(DOuter_ccb*, Halfedge*); 887 void erase_outer_ccb(DOuter_ccb*); 888 void add_inner_ccb(DInner_ccb*, Halfedge*); 889 void erase_inner_ccb(DInner_ccb*); 890 void add_isolated_vertex(DIso_vertex*, DVertex*); 891 void erase_isolated_vertex(DIso_vertex*); 892 }; 893 894 protected: 895 typedef CGAL_ALLOCATOR(Point_2) Points_alloc; 896 typedef CGAL_ALLOCATOR(X_monotone_curve_2) Curves_alloc; 897 898 typedef Arr_observer<Self> Observer; 899 typedef std::list<Observer*> Observers_container; 900 typedef typename Observers_container::iterator Observers_iterator; 901 902 typedef typename Observers_container::reverse_iterator 903 Observers_rev_iterator; 904 905 // Data members: 906 Topology_traits m_topol_traits; // the topology traits. 907 Points_alloc m_points_alloc; // allocator for the points. 908 Curves_alloc m_curves_alloc; // allocator for the curves. 909 Observers_container m_observers; // pointers to existing observers. 910 const Traits_adaptor_2* m_geom_traits; // the geometry-traits adaptor. 911 bool m_own_traits; // inidicates whether the geometry 912 // traits should be freed up. 913 914 bool m_sweep_mode = false; 915 // sweep mode efficiently 916 // merges inner CCB but 917 // keeps invalid inner CCB 918 // and memory overhead that 919 // should be cleaned 920 // afterwards 921 922 public: 923 /// \name Constructors. 924 //@{ 925 926 /*! Default constructor. */ 927 Arrangement_on_surface_2(); 928 929 /*! Copy constructor. */ 930 Arrangement_on_surface_2(const Self & arr); 931 932 /*! Constructor given a traits object. */ 933 Arrangement_on_surface_2(const Geometry_traits_2* geom_traits); 934 //@} 935 936 /// \name Assignment functions. 937 //@{ 938 939 /*! Assignment operator. */ 940 Self& operator=(const Self& arr); 941 942 /*! Assign an arrangement. */ 943 void assign(const Self& arr); 944 //@} 945 946 /// \name Destruction functions. 947 //@{ 948 949 /*! Destructor. */ 950 virtual ~Arrangement_on_surface_2(); 951 952 /*! Change mode. */ set_sweep_mode(bool mode)953 void set_sweep_mode (bool mode) { m_sweep_mode = mode; } 954 955 /*! Clear the arrangement. */ 956 virtual void clear(); 957 //@} 958 959 /// \name Access the traits-class objects. 960 //@{ 961 962 /*! Access the geometry-traits object (const version). */ traits_adaptor()963 inline const Traits_adaptor_2* traits_adaptor() const 964 { return (m_geom_traits); } 965 966 /*! Access the geometry-traits object (const version). */ geometry_traits()967 inline const Geometry_traits_2* geometry_traits() const 968 { return (m_geom_traits); } 969 970 /*! Access the topology-traits object (non-const version). */ topology_traits()971 inline Topology_traits* topology_traits() 972 { return (&m_topol_traits); } 973 974 /*! Access the topology-traits object (const version). */ topology_traits()975 inline const Topology_traits* topology_traits() const 976 { return (&m_topol_traits); } 977 //@} 978 979 /// \name Access the arrangement dimensions. 980 //@{ 981 982 /*! Check whether the arrangement is empty. */ is_empty()983 bool is_empty() const 984 { return (m_topol_traits.is_empty_dcel()); } 985 986 /*! 987 * Check whether the arrangement is valid. In particular, check the 988 * validity of each vertex, halfedge and face, their incidence relations 989 * and the geometric properties of the arrangement. 990 */ 991 bool is_valid() const; 992 993 /*! Get the number of arrangement vertices. */ number_of_vertices()994 Size number_of_vertices() const 995 { return (m_topol_traits.number_of_concrete_vertices()); } 996 997 /*! Get the number of isolated arrangement vertices. */ number_of_isolated_vertices()998 Size number_of_isolated_vertices() const 999 { return (_dcel().size_of_isolated_vertices()); } 1000 1001 /*! Get the number of arrangement halfedges (the result is always even). */ number_of_halfedges()1002 Size number_of_halfedges() const 1003 { return (m_topol_traits.number_of_valid_halfedges()); } 1004 1005 /*! Get the number of arrangement edges. */ number_of_edges()1006 Size number_of_edges() const 1007 { return (m_topol_traits.number_of_valid_halfedges() / 2); } 1008 1009 /*! Get the number of arrangement faces. */ number_of_faces()1010 Size number_of_faces() const 1011 { return (m_topol_traits.number_of_valid_faces()); } 1012 1013 /*! Get the number of unbounded faces in the arrangement. */ number_of_unbounded_faces()1014 Size number_of_unbounded_faces() const 1015 { 1016 Unbounded_face_const_iterator iter = unbounded_faces_begin(); 1017 Unbounded_face_const_iterator end = unbounded_faces_end(); 1018 Size n_unb = 0; 1019 1020 while (iter != end) { 1021 ++n_unb; 1022 ++iter; 1023 } 1024 1025 return (n_unb); 1026 } 1027 //@} 1028 1029 /// \name Traversal functions for the arrangement vertices. 1030 //@{ 1031 1032 /*! Get an iterator for the first vertex in the arrangement. */ vertices_begin()1033 Vertex_iterator vertices_begin() 1034 { 1035 return (Vertex_iterator(_dcel().vertices_begin(), _dcel().vertices_end(), 1036 _Is_concrete_vertex(&m_topol_traits))); 1037 } 1038 1039 /*! Get a past-the-end iterator for the arrangement vertices. */ vertices_end()1040 Vertex_iterator vertices_end() 1041 { 1042 return (Vertex_iterator(_dcel().vertices_end(), _dcel().vertices_end(), 1043 _Is_concrete_vertex(&m_topol_traits))); 1044 } 1045 1046 /*! 1047 returns a range over handles of the arrangement vertices . 1048 */ 1049 Iterator_range<Prevent_deref<Vertex_iterator> > vertex_handles()1050 vertex_handles() 1051 { 1052 return make_prevent_deref_range(vertices_begin(), vertices_end()); 1053 } 1054 1055 /*! Get a const iterator for the first vertex in the arrangement. */ vertices_begin()1056 Vertex_const_iterator vertices_begin() const 1057 { 1058 return (Vertex_const_iterator(_dcel().vertices_begin(), 1059 _dcel().vertices_end(), 1060 _Is_concrete_vertex(&m_topol_traits))); 1061 } 1062 1063 /*! Get a past-the-end const iterator for the arrangement vertices. */ vertices_end()1064 Vertex_const_iterator vertices_end() const 1065 { 1066 return (Vertex_const_iterator(_dcel().vertices_end(), 1067 _dcel().vertices_end(), 1068 _Is_concrete_vertex(&m_topol_traits))); 1069 } 1070 1071 /*! 1072 returns a const range (model of `ConstRange`) over handles of the arrangement vertices . 1073 */ 1074 Iterator_range<Prevent_deref<Vertex_iterator> > vertex_handles()1075 vertex_handles() const 1076 { 1077 return make_prevent_deref_range(vertices_begin(), vertices_end()); 1078 } 1079 1080 //@} 1081 1082 /// \name Traversal functions for the arrangement halfedges. 1083 //@{ 1084 1085 /*! Get an iterator for the first halfedge in the arrangement. */ halfedges_begin()1086 Halfedge_iterator halfedges_begin() 1087 { 1088 return (Halfedge_iterator(_dcel().halfedges_begin(), 1089 _dcel().halfedges_end(), 1090 _Is_valid_halfedge(&m_topol_traits))); 1091 } 1092 1093 /*! Get a past-the-end iterator for the arrangement halfedges. */ halfedges_end()1094 Halfedge_iterator halfedges_end() 1095 { 1096 return (Halfedge_iterator(_dcel().halfedges_end(), 1097 _dcel().halfedges_end(), 1098 _Is_valid_halfedge(&m_topol_traits))); 1099 } 1100 1101 /*! 1102 returns a range over handles of the arrangement halfedges . 1103 */ 1104 Iterator_range<Prevent_deref<Halfedge_iterator> > halfedge_handles()1105 halfedge_handles() 1106 { 1107 return make_prevent_deref_range(halfedges_begin(), halfedges_end()); 1108 } 1109 1110 /*! Get a const iterator for the first halfedge in the arrangement. */ halfedges_begin()1111 Halfedge_const_iterator halfedges_begin() const 1112 { 1113 return (Halfedge_const_iterator(_dcel().halfedges_begin(), 1114 _dcel().halfedges_end(), 1115 _Is_valid_halfedge(&m_topol_traits))); 1116 } 1117 1118 /*! Get a past-the-end const iterator for the arrangement halfedges. */ halfedges_end()1119 Halfedge_const_iterator halfedges_end() const 1120 { 1121 return (Halfedge_const_iterator(_dcel().halfedges_end(), 1122 _dcel().halfedges_end(), 1123 _Is_valid_halfedge(&m_topol_traits))); 1124 } 1125 /*! 1126 returns a const range (model of `ConstRange`) over handles of the arrangement halfedges . 1127 */ 1128 Iterator_range<Prevent_deref<Halfedge_iterator> > halfedge_handles()1129 halfedge_handles() const 1130 { 1131 return make_prevent_deref_range(halfedges_begin(), halfedges_end()); 1132 } 1133 //@} 1134 1135 /// \name Traversal functions for the arrangement edges. 1136 //@{ 1137 1138 /*! Get an iterator for the first edge in the arrangement. */ edges_begin()1139 Edge_iterator edges_begin() 1140 { 1141 return (Edge_iterator(_dcel().edges_begin(), _dcel().edges_end(), 1142 _Is_valid_halfedge(&m_topol_traits))); 1143 } 1144 1145 /*! Get a past-the-end iterator for the arrangement edges. */ edges_end()1146 Edge_iterator edges_end() 1147 { 1148 return (Edge_iterator(_dcel().edges_end(), _dcel().edges_end(), 1149 _Is_valid_halfedge(&m_topol_traits))); 1150 } 1151 1152 /*! 1153 returns a range over handles of the arrangement edges . 1154 */ 1155 Iterator_range<Prevent_deref<Edge_iterator> > edge_handles()1156 edge_handles() 1157 { 1158 return make_prevent_deref_range(edges_begin(), edges_end()); 1159 } 1160 1161 /*! Get a const iterator for the first edge in the arrangement. */ edges_begin()1162 Edge_const_iterator edges_begin() const 1163 { 1164 return (Edge_const_iterator(_dcel().edges_begin(), _dcel().edges_end(), 1165 _Is_valid_halfedge(&m_topol_traits))); 1166 } 1167 1168 /*! Get a past-the-end const iterator for the arrangement edges. */ edges_end()1169 Edge_const_iterator edges_end() const 1170 { 1171 return (Edge_const_iterator(_dcel().edges_end(), _dcel().edges_end(), 1172 _Is_valid_halfedge(&m_topol_traits))); 1173 } 1174 1175 /*! 1176 returns a const range (model of `ConstRange`) over handles of the arrangement edges . 1177 */ 1178 Iterator_range<Prevent_deref<Edge_iterator> > edge_handles()1179 edge_handles() const 1180 { 1181 return make_prevent_deref_range(edges_begin(), edges_end()); 1182 } 1183 //@} 1184 1185 /// \name Traversal functions for the arrangement faces. 1186 //@{ 1187 1188 /*! Get an iterator for the first face in the arrangement. */ faces_begin()1189 Face_iterator faces_begin() 1190 { 1191 return (Face_iterator(_dcel().faces_begin(), _dcel().faces_end(), 1192 _Is_valid_face(&m_topol_traits))); 1193 } 1194 1195 /*! Get a past-the-end iterator for the arrangement faces. */ faces_end()1196 Face_iterator faces_end() 1197 { 1198 return (Face_iterator(_dcel().faces_end(), _dcel().faces_end(), 1199 _Is_valid_face(&m_topol_traits))); 1200 } 1201 1202 /*! 1203 returns a range over handles of the arrangement faces . 1204 */ 1205 Iterator_range<Prevent_deref<Face_iterator> > face_handles()1206 face_handles() 1207 { 1208 return make_prevent_deref_range(faces_begin(), faces_end()); 1209 } 1210 /*! Get a const iterator for the first face in the arrangement. */ faces_begin()1211 Face_const_iterator faces_begin() const 1212 { 1213 return (Face_const_iterator(_dcel().faces_begin(), _dcel().faces_end(), 1214 _Is_valid_face(&m_topol_traits))); 1215 } 1216 1217 /*! Get a past-the-end const iterator for the arrangement faces. */ faces_end()1218 Face_const_iterator faces_end() const 1219 { 1220 return (Face_const_iterator(_dcel().faces_end(), _dcel().faces_end(), 1221 _Is_valid_face(&m_topol_traits))); 1222 } 1223 1224 /*! 1225 returns a const range (model of `ConstRange`) over handles of the arrangement faces . 1226 */ 1227 Iterator_range<Prevent_deref<Face_iterator> > face_handles()1228 face_handles() const 1229 { 1230 return make_prevent_deref_range(faces_begin(), faces_end()); 1231 } 1232 //! reference_face (const version). 1233 /*! The function returns a reference face of the arrangement. 1234 * All reference faces of arrangements of the same type have a common 1235 * point. 1236 * \return A const handle to the reference face. 1237 */ reference_face()1238 Face_const_handle reference_face() const 1239 { 1240 return _const_handle_for(this->topology_traits()->reference_face()); 1241 } 1242 1243 //! reference_face (non-const version). 1244 /*! The function returns a reference face of the arrangement. 1245 All reference faces of arrangements of the same type have a common 1246 point. 1247 \return A handle to the reference face. 1248 */ reference_face()1249 Face_handle reference_face() 1250 { return _handle_for(this->topology_traits()->reference_face()); } 1251 1252 //@} 1253 1254 /// \name Traversal functions for the unbounded faces of the arrangement. 1255 //@{ 1256 1257 /*! Get an iterator for the first unbounded face in the arrangement. */ unbounded_faces_begin()1258 Unbounded_face_iterator unbounded_faces_begin() 1259 { 1260 return Unbounded_face_iterator(_dcel().faces_begin(), _dcel().faces_end(), 1261 _Is_unbounded_face(&m_topol_traits)); 1262 } 1263 1264 /*! Get a past-the-end iterator for the unbounded arrangement faces. */ unbounded_faces_end()1265 Unbounded_face_iterator unbounded_faces_end() 1266 { 1267 return Unbounded_face_iterator(_dcel().faces_end(), _dcel().faces_end(), 1268 _Is_unbounded_face(&m_topol_traits)); 1269 } 1270 1271 /*! Get a const iterator for the first unbounded face in the arrangement. */ unbounded_faces_begin()1272 Unbounded_face_const_iterator unbounded_faces_begin() const 1273 { 1274 return Unbounded_face_const_iterator(_dcel().faces_begin(), 1275 _dcel().faces_end(), 1276 _Is_unbounded_face(&m_topol_traits)); 1277 } 1278 1279 /*! Get a past-the-end const iterator for the unbounded arrangement faces. */ unbounded_faces_end()1280 Unbounded_face_const_iterator unbounded_faces_end() const 1281 { 1282 return Unbounded_face_const_iterator(_dcel().faces_end(), 1283 _dcel().faces_end(), 1284 _Is_unbounded_face(&m_topol_traits)); 1285 } 1286 1287 /*! Get the fictitious face (non-const version). */ fictitious_face()1288 Face_handle fictitious_face() 1289 { 1290 // The fictitious contains all other faces in a single hole inside it. 1291 return 1292 Face_handle(const_cast<DFace*>(this->topology_traits()->initial_face())); 1293 } 1294 1295 /*! 1296 * Get the unbounded face (const version). 1297 * The fictitious contains all other faces in a single hole inside it. 1298 */ fictitious_face()1299 Face_const_handle fictitious_face() const 1300 { return DFace_const_iter(this->topology_traits()->initial_face()); } 1301 //@} 1302 1303 /// \name Casting away constness for handle types. 1304 //@{ non_const_handle(Vertex_const_handle vh)1305 Vertex_handle non_const_handle(Vertex_const_handle vh) 1306 { 1307 DVertex* p_v = (DVertex*)&(*vh); 1308 return (Vertex_handle(p_v)); 1309 } 1310 non_const_handle(Halfedge_const_handle hh)1311 Halfedge_handle non_const_handle(Halfedge_const_handle hh) 1312 { 1313 DHalfedge* p_he = (DHalfedge*)&(*hh); 1314 return (Halfedge_handle(p_he)); 1315 } 1316 non_const_handle(Face_const_handle fh)1317 Face_handle non_const_handle(Face_const_handle fh) 1318 { 1319 DFace* p_f = (DFace*) &(*fh); 1320 return (Face_handle(p_f)); 1321 } 1322 //@} 1323 1324 /// \name Specilaized insertion functions. 1325 //@{ 1326 1327 /*! 1328 * Insert a point that forms an isolated vertex in the interior of a given 1329 * face. 1330 * \param p The given point. 1331 * \param f The face into which we insert the new isolated vertex. 1332 * \return A handle for the isolated vertex that has been created. 1333 */ 1334 Vertex_handle insert_in_face_interior(const Point_2& p, Face_handle f); 1335 1336 /*! 1337 * Insert an x-monotone curve into the arrangement as a new hole (inner 1338 * component) inside the given face. 1339 * \param cv The given x-monotone curve. 1340 * \param f The face into which we insert the new hole. 1341 * \return A handle for one of the halfedges corresponding to the inserted 1342 * curve, directed (lexicographically) from left to right. 1343 */ 1344 Halfedge_handle insert_in_face_interior(const X_monotone_curve_2& cv, 1345 Face_handle f); 1346 1347 /*! 1348 * Insert an x-monotone curve into the arrangement, such that its left 1349 * endpoint corresponds to a given arrangement vertex. 1350 * \param cv The given x-monotone curve. 1351 * \param v The given vertex. 1352 * \param f The face that contains v (in case it has no incident edges). 1353 * \pre The left endpoint of cv is incident to the vertex v. 1354 * \return A handle for one of the halfedges corresponding to the inserted 1355 * curve, whose target is the new vertex. 1356 */ 1357 Halfedge_handle insert_from_left_vertex(const X_monotone_curve_2& cv, 1358 Vertex_handle v, 1359 Face_handle f = Face_handle()); 1360 1361 /*! 1362 * Insert an x-monotone curve into the arrangement, such that its left 1363 * endpoints corresponds to a given arrangement vertex, given the exact 1364 * place for the curve in the circular list around this vertex. 1365 * \param cv The given x-monotone curve. 1366 * \param prev The reference halfedge. We should represent cv as a pair 1367 * of edges, one of them should become prev's successor. 1368 * \pre The target vertex of prev is cv's left endpoint. 1369 * \return A handle for one of the halfedges corresponding to the inserted 1370 * curve, whose target is the new vertex that was created. 1371 */ 1372 Halfedge_handle insert_from_left_vertex(const X_monotone_curve_2& cv, 1373 Halfedge_handle prev); 1374 1375 /*! 1376 * Insert an x-monotone curve into the arrangement, such that its right 1377 * endpoint corresponds to a given arrangement vertex. 1378 * \param cv The given x-monotone curve. 1379 * \param v The given vertex. 1380 * \param f The face that contains v (in case it has no incident edges). 1381 * \pre The right endpoint of cv is incident to the vertex v. 1382 * \return A handle for one of the halfedges corresponding to the inserted 1383 * curve, whose target is the new vertex. 1384 */ 1385 Halfedge_handle insert_from_right_vertex(const X_monotone_curve_2& cv, 1386 Vertex_handle v, 1387 Face_handle f = Face_handle()); 1388 1389 /*! 1390 * Insert an x-monotone curve into the arrangement, such that its right 1391 * endpoints corresponds to a given arrangement vertex, given the exact 1392 * place for the curve in the circular list around this vertex. 1393 1394 * \param cv The given x-monotone curve. 1395 * \param prev The reference halfedge. We should represent cv as a pair 1396 * of edges, one of them should become prev's successor. 1397 * \pre The target vertex of prev is cv's right endpoint. 1398 * \return A handle for one of the halfedges corresponding to the inserted 1399 * curve, whose target is the new vertex that was created. 1400 */ 1401 Halfedge_handle insert_from_right_vertex(const X_monotone_curve_2& cv, 1402 Halfedge_handle prev); 1403 1404 /*! 1405 * Insert an x-monotone curve into the arrangement, such that both its 1406 * endpoints correspond to given arrangement vertices. 1407 * \param cv The given x-monotone curve. 1408 * \param v1 The first vertex. 1409 * \param v2 The second vertex. 1410 * \param f The face that contains v1 and v2 1411 * (in case both have no incident edges). 1412 * \pre v1 and v2 corresponds to cv's endpoints. 1413 * \return A handle for one of the halfedges corresponding to the inserted 1414 * curve directed from v1 to v2. 1415 */ 1416 Halfedge_handle insert_at_vertices(const X_monotone_curve_2& cv, 1417 Vertex_handle v1, 1418 Vertex_handle v2, 1419 Face_handle f = Face_handle()); 1420 1421 /*! 1422 * Insert an x-monotone curve into the arrangement, such that both its 1423 * endpoints correspond to given arrangement vertices, given the exact 1424 * place for the curve in one of the circular lists around a vertex. 1425 * \param cv The given x-monotone curve. 1426 * \param prev1 The reference halfedge for the first vertex. 1427 * \param v2 The second vertex. 1428 * \pre The target vertex of prev1 and v2 corresponds to cv's endpoints. 1429 * \return A handle for one of the halfedges corresponding to the inserted 1430 * curve directed from prev1 to v2. 1431 */ 1432 Halfedge_handle insert_at_vertices(const X_monotone_curve_2& cv, 1433 Halfedge_handle prev1, 1434 Vertex_handle v2); 1435 1436 /*! 1437 * Insert an x-monotone curve into the arrangement, such that both its 1438 * endpoints correspond to given arrangement vertices, given the exact 1439 * place for the curve in both circular lists around these two vertices. 1440 * \param cv the given curve. 1441 * \param prev1 The reference halfedge for the first vertex. 1442 * \param prev2 The reference halfedge for the second vertex. 1443 * \pre The target vertices of prev1 and prev2 are cv's endpoints. 1444 * \return A handle for one of the halfedges corresponding to the inserted 1445 * curve directed from prev1's target to prev2's target. 1446 */ 1447 Halfedge_handle insert_at_vertices(const X_monotone_curve_2 & cv, 1448 Halfedge_handle prev1, 1449 Halfedge_handle prev2); 1450 1451 //@} 1452 1453 /// \name Vertex manipulation functions. 1454 //@{ 1455 1456 /*! 1457 * Replace the point associated with the given vertex. 1458 * \param v The vertex to modify. 1459 * \param p The point that should be associated with the edge. 1460 * \pre p is geometrically equivalent to the current point 1461 * associated with v. 1462 * \return A handle for a the modified vertex (same as v). 1463 */ 1464 Vertex_handle modify_vertex(Vertex_handle v, const Point_2& p); 1465 1466 /*! 1467 * Remove an isolated vertex from the interior of a given face. 1468 * \param v The vertex to remove. 1469 * \pre v is an isolated vertex (it has no incident halfedges). 1470 * \return A handle for the face containing v. 1471 */ 1472 Face_handle remove_isolated_vertex(Vertex_handle v); 1473 1474 ///@} 1475 1476 /// \name Halfedge manipulation functions. 1477 //@{ 1478 1479 /*! 1480 * Replace the x-monotone curve associated with the given edge. 1481 * \param e The edge to modify. 1482 * \param cv The curve that should be associated with the edge. 1483 * \pre cv is geometrically equivalent to the current curve 1484 * associated with e. 1485 * \return A handle for a the modified halfedge (same as e). 1486 */ 1487 Halfedge_handle modify_edge(Halfedge_handle e, const X_monotone_curve_2& cv); 1488 1489 /*! 1490 * Split a given edge into two, and associate the given x-monotone 1491 * curves with the split edges. 1492 * \param e The edge to split (one of the pair of twin halfegdes). 1493 * \param cv1 The curve that should be associated with the first split edge. 1494 * \param cv2 The curve that should be associated with the second split edge. 1495 1496 * \pre cv1's source and cv2's target equal the endpoints of the curve 1497 * currently assoicated with e (respectively), and cv1's target equals 1498 * cv2's target, and this is the split point (ot vice versa). 1499 * \return A handle for the halfedge whose source is the source of the 1500 * original halfedge e, and whose target is the split point. 1501 */ 1502 Halfedge_handle split_edge(Halfedge_handle e, 1503 const X_monotone_curve_2& cv1, 1504 const X_monotone_curve_2& cv2); 1505 1506 /*! 1507 * Merge two edges to form a single edge, and associate the given x-monotone 1508 * curve with the merged edge. 1509 * \param e1 The first edge to merge (one of the pair of twin halfegdes). 1510 * \param e2 The second edge to merge (one of the pair of twin halfegdes). 1511 * \param cv The curve that should be associated with merged edge. 1512 * \return A handle for the merged halfedge. 1513 */ 1514 Halfedge_handle merge_edge(Halfedge_handle e1, Halfedge_handle e2, 1515 const X_monotone_curve_2& cv); 1516 1517 /*! 1518 * Remove an edge from the arrangement. 1519 * \param e The edge to remove (one of the pair of twin halfegdes). 1520 * \param remove_source Should the source vertex of e be removed if it 1521 * becomes isolated (true by default). 1522 * \param remove_target Should the target vertex of e be removed if it 1523 * becomes isolated (true by default). 1524 * \return A handle for the remaining face. 1525 */ 1526 Face_handle remove_edge(Halfedge_handle e, 1527 bool remove_source = true, 1528 bool remove_target = true); 1529 1530 //@} 1531 1532 /*! 1533 * Cleans the inner CCB if sweep mode was used, by removing all 1534 * non-valid inner CCBs 1535 */ clean_inner_ccbs_after_sweep()1536 void clean_inner_ccbs_after_sweep() 1537 { 1538 for (DHalfedge_iter he = _dcel().halfedges_begin(); 1539 he != _dcel().halfedges_end(); ++ he) 1540 { 1541 if (!he->is_on_inner_ccb()) 1542 continue; 1543 1544 DInner_ccb* ic1 = he->inner_ccb_no_redirect(); 1545 if (ic1->is_valid()) 1546 continue; 1547 1548 // Calling Halfedge::inner_ccb() reduces the path and makes the 1549 // halfedge point to a correct CCB 1550 DInner_ccb* ic2 = he->inner_ccb(); 1551 CGAL_USE(ic2); 1552 CGAL_assertion (ic2->halfedge()->is_on_inner_ccb() 1553 && ic2->halfedge()->inner_ccb_no_redirect() == ic2); 1554 } 1555 1556 typename Dcel::Inner_ccb_iterator it = _dcel().inner_ccbs_begin(); 1557 while (it != _dcel().inner_ccbs_end()) 1558 { 1559 typename Dcel::Inner_ccb_iterator current = it ++; 1560 if (!current->is_valid()) 1561 _dcel().delete_inner_ccb(&*current); 1562 } 1563 } 1564 1565 protected: 1566 /// \name Determining the boundary-side conditions. 1567 //@{ 1568 1569 /*! Determines whether a boundary-side categoty indicates an open side. 1570 */ is_open(Arr_boundary_side_tag)1571 inline bool is_open(Arr_boundary_side_tag) const { return false; } is_open(Arr_open_side_tag)1572 inline bool is_open(Arr_open_side_tag) const { return true; } 1573 1574 /*! Determines whether the given x and y parameter spaces are open. 1575 * These parameter spaces are typically associated with a particular curve 1576 * end. 1577 * \param ps_x The parameter space in x. 1578 * \param ps_y The parameter space in y. 1579 */ is_open(Arr_parameter_space ps_x,Arr_parameter_space ps_y)1580 inline bool is_open(Arr_parameter_space ps_x, Arr_parameter_space ps_y) const 1581 { 1582 return 1583 (((ps_x == ARR_LEFT_BOUNDARY) && is_open(Left_side_category())) || 1584 ((ps_x == ARR_RIGHT_BOUNDARY) && is_open(Right_side_category())) || 1585 ((ps_y == ARR_BOTTOM_BOUNDARY) && is_open(Bottom_side_category())) || 1586 ((ps_y == ARR_TOP_BOUNDARY) && is_open(Top_side_category()))); 1587 1588 } 1589 1590 /*! Determines whether a boundary-side categoty indicates a constracted side. 1591 */ is_contracted(Arr_boundary_side_tag)1592 inline bool is_contracted(Arr_boundary_side_tag) const { return false; } is_contracted(Arr_contracted_side_tag)1593 inline bool is_contracted(Arr_contracted_side_tag) const { return true; } 1594 1595 /*! Determines whether a boundary-side categoty indicates a constracted side. 1596 */ is_identified(Arr_boundary_side_tag)1597 inline bool is_identified(Arr_boundary_side_tag) const { return false; } is_identified(Arr_identified_side_tag)1598 inline bool is_identified(Arr_identified_side_tag) const { return true; } 1599 //@} 1600 1601 /// \name Allocating and de-allocating points and curves. 1602 //@{ 1603 1604 /*! Allocate a new point. */ _new_point(const Point_2 & pt)1605 Point_2*_new_point(const Point_2& pt) 1606 { 1607 Point_2* p_pt = m_points_alloc.allocate(1); 1608 std::allocator_traits<Points_alloc>::construct(m_points_alloc, p_pt, pt); 1609 return (p_pt); 1610 } 1611 1612 /*! De-allocate a point. */ _delete_point(Point_2 & pt)1613 void _delete_point(Point_2& pt) 1614 { 1615 Point_2* p_pt = &pt; 1616 std::allocator_traits<Points_alloc>::destroy(m_points_alloc, p_pt); 1617 m_points_alloc.deallocate(p_pt, 1); 1618 } 1619 1620 /*! Allocate a new curve. */ _new_curve(const X_monotone_curve_2 & cv)1621 X_monotone_curve_2* _new_curve(const X_monotone_curve_2& cv) 1622 { 1623 X_monotone_curve_2* p_cv = m_curves_alloc.allocate(1); 1624 std::allocator_traits<Curves_alloc>::construct(m_curves_alloc, p_cv, cv); 1625 return (p_cv); 1626 } 1627 1628 /*! De-allocate a curve. */ _delete_curve(X_monotone_curve_2 & cv)1629 void _delete_curve(X_monotone_curve_2& cv) 1630 { 1631 X_monotone_curve_2* p_cv = &cv; 1632 std::allocator_traits<Curves_alloc>::destroy(m_curves_alloc, p_cv); 1633 m_curves_alloc.deallocate(p_cv, 1); 1634 } 1635 //@} 1636 1637 /// \name Converting handles to pointers (for the arrangement accessor). 1638 //@{ 1639 /*! Access the DCEL (non-const version). */ _dcel()1640 inline Dcel& _dcel() { return (m_topol_traits.dcel()); } 1641 /*! Access the DCEL (const version). */ _dcel()1642 inline const Dcel& _dcel() const 1643 { return (m_topol_traits.dcel()); } 1644 1645 /*! Convert a vertex handle to a pointer to a DCEL vertex. */ _vertex(Vertex_handle vh)1646 inline DVertex* _vertex(Vertex_handle vh) const 1647 { return (&(*vh)); } 1648 1649 /*! Convert a constant vertex handle to a pointer to a DCEL vertex. */ _vertex(Vertex_const_handle vh)1650 inline const DVertex* _vertex(Vertex_const_handle vh) const 1651 { return (&(*vh)); } 1652 1653 /*! Convert a halfedge handle to a pointer to a DCEL halfedge. */ _halfedge(Halfedge_handle hh)1654 inline DHalfedge* _halfedge(Halfedge_handle hh) const 1655 { return (&(*hh)); } 1656 1657 /*! Convert a constant halfedge handle to a pointer to a DCEL halfedge. */ _halfedge(Halfedge_const_handle hh)1658 inline const DHalfedge* _halfedge(Halfedge_const_handle hh) const 1659 { return (&(*hh)); } 1660 1661 /*! Convert a face handle to a pointer to a DCEL face. */ _face(Face_handle fh)1662 inline DFace* _face(Face_handle fh) const 1663 { return (&(*fh)); } 1664 1665 /*! Convert a constant face handle to a pointer to a DCEL face. */ _face(Face_const_handle fh)1666 inline const DFace* _face(Face_const_handle fh) const 1667 { return (&(*fh)); } 1668 //@} 1669 1670 /// \name Converting pointers to handles (for the arrangement accessor). 1671 //@{ 1672 1673 /*! Convert a pointer to a DCEL vertex to a vertex handle. */ _handle_for(DVertex * v)1674 Vertex_handle _handle_for(DVertex* v) 1675 { return (Vertex_handle(v)); } 1676 1677 /*! Convert a pointer to a DCEL vertex to a constant vertex handle. */ _const_handle_for(const DVertex * v)1678 Vertex_const_handle _const_handle_for(const DVertex* v) const 1679 { return (Vertex_const_handle(v)); } 1680 1681 /*! Convert a pointer to a DCEL halfedge to a halfedge handle. */ _handle_for(DHalfedge * he)1682 Halfedge_handle _handle_for(DHalfedge* he) 1683 { return (Halfedge_handle(he)); } 1684 1685 1686 /*! Convert a pointer to a DCEL halfedge to a constant halfedge handle. */ _const_handle_for(const DHalfedge * he)1687 Halfedge_const_handle _const_handle_for(const DHalfedge* he) const 1688 { return (Halfedge_const_handle(he)); } 1689 1690 /*! Convert a pointer to a DCEL face to a face handle. */ _handle_for(DFace * f)1691 Face_handle _handle_for(DFace* f) 1692 { return (Face_handle(f)); } 1693 1694 /*! Convert a pointer to a DCEL face to a constant face handle. */ _const_handle_for(const DFace * f)1695 Face_const_handle _const_handle_for(const DFace* f) const 1696 { return (Face_const_handle(f)); } 1697 //@} 1698 1699 /// \name Auxiliary (protected) functions. 1700 //@{ 1701 1702 /*! Is the vertex incident to a given halfedge lexicographically smaller than 1703 * the vertex incident to another given halfedge. Recall that the incident 1704 * vertex is the target vertex. This function is used, for example, in the 1705 * search for lexicographically smallest vertex in a CCB, when an edge is 1706 * about to be removed from the DCEL. 1707 * 1708 * This is the implementation for the case where all 4 boundary sides are 1709 * oblivious. 1710 * 1711 * \param he1 the given first halfedge 1712 * \param ps_x1 the parameter space in x of the vertex incident to he1 1713 * \param ps_y1 the parameter space in y of the vertex incident to he1 1714 * \param he2 the given second halfedge 1715 * \param ps_x2 the parameter space in x of the vertex incident to he2 1716 * \param ps_y2 the parameter space in y of the vertex incident to he2 1717 * \precondition he1 is directed from right to left 1718 * \precondition he2 is directed from right to left 1719 * \precondition the vertex incident to he1 (he1->vertex()) is different 1720 * than the vertex incident to he1 (he2->vertex()), and thus their 1721 * geometric mappings (he1->vertex()->point() and 1722 * he2->vertex()->point()) are not equal. 1723 */ 1724 bool _is_smaller(const DHalfedge* he1, 1725 Arr_parameter_space ps_x1, Arr_parameter_space ps_y1, 1726 const DHalfedge* he2, 1727 Arr_parameter_space ps_x2, Arr_parameter_space ps_y2, 1728 Arr_all_sides_oblivious_tag) const; 1729 1730 /*! This is a wrapper for the case where any boundary side is not 1731 * necessarily oblivious. 1732 */ 1733 bool _is_smaller(const DHalfedge* he1, 1734 Arr_parameter_space ps_x1, Arr_parameter_space ps_y1, 1735 const DHalfedge* he2, 1736 Arr_parameter_space ps_x2, Arr_parameter_space ps_y2, 1737 Arr_not_all_sides_oblivious_tag) const; 1738 1739 /*! Is the lexicographically minimal vertex of a given x-monotone curve 1740 * lexicographically smaller than the lexicographically minimal vertex of 1741 * another given x-monotone curve. This function is used, for example, when 1742 * a new curve is to be inserted into the arrangement. In this case the 1743 * search is conducted over the curves that will comprise a new CCB. 1744 * 1745 * This is the implementation for the case where all 4 boundary sides are 1746 * oblivious. 1747 * 1748 * \param cv1 the given first x-monotone curve 1749 * \param ps_x1 the parameter space in x of the minimal point of cv1 1750 * \param ps_y1 the parameter space in y of the minimal point of cv1 1751 * \param cv2 the given second x-monotone curve 1752 * \param ps_x2 the parameter space in x of the minimal point of cv2 1753 * \param ps_y2 the parameter space in y of the minimal point of cv2 1754 * \precondition the minimal points of cv1 and cv2 are not equal. 1755 */ 1756 bool _is_smaller(const X_monotone_curve_2& cv1, const Point_2& p1, 1757 Arr_parameter_space ps_x1, Arr_parameter_space ps_y1, 1758 const X_monotone_curve_2& cv2, const Point_2& p2, 1759 Arr_parameter_space ps_x2, Arr_parameter_space ps_y2, 1760 Arr_all_sides_oblivious_tag) const; 1761 1762 /*! This is the implementation for the case where any one of the 4 boundary 1763 * sides can be of any type. 1764 */ 1765 bool _is_smaller(const X_monotone_curve_2& cv1, const Point_2& p1, 1766 Arr_parameter_space ps_x1, Arr_parameter_space ps_y1, 1767 const X_monotone_curve_2& cv2, const Point_2& p2, 1768 Arr_parameter_space ps_x2, Arr_parameter_space ps_y2, 1769 Arr_not_all_sides_oblivious_tag) const; 1770 1771 /*! Given two x-monotone curves that share their minimal end point. 1772 * The function return true if the y-coordinate of the first curve curve 1773 * near its minimal end smaller than the y-coordinate of the second curve 1774 * (near its minimal end). This function is used, for example, when 1775 * a new curve is to be inserted into the arrangement. In this case the 1776 * search is conducted over the curves that will comprise a new CCB. 1777 * 1778 * This is the implementation for the case where all 4 boundary sides are 1779 * oblivious. 1780 * 1781 * \param cv1 the given first x-monotone curve 1782 * \param cv2 the given second x-monotone curve 1783 * \param p the shared minimal point of cv1 and cv2 1784 * \param ps_x the parameter space in x of the minimal point of cv1 1785 * \param ps_y the parameter space in y of the minimal point of cv1 1786 * \precondition the minimal points of cv1 and cv2 are equal. 1787 */ 1788 bool _is_smaller_near_right(const X_monotone_curve_2& cv1, 1789 const X_monotone_curve_2& cv2, 1790 const Point_2& p, 1791 Arr_parameter_space ps_x, 1792 Arr_parameter_space ps_y, 1793 Arr_all_sides_oblivious_tag) const; 1794 1795 /*! This is the implementation for the case where any one of the 4 boundary 1796 * sides can be of any type. 1797 */ 1798 bool _is_smaller_near_right(const X_monotone_curve_2& cv1, 1799 const X_monotone_curve_2& cv2, 1800 const Point_2& p, 1801 Arr_parameter_space ps_x, 1802 Arr_parameter_space ps_y, 1803 Arr_not_all_sides_oblivious_tag) const; 1804 1805 /*! 1806 * Locate the place for the given curve around the given vertex. 1807 * \param v The given arrangement vertex. 1808 * \param cv The given x-monotone curve. 1809 * \param ind Whether we refer to the minimal or maximal end of cv. 1810 * \return A pointer to a halfedge whose target is v, where cv should be 1811 * inserted between this halfedge and the next halfedge around this 1812 * vertex (in a clockwise order). 1813 * A nullptr return value indicates a precondition violation. 1814 */ 1815 DHalfedge* _locate_around_vertex(DVertex* v, const X_monotone_curve_2& cv, 1816 Arr_curve_end ind) const; 1817 1818 /*! 1819 * Compute the distance (in halfedges) between two halfedges. 1820 * \param e1 The source halfedge. 1821 * \param e2 The destination halfedge. 1822 * \pre e1 and e2 belong to the same connected component 1823 * \return The number of halfedges along the component boundary between the 1824 * two halfedges. 1825 */ 1826 unsigned int _halfedge_distance(const DHalfedge* e1, 1827 const DHalfedge* e2) const; 1828 1829 /*! 1830 * Compare the length of the induced paths from e1 to e2 and 1831 * from e2 to e1. 1832 * \pre e1 and e2 belong to the same connected component 1833 * \return The comparison result 1834 */ 1835 Comparison_result _compare_induced_path_length(const DHalfedge* e1, 1836 const DHalfedge* e2) const; 1837 1838 /*! 1839 * Update the indices according to boundary locations 1840 */ 1841 void 1842 _compute_indices(Arr_parameter_space ps_x_curr, Arr_parameter_space ps_y_curr, 1843 Arr_parameter_space ps_x_next, Arr_parameter_space ps_y_next, 1844 int& x_index, int& y_index, boost::mpl::bool_<true>) const; 1845 1846 /*! 1847 * Update the indices according to boundary locations (i.e. does nothing) 1848 */ 1849 void 1850 _compute_indices(Arr_parameter_space ps_x_curr, Arr_parameter_space ps_y_curr, 1851 Arr_parameter_space ps_x_next, Arr_parameter_space ps_y_next, 1852 int& x_index, int& y_index, boost::mpl::bool_<false>) const; 1853 1854 /*! 1855 * Is the first given x-monotone curve above the second given? 1856 * \param xcv1 the first given curve 1857 * \param ps_y1 the parameter space in y of xcv1 1858 * \param xcv2 the second given curve 1859 * \param Arr_identified_side_tag used for dispatching to ensure that this 1860 * function is invoked when the bottom and top boundaries are 1861 * identified 1862 */ 1863 bool _is_above(const X_monotone_curve_2& xcv1, 1864 const X_monotone_curve_2& xcv2, 1865 const Point_2& point, 1866 Arr_parameter_space ps_y1, 1867 Arr_has_identified_side_tag) const; 1868 1869 /*! 1870 * Is the first given x-monotone curve above the second given? 1871 * \param xcv1 the first given curve 1872 * \param ps_y1 the parameter space in y of xcv1 1873 * \param xcv2 the second given curve 1874 * \param Arr_contracted_side_tag used for dispatching to ensure that this 1875 * function is invoked when the bottom or top boundaries are 1876 * contracted 1877 */ 1878 bool _is_above(const X_monotone_curve_2& xcv1, 1879 const X_monotone_curve_2& xcv2, 1880 const Point_2& point, 1881 Arr_parameter_space ps_y1, 1882 Arr_has_contracted_side_tag) const; 1883 1884 /*! 1885 * Is the first given x-monotone curve above the second given? 1886 * \param xcv1 the first given curve 1887 * \param ps_y1 the parameter space in y of xcv1 1888 * \param xcv2 the second given curve 1889 * \param Arr_oblivious_side_tag used for dispatching to ensure that this 1890 * function is invoked when the bottom and top boundaries are neither 1891 * identified nor contracted 1892 */ 1893 bool _is_above(const X_monotone_curve_2& xcv1, 1894 const X_monotone_curve_2& xcv2, 1895 const Point_2& point, 1896 Arr_parameter_space ps_y1, 1897 Arr_boundary_cond_tag) const; 1898 1899 /*! 1900 * Compute the signs (in left/right and bottom/top) of a path 1901 * induced by the sequence he_to=>cv,cv_dir=>he_away, and reports 1902 * as side-effect the halfedges pointing to local minima copied 1903 * to an outputiterator. 1904 * \param he_to The predecessor halfedge. 1905 * \param cv The x-monotone curve we use to connect he_to's target and 1906 * he_away's source vertex. 1907 * \param cv_dir the direction of the curve between he_to and he_away 1908 * \param he_away The succcessor halfedge. 1909 * \param local_mins_it the outputiterator 1910 * (value_type = std::pair< DHalfedge*, int >, where the int denotes the 1911 * index) to report the halfedges pointing to local minima (<-shaped 1912 * situation) 1913 * \return A pair of signs for the induced path (ZERO if non-perimetric, 1914 * POSITIVE if perimetric ccb is oriented in positive direction, 1915 * NEGATIVE if perimetric ccb is oriented in negative direction). 1916 */ 1917 template <typename OutputIterator> 1918 std::pair<Sign, Sign> 1919 _compute_signs_and_local_minima(const DHalfedge* he_to, 1920 const X_monotone_curve_2& cv, 1921 Arr_halfedge_direction cv_dir, 1922 const DHalfedge* he_away, 1923 OutputIterator local_mins_it) const; 1924 1925 /*! 1926 * Compute the signs (in left/right and bottom/top) of a closed ccb (loop) 1927 * represented by a given halfedge, and the halfedge pointing to the smallest 1928 * vertex on the ccb. 1929 * \param he The representative halfedge on the ccb. 1930 * \param ps_x_min The parameter space in x of the smallest vertex. 1931 * \param ps_y_min The parameter space in y of the smallest vertex. 1932 * \param index_min The index of the smallest vertex. 1933 * \return A pair of, a pair of signs for the induced path, and the halfedge 1934 * pointing to the smallest vertex. 1935 * A sign ZERO is if the ccb is non-perimetric, 1936 * POSITIVE if the ccb is perimetric and oriented in positive direction, 1937 * NEGATIVE if the ccb is perimetric and oriented in negative direction). 1938 */ 1939 std::pair<std::pair<Sign, Sign>, const DHalfedge*> 1940 _compute_signs_and_min(const DHalfedge* he, 1941 Arr_parameter_space& ps_x_min, 1942 Arr_parameter_space& ps_y_min, 1943 int& index_min) const; 1944 1945 /*! 1946 * Compute the signs (in left/right and bottom/top) of a closed ccb (loop) 1947 * represented by a given halfedge. 1948 * \param he The representative halfedge on the ccb. 1949 * \return A pair of signs for the induced path. 1950 * A sign ZERO is if the ccb is non-perimetric, 1951 * POSITIVE if the ccb is perimetric and oriented in positive direction, 1952 * NEGATIVE if the ccb is perimetric and oriented in negative direction). 1953 */ 1954 std::pair<Sign, Sign> _compute_signs(const DHalfedge* he, 1955 boost::mpl::bool_<true>) const; 1956 1957 /*! Compute the signs (in left/right and bottom/top) of a closed ccb (loop) 1958 * represented by a given halfedge for the case where non of the boundaries 1959 * is identified. 1960 * \return the pair (ZERO, ZERO) 1961 */ 1962 std::pair<Sign, Sign> _compute_signs(const DHalfedge* he, 1963 boost::mpl::bool_<false>) const; 1964 1965 /*! 1966 * Given two predecessor halfedges that will be used for inserting a 1967 * new halfedge pair (he_to is the predecessor of the directed curve 1968 * cv, cv_dir and he_away will be the successor), such that the 1969 * insertion will create a new face that forms a hole inside an existing 1970 * face, determine whether he_to=>cv,cv_dir=>he_away will be part 1971 * of the new outer ccb of the new face. 1972 * \param he_to The predecessor halfedge. 1973 * \param cv The x-monotone curve we use to connect he_to's target and 1974 * he_away's source vertex. 1975 * \param cv_dir the direction of the curve between he_to and he_away 1976 * \param he_away The succcessor halfedge. 1977 * \pre he_to and he_away belong to the same inner CCB. 1978 * \return true if he_to=>cv,cv_dir=>he_away lie in the interior of the face we 1979 * are about to create (i.e.~are part of the new outer ccb), 1980 * false otherwise - in which case the subsequence 1981 * he_away->next()=>cv,opposite(cv_dir)=>he_to->next() 1982 * must be incident to this new face (i.e.~are part 1983 * of the new outer ccb). 1984 */ 1985 template <typename InputIterator> 1986 bool _defines_outer_ccb_of_new_face(const DHalfedge* he_to, 1987 const X_monotone_curve_2& cv, 1988 const DHalfedge* he_away, 1989 InputIterator lm_begin, 1990 InputIterator lm_end) const; 1991 1992 /*! 1993 * Move a given outer CCB from one face to another. 1994 * \param from_face The face currently containing the component. 1995 * \param to_face The face into which we should move the component. 1996 * \param he A halfedge lying on the outer component. 1997 */ 1998 void _move_outer_ccb(DFace* from_face, DFace* to_face, DHalfedge* he); 1999 2000 /*! 2001 * Move a given inner CCB (hole) from one face to another. 2002 * \param from_face The face currently containing the component. 2003 * \param to_face The face into which we should move the component. 2004 * \param he A halfedge lying on the inner component. 2005 */ 2006 void _move_inner_ccb(DFace* from_face, DFace* to_face, DHalfedge* he); 2007 2008 /*! 2009 * Move all inner CCBs (holes) from one face to another. 2010 * \param from_face The face currently containing the components. 2011 * \param to_face The face into which we should move the components. 2012 */ 2013 void _move_all_inner_ccb(DFace* from_face, DFace* to_face); 2014 2015 /*! 2016 * Insert the given vertex as an isolated vertex inside the given face. 2017 * \param f The face that should contain the isolated vertex. 2018 * \param v The isolated vertex. 2019 */ 2020 void _insert_isolated_vertex(DFace* f, DVertex* v); 2021 2022 /*! 2023 * Move a given isolated vertex from one face to another. 2024 * \param from_face The face currently containing the isolated vertex. 2025 * \param to_face The face into which we should move the isolated vertex. 2026 * \param v The isolated vertex. 2027 */ 2028 void _move_isolated_vertex(DFace* from_face, DFace* to_face, DVertex* v); 2029 2030 /*! 2031 * Move all isolated vertices from one face to another. 2032 * \param from_face The face currently containing the isolated vertices. 2033 * \param to_face The face into which we should move the isolated vertices. 2034 */ 2035 void _move_all_isolated_vertices(DFace* from_face, DFace* to_face); 2036 2037 /*! 2038 * Create a new vertex and associate it with the given point. 2039 * \param p The point. 2040 * \return A pointer to the newly created vertex. 2041 */ 2042 DVertex* _create_vertex(const Point_2& p); 2043 2044 /*! 2045 * Create a new boundary vertex. 2046 * \param cv The curve incident to the boundary. 2047 * \param ind The relevant curve-end. 2048 * \param bx The boundary condition in x. 2049 * \param by The boundary condition in y. 2050 * \pre Either bx or by does not equal ARR_INTERIOR. 2051 * \return A pointer to the newly created vertex. 2052 */ 2053 DVertex* _create_boundary_vertex(const X_monotone_curve_2& cv, 2054 Arr_curve_end ind, 2055 Arr_parameter_space bx, 2056 Arr_parameter_space by); 2057 2058 /*! 2059 * Locate the DCEL features that will be used for inserting the given curve 2060 * end, which has a boundary condition, and set a proper vertex there. 2061 * \param f The face that contains the curve end. 2062 * \param cv The x-monotone curve. 2063 * \param ind The curve end. 2064 * \param bx The boundary condition at the x-coordinate. 2065 * \param by The boundary condition at the y-coordinate. 2066 * \param p_pred Output: The predecessor halfedge around this vertex 2067 * (may be nullptr, if no such halfedge exists). 2068 * \return The vertex that corresponds to the curve end. 2069 */ 2070 DVertex* _place_and_set_curve_end(DFace* f, 2071 const X_monotone_curve_2& cv, 2072 Arr_curve_end ind, 2073 Arr_parameter_space bx, 2074 Arr_parameter_space by, 2075 DHalfedge** p_pred); 2076 2077 /*! 2078 * Insert an x-monotone curve into the arrangement, such that both its 2079 * endpoints correspond to free arrangement vertices (newly created vertices 2080 * or existing isolated vertices), so a new inner CCB is formed in the face 2081 * that contains the two vertices. 2082 * \param f The face containing the two end vertices. 2083 * \param cv The given x-monotone curve. 2084 * \param cv_dir The direction of the curve 2085 * \param v1 The free vertex that corresponds to the left endpoint of cv. 2086 * \param v2 The free vertex that corresponds to the right endpoint of cv. 2087 * \return A pointer to one of the halfedges corresponding to the inserted 2088 * curve, directed from v1 to v2. 2089 */ 2090 DHalfedge* _insert_in_face_interior(DFace* f, 2091 const X_monotone_curve_2& cv, 2092 Arr_halfedge_direction cv_dir, 2093 DVertex* v1, DVertex* v2); 2094 2095 /*! 2096 * Insert an x-monotone curve into the arrangement, such that one of its 2097 * endpoints corresponds to a given arrangement vertex, given the exact 2098 * place for the curve in the circular list around this vertex. The other 2099 * endpoint corrsponds to a free vertex (a newly created vertex or an 2100 * isolated vertex). 2101 * \param he_to The reference halfedge. We should represent cv as a pair 2102 * of edges, one of them should become he_to's successor. 2103 * \param cv The given x-monotone curve. 2104 * \param cv_dir The direction of cv. 2105 * \param v The free vertex that corresponds to the other endpoint. 2106 * \return A pointer to one of the halfedges corresponding to the inserted 2107 * curve, whose target is the vertex v. 2108 */ 2109 DHalfedge* _insert_from_vertex(DHalfedge* he_to, const X_monotone_curve_2& cv, 2110 Arr_halfedge_direction cv_dir, 2111 DVertex* v); 2112 2113 /*! 2114 * Insert an x-monotone curve into the arrangement, where the end vertices 2115 * are given by the target points of two given halfedges. 2116 * The two halfedges should be given such that in case a new face is formed, 2117 * it will be the incident face of the halfedge directed from the first 2118 * vertex to the second vertex. 2119 * \param he_to The reference halfedge pointing to the insertion vertex 2120 * \param cv the given curve. 2121 * \param cv_dir the direction of the curve 2122 * \param he_away the reference halfedge for the second vertex. 2123 * \param res the comparison result of the points associated with prev1's 2124 * target vertex and prev2's target vertex. 2125 * \param new_face (Output) indicates whether a new face has been created. 2126 * \param swapped_predecessors (Output) indicates whether roles of prev1 and 2127 * prev2 have been switched 2128 * \param allow_swap_of_predecessors set to false if no swapping should 2129 * take place at all 2130 * \return A pointer to one of the halfedges corresponding to the inserted 2131 * curve directed from prev1's target to prev2's target. 2132 * In case a new face has been created, it is given as the incident 2133 * face of this halfedge. 2134 */ 2135 DHalfedge* _insert_at_vertices(DHalfedge* he_to, 2136 const X_monotone_curve_2& cv, 2137 Arr_halfedge_direction cv_dir, 2138 DHalfedge* he_away, 2139 bool& new_face, 2140 bool& swapped_predecessors, 2141 bool allow_swap_of_predecessors = true); 2142 2143 /*! 2144 * Relocate all inner CCBs and isolated vertices to their proper position, 2145 * immediately after a face has split due to the insertion of a new halfedge. 2146 * \param new_he The new halfedge that caused the split, such that the new 2147 * face lies to its left and the old face to its right. 2148 */ 2149 void _relocate_in_new_face(DHalfedge* new_he); 2150 2151 /*! 2152 * Relocate all inner CCBs to their proper position, 2153 * immediately after a face has split due to the insertion of a new halfedge. 2154 * \param new_he The new halfedge that caused the split, such that the new 2155 * face lies to its left and the old face to its right. 2156 */ 2157 void _relocate_inner_ccbs_in_new_face(DHalfedge* new_he); 2158 2159 /*! 2160 * Relocate all vertices to their proper position, 2161 * immediately after a face has split due to the insertion of a new halfedge. 2162 * \param new_he The new halfedge that caused the split, such that the new 2163 * face lies to its left and the old face to its right. 2164 */ 2165 void _relocate_isolated_vertices_in_new_face(DHalfedge* new_he); 2166 2167 /*! 2168 * Replace the point associated with the given vertex. 2169 * \param v The vertex to modify. 2170 * \param p The point that should be associated with the edge. 2171 */ 2172 void _modify_vertex(DVertex* v, const Point_2& p); 2173 2174 /*! 2175 * Replace the x-monotone curve associated with the given edge. 2176 * \param e The edge to modify. 2177 * \param cv The curve that should be associated with the edge. 2178 */ 2179 void _modify_edge(DHalfedge* he, const X_monotone_curve_2& cv); 2180 2181 /*! 2182 * Check if the given vertex represents one of the ends of a given curve. 2183 * \param v The vertex. 2184 * \param cv The curve. 2185 * \param ind Indicates whether the minimal or the maximal end of cv is 2186 * refereed to. 2187 * \return Whether v represents the left (or right) end of cv. 2188 */ 2189 bool _are_equal(const DVertex* v, 2190 const X_monotone_curve_2& cv, Arr_curve_end ind) const; 2191 2192 /*! 2193 * Split a given edge into two at a given point, and associate the given 2194 * x-monotone curves with the split edges. 2195 * \param e The edge to split (one of the pair of twin halfegdes). 2196 * \param p The split point. 2197 * \param cv1 The curve that should be associated with the first split edge, 2198 * whose source equals e's source and its target is p. 2199 * \param cv2 The curve that should be associated with the second split edge, 2200 * whose source is p and its target equals e's target. 2201 * \return A pointer to the first split halfedge, whose source equals the 2202 * source of e, and whose target is the split point. 2203 */ 2204 DHalfedge* _split_edge(DHalfedge* e, const Point_2& p, 2205 const X_monotone_curve_2& cv1, 2206 const X_monotone_curve_2& cv2); 2207 2208 /*! 2209 * Split a given edge into two at a given vertex, and associate the given 2210 * x-monotone curves with the split edges. 2211 * \param e The edge to split (one of the pair of twin halfegdes). 2212 * \param v The split vertex. 2213 * \param cv1 The curve that should be associated with the first split edge, 2214 * whose source equals e's source and its target is v. 2215 * \param cv2 The curve that should be associated with the second split edge, 2216 * whose source is v and its target equals e's target. 2217 * \return A pointer to the first split halfedge, whose source equals the 2218 * source of e, and whose target is v. 2219 */ 2220 DHalfedge* _split_edge(DHalfedge* e, DVertex* v, 2221 const X_monotone_curve_2& cv1, 2222 const X_monotone_curve_2& cv2); 2223 2224 /*! 2225 * Remove a pair of twin halfedges from the arrangement. 2226 * \param e One of the halfedges to be removed. 2227 * \param remove_source Should the source vertex of e be removed if it 2228 * becomes isolated. 2229 * \param remove_target Should the target vertex of e be removed if it 2230 * becomes isolated. 2231 * \pre In case the removal causes the creation of a new inner CCB (hole), 2232 * e should point at this hole. 2233 * \return A pointer to the remaining face. 2234 */ 2235 DFace* _remove_edge(DHalfedge* e, bool remove_source, bool remove_target); 2236 2237 /*! 2238 * Decide whether a hole is created when an edge is removed. 2239 * 2240 * \param signs1 signs of future ccb1 2241 * \param signs2 signs of future ccb2 2242 * \param same_face to he and he->opposite() belong to same face 2243 * return true, in case a new hole is created, false otherwise 2244 */ 2245 bool _hole_creation_on_edge_removal(std::pair< CGAL::Sign, CGAL::Sign > signs1, 2246 std::pair< CGAL::Sign, CGAL::Sign > signs2, 2247 bool same_face); 2248 2249 /*! 2250 * Remove a vertex in case it becomes redundant after the deletion of an 2251 * incident edge. 2252 * \param v The vertex. 2253 * \param f The face that contains v (in case it becomes isolated). 2254 */ 2255 void _remove_vertex_if_redundant(DVertex* v, DFace* f); 2256 2257 /*! 2258 * Remove an isolated vertex from the interior of its face (but not from 2259 * the DCEL). 2260 * \param v The isolated vertex to remove. 2261 */ 2262 void _remove_isolated_vertex(DVertex* v); 2263 //@} 2264 2265 /// \name Auxiliary (protected) functions for validity checking. 2266 //@{ 2267 2268 /*! Check the validity of a given vertex. */ 2269 bool _is_valid(Vertex_const_handle v) const; 2270 2271 /*! Check the validity of a given halfedge. */ 2272 bool _is_valid(Halfedge_const_handle he) const; 2273 2274 /*! Check the validity of a given face. */ 2275 bool _is_valid(Face_const_handle f) const; 2276 2277 /*! Check the validity of an outer CCB. */ 2278 bool _is_outer_ccb_valid(const DOuter_ccb* oc, const DHalfedge* first) const; 2279 2280 /*! Check the validity of an inner CCB. */ 2281 bool _is_inner_ccb_valid(const DInner_ccb* ic, const DHalfedge* first) const; 2282 2283 /*! 2284 * Check that all vertices are unique (no two vertices with the same 2285 * geometric point. 2286 */ 2287 bool _are_vertices_unique() const; 2288 2289 /*! Check that the curves around a given vertex are ordered clockwise. */ 2290 bool _are_curves_ordered_cw_around_vertrex(Vertex_const_handle v) const; 2291 2292 //@} 2293 2294 protected: 2295 /// \name Managing and notifying the arrangement observers. 2296 //@{ 2297 2298 /*! 2299 * Register a new observer (so it starts receiving notifications). 2300 * \param p_obs A pointer to the observer object. 2301 */ _register_observer(Observer * p_obs)2302 void _register_observer(Observer* p_obs) { m_observers.push_back(p_obs); } 2303 2304 /*! 2305 * Unregister a new observer (so it stops receiving notifications). 2306 * \param p_obs A pointer to the observer object. 2307 * \return Whether the observer was successfully unregistered. 2308 */ _unregister_observer(Observer * p_obs)2309 bool _unregister_observer(Observer* p_obs) 2310 { 2311 Observers_iterator iter; 2312 Observers_iterator end = m_observers.end(); 2313 2314 for (iter = m_observers.begin(); iter != end; ++iter) { 2315 if ((*iter) == p_obs) { 2316 // Remove the p_ob pointer from the list of observers. 2317 m_observers.erase (iter); 2318 return true; 2319 } 2320 } 2321 2322 // If we reached here, the observer was not registered. 2323 return false; 2324 } 2325 2326 protected: 2327 /* Notify the observers on global arrangement operations: */ 2328 _notify_before_assign(const Self & arr)2329 void _notify_before_assign(const Self& arr) 2330 { 2331 Observers_iterator iter; 2332 Observers_iterator end = m_observers.end(); 2333 for (iter = m_observers.begin(); iter != end; ++iter) 2334 (*iter)->before_assign(arr); 2335 } 2336 _notify_after_assign()2337 void _notify_after_assign() 2338 { 2339 Observers_rev_iterator iter; 2340 Observers_rev_iterator end = m_observers.rend(); 2341 for (iter = m_observers.rbegin(); iter != end; ++iter) 2342 (*iter)->after_assign(); 2343 } 2344 _notify_before_clear()2345 void _notify_before_clear() 2346 { 2347 Observers_iterator iter; 2348 Observers_iterator end = m_observers.end(); 2349 for (iter = m_observers.begin(); iter != end; ++iter) 2350 (*iter)->before_clear(); 2351 } 2352 _notify_after_clear()2353 void _notify_after_clear() 2354 { 2355 Observers_rev_iterator iter; 2356 Observers_rev_iterator end = m_observers.rend(); 2357 2358 for (iter = m_observers.rbegin(); iter != end; ++iter) 2359 (*iter)->after_clear(); 2360 } 2361 _notify_before_global_change()2362 void _notify_before_global_change() 2363 { 2364 Observers_iterator iter; 2365 Observers_iterator end = m_observers.end(); 2366 for (iter = m_observers.begin(); iter != end; ++iter) 2367 (*iter)->before_global_change(); 2368 } 2369 _notify_after_global_change()2370 void _notify_after_global_change() 2371 { 2372 Observers_rev_iterator iter; 2373 Observers_rev_iterator end = m_observers.rend(); 2374 for (iter = m_observers.rbegin(); iter != end; ++iter) 2375 (*iter)->after_global_change(); 2376 } 2377 2378 /* Notify the observers on local changes in the arrangement: */ 2379 _notify_before_create_vertex(const Point_2 & p)2380 void _notify_before_create_vertex(const Point_2& p) 2381 { 2382 Observers_iterator iter; 2383 Observers_iterator end = m_observers.end(); 2384 for (iter = m_observers.begin(); iter != end; ++iter) 2385 (*iter)->before_create_vertex(p); 2386 } 2387 _notify_after_create_vertex(Vertex_handle v)2388 void _notify_after_create_vertex(Vertex_handle v) 2389 { 2390 Observers_rev_iterator iter; 2391 Observers_rev_iterator end = m_observers.rend(); 2392 for (iter = m_observers.rbegin(); iter != end; ++iter) 2393 (*iter)->after_create_vertex(v); 2394 } 2395 _notify_before_create_boundary_vertex(const X_monotone_curve_2 & cv,Arr_curve_end ind,Arr_parameter_space bx,Arr_parameter_space by)2396 void _notify_before_create_boundary_vertex(const X_monotone_curve_2& cv, 2397 Arr_curve_end ind, 2398 Arr_parameter_space bx, 2399 Arr_parameter_space by) 2400 { 2401 Observers_iterator iter; 2402 Observers_iterator end = m_observers.end(); 2403 2404 for (iter = m_observers.begin(); iter != end; ++iter) 2405 (*iter)->before_create_boundary_vertex(cv, ind, bx, by); 2406 } 2407 _notify_after_create_boundary_vertex(Vertex_handle v)2408 void _notify_after_create_boundary_vertex(Vertex_handle v) 2409 { 2410 Observers_rev_iterator iter; 2411 Observers_rev_iterator end = m_observers.rend(); 2412 for (iter = m_observers.rbegin(); iter != end; ++iter) 2413 (*iter)->after_create_boundary_vertex(v); 2414 } 2415 _notify_before_create_edge(const X_monotone_curve_2 & c,Vertex_handle v1,Vertex_handle v2)2416 void _notify_before_create_edge(const X_monotone_curve_2& c, 2417 Vertex_handle v1, Vertex_handle v2) 2418 { 2419 Observers_iterator iter; 2420 Observers_iterator end = m_observers.end(); 2421 for (iter = m_observers.begin(); iter != end; ++iter) 2422 (*iter)->before_create_edge(c, v1, v2); 2423 } 2424 _notify_after_create_edge(Halfedge_handle e)2425 void _notify_after_create_edge(Halfedge_handle e) 2426 { 2427 Observers_rev_iterator iter; 2428 Observers_rev_iterator end = m_observers.rend(); 2429 for (iter = m_observers.rbegin(); iter != end; ++iter) 2430 (*iter)->after_create_edge(e); 2431 } 2432 _notify_before_modify_vertex(Vertex_handle v,const Point_2 & p)2433 void _notify_before_modify_vertex(Vertex_handle v, const Point_2& p) 2434 { 2435 Observers_iterator iter; 2436 Observers_iterator end = m_observers.end(); 2437 for (iter = m_observers.begin(); iter != end; ++iter) 2438 (*iter)->before_modify_vertex(v, p); 2439 } 2440 _notify_after_modify_vertex(Vertex_handle v)2441 void _notify_after_modify_vertex(Vertex_handle v) 2442 { 2443 Observers_rev_iterator iter; 2444 Observers_rev_iterator end = m_observers.rend(); 2445 for (iter = m_observers.rbegin(); iter != end; ++iter) 2446 (*iter)->after_modify_vertex(v); 2447 } 2448 _notify_before_modify_edge(Halfedge_handle e,const X_monotone_curve_2 & c)2449 void _notify_before_modify_edge(Halfedge_handle e, 2450 const X_monotone_curve_2& c) 2451 { 2452 Observers_iterator iter; 2453 Observers_iterator end = m_observers.end(); 2454 for (iter = m_observers.begin(); iter != end; ++iter) 2455 (*iter)->before_modify_edge(e, c); 2456 } 2457 _notify_after_modify_edge(Halfedge_handle e)2458 void _notify_after_modify_edge(Halfedge_handle e) 2459 { 2460 Observers_rev_iterator iter; 2461 Observers_rev_iterator end = m_observers.rend(); 2462 for (iter = m_observers.rbegin(); iter != end; ++iter) 2463 (*iter)->after_modify_edge(e); 2464 } 2465 _notify_before_split_edge(Halfedge_handle e,Vertex_handle v,const X_monotone_curve_2 & c1,const X_monotone_curve_2 & c2)2466 void _notify_before_split_edge(Halfedge_handle e, Vertex_handle v, 2467 const X_monotone_curve_2& c1, 2468 const X_monotone_curve_2& c2) 2469 { 2470 Observers_iterator iter; 2471 Observers_iterator end = m_observers.end(); 2472 for (iter = m_observers.begin(); iter != end; ++iter) 2473 (*iter)->before_split_edge(e, v, c1, c2); 2474 } 2475 _notify_after_split_edge(Halfedge_handle e1,Halfedge_handle e2)2476 void _notify_after_split_edge(Halfedge_handle e1, Halfedge_handle e2) 2477 { 2478 Observers_rev_iterator iter; 2479 Observers_rev_iterator end = m_observers.rend(); 2480 for (iter = m_observers.rbegin(); iter != end; ++iter) 2481 (*iter)->after_split_edge(e1, e2); 2482 } 2483 _notify_before_split_fictitious_edge(Halfedge_handle e,Vertex_handle v)2484 void _notify_before_split_fictitious_edge(Halfedge_handle e, Vertex_handle v) 2485 { 2486 Observers_iterator iter; 2487 Observers_iterator end = m_observers.end(); 2488 for (iter = m_observers.begin(); iter != end; ++iter) 2489 (*iter)->before_split_fictitious_edge(e, v); 2490 } 2491 _notify_after_split_fictitious_edge(Halfedge_handle e1,Halfedge_handle e2)2492 void _notify_after_split_fictitious_edge(Halfedge_handle e1, 2493 Halfedge_handle e2) 2494 { 2495 Observers_rev_iterator iter; 2496 Observers_rev_iterator end = m_observers.rend(); 2497 for (iter = m_observers.rbegin(); iter != end; ++iter) 2498 (*iter)->after_split_fictitious_edge(e1, e2); 2499 } 2500 _notify_before_split_face(Face_handle f,Halfedge_handle e)2501 void _notify_before_split_face(Face_handle f, Halfedge_handle e) 2502 { 2503 Observers_iterator iter; 2504 Observers_iterator end = m_observers.end(); 2505 for (iter = m_observers.begin(); iter != end; ++iter) 2506 (*iter)->before_split_face(f, e); 2507 } 2508 _notify_after_split_face(Face_handle f,Face_handle new_f,bool is_hole)2509 void _notify_after_split_face(Face_handle f, Face_handle new_f, bool is_hole) 2510 { 2511 Observers_rev_iterator iter; 2512 Observers_rev_iterator end = m_observers.rend(); 2513 for (iter = m_observers.rbegin(); iter != end; ++iter) 2514 (*iter)->after_split_face(f, new_f, is_hole); 2515 } 2516 _notify_before_split_outer_ccb(Face_handle f,Ccb_halfedge_circulator h,Halfedge_handle e)2517 void _notify_before_split_outer_ccb(Face_handle f, Ccb_halfedge_circulator h, 2518 Halfedge_handle e) 2519 { 2520 Observers_iterator iter; 2521 Observers_iterator end = m_observers.end(); 2522 for (iter = m_observers.begin(); iter != end; ++iter) 2523 (*iter)->before_split_outer_ccb(f, h, e); 2524 } 2525 _notify_after_split_outer_ccb(Face_handle f,Ccb_halfedge_circulator h1,Ccb_halfedge_circulator h2)2526 void _notify_after_split_outer_ccb(Face_handle f, Ccb_halfedge_circulator h1, 2527 Ccb_halfedge_circulator h2) 2528 { 2529 Observers_rev_iterator iter; 2530 Observers_rev_iterator end = m_observers.rend(); 2531 for (iter = m_observers.rbegin(); iter != end; ++iter) 2532 (*iter)->after_split_outer_ccb(f, h1, h2); 2533 } 2534 _notify_before_split_inner_ccb(Face_handle f,Ccb_halfedge_circulator h,Halfedge_handle e)2535 void _notify_before_split_inner_ccb(Face_handle f, Ccb_halfedge_circulator h, 2536 Halfedge_handle e) 2537 { 2538 Observers_iterator iter; 2539 Observers_iterator end = m_observers.end(); 2540 for (iter = m_observers.begin(); iter != end; ++iter) 2541 (*iter)->before_split_inner_ccb(f, h, e); 2542 } 2543 _notify_after_split_inner_ccb(Face_handle f,Ccb_halfedge_circulator h1,Ccb_halfedge_circulator h2)2544 void _notify_after_split_inner_ccb(Face_handle f, 2545 Ccb_halfedge_circulator h1, 2546 Ccb_halfedge_circulator h2) 2547 { 2548 Observers_rev_iterator iter; 2549 Observers_rev_iterator end = m_observers.rend(); 2550 for (iter = m_observers.rbegin(); iter != end; ++iter) 2551 (*iter)->after_split_inner_ccb(f, h1, h2); 2552 } 2553 _notify_before_add_outer_ccb(Face_handle f,Halfedge_handle e)2554 void _notify_before_add_outer_ccb(Face_handle f, Halfedge_handle e) 2555 { 2556 Observers_iterator iter; 2557 Observers_iterator end = m_observers.end(); 2558 for (iter = m_observers.begin(); iter != end; ++iter) 2559 (*iter)->before_add_outer_ccb(f, e); 2560 } 2561 _notify_after_add_outer_ccb(Ccb_halfedge_circulator h)2562 void _notify_after_add_outer_ccb(Ccb_halfedge_circulator h) 2563 { 2564 Observers_rev_iterator iter; 2565 Observers_rev_iterator end = m_observers.rend(); 2566 for (iter = m_observers.rbegin(); iter != end; ++iter) 2567 (*iter)->after_add_outer_ccb(h); 2568 } 2569 _notify_before_add_inner_ccb(Face_handle f,Halfedge_handle e)2570 void _notify_before_add_inner_ccb(Face_handle f, Halfedge_handle e) 2571 { 2572 Observers_iterator iter; 2573 Observers_iterator end = m_observers.end(); 2574 for (iter = m_observers.begin(); iter != end; ++iter) 2575 (*iter)->before_add_inner_ccb(f, e); 2576 } 2577 _notify_after_add_inner_ccb(Ccb_halfedge_circulator h)2578 void _notify_after_add_inner_ccb(Ccb_halfedge_circulator h) 2579 { 2580 Observers_rev_iterator iter; 2581 Observers_rev_iterator end = m_observers.rend(); 2582 for (iter = m_observers.rbegin(); iter != end; ++iter) 2583 (*iter)->after_add_inner_ccb(h); 2584 } 2585 _notify_before_add_isolated_vertex(Face_handle f,Vertex_handle v)2586 void _notify_before_add_isolated_vertex(Face_handle f, Vertex_handle v) 2587 { 2588 Observers_iterator iter; 2589 Observers_iterator end = m_observers.end(); 2590 for (iter = m_observers.begin(); iter != end; ++iter) 2591 (*iter)->before_add_isolated_vertex(f, v); 2592 } 2593 _notify_after_add_isolated_vertex(Vertex_handle v)2594 void _notify_after_add_isolated_vertex(Vertex_handle v) 2595 { 2596 Observers_rev_iterator iter; 2597 Observers_rev_iterator end = m_observers.rend(); 2598 for (iter = m_observers.rbegin(); iter != end; ++iter) 2599 (*iter)->after_add_isolated_vertex(v); 2600 } 2601 _notify_before_merge_edge(Halfedge_handle e1,Halfedge_handle e2,const X_monotone_curve_2 & c)2602 void _notify_before_merge_edge(Halfedge_handle e1, Halfedge_handle e2, 2603 const X_monotone_curve_2& c) 2604 { 2605 Observers_iterator iter; 2606 Observers_iterator end = m_observers.end(); 2607 for (iter = m_observers.begin(); iter != end; ++iter) 2608 (*iter)->before_merge_edge(e1, e2, c); 2609 } 2610 _notify_after_merge_edge(Halfedge_handle e)2611 void _notify_after_merge_edge(Halfedge_handle e) 2612 { 2613 Observers_rev_iterator iter; 2614 Observers_rev_iterator end = m_observers.rend(); 2615 for (iter = m_observers.rbegin(); iter != end; ++iter) 2616 (*iter)->after_merge_edge(e); 2617 } 2618 _notify_before_merge_fictitious_edge(Halfedge_handle e1,Halfedge_handle e2)2619 void _notify_before_merge_fictitious_edge(Halfedge_handle e1, 2620 Halfedge_handle e2) 2621 { 2622 Observers_iterator iter; 2623 Observers_iterator end = m_observers.end(); 2624 for (iter = m_observers.begin(); iter != end; ++iter) 2625 (*iter)->before_merge_fictitious_edge(e1, e2); 2626 } 2627 _notify_after_merge_fictitious_edge(Halfedge_handle e)2628 void _notify_after_merge_fictitious_edge(Halfedge_handle e) 2629 { 2630 Observers_rev_iterator iter; 2631 Observers_rev_iterator end = m_observers.rend(); 2632 for (iter = m_observers.rbegin(); iter != end; ++iter) 2633 (*iter)->after_merge_fictitious_edge(e); 2634 } 2635 _notify_before_merge_face(Face_handle f1,Face_handle f2,Halfedge_handle e)2636 void _notify_before_merge_face(Face_handle f1, Face_handle f2, 2637 Halfedge_handle e) 2638 { 2639 Observers_iterator iter; 2640 Observers_iterator end = m_observers.end(); 2641 for (iter = m_observers.begin(); iter != end; ++iter) 2642 (*iter)->before_merge_face(f1, f2, e); 2643 } 2644 _notify_after_merge_face(Face_handle f)2645 void _notify_after_merge_face(Face_handle f) 2646 { 2647 Observers_rev_iterator iter; 2648 Observers_rev_iterator end = m_observers.rend(); 2649 for (iter = m_observers.rbegin(); iter != end; ++iter) 2650 (*iter)->after_merge_face(f); 2651 } 2652 _notify_before_merge_outer_ccb(Face_handle f,Ccb_halfedge_circulator h1,Ccb_halfedge_circulator h2,Halfedge_handle e)2653 void _notify_before_merge_outer_ccb(Face_handle f, 2654 Ccb_halfedge_circulator h1, 2655 Ccb_halfedge_circulator h2, 2656 Halfedge_handle e) 2657 { 2658 Observers_iterator iter; 2659 Observers_iterator end = m_observers.end(); 2660 for (iter = m_observers.begin(); iter != end; ++iter) 2661 (*iter)->before_merge_outer_ccb(f, h1, h2, e); 2662 } 2663 _notify_after_merge_outer_ccb(Face_handle f,Ccb_halfedge_circulator h)2664 void _notify_after_merge_outer_ccb(Face_handle f, 2665 Ccb_halfedge_circulator h) 2666 { 2667 Observers_rev_iterator iter; 2668 Observers_rev_iterator end = m_observers.rend(); 2669 for (iter = m_observers.rbegin(); iter != end; ++iter) 2670 (*iter)->after_merge_outer_ccb(f, h); 2671 } 2672 _notify_before_merge_inner_ccb(Face_handle f,Ccb_halfedge_circulator h1,Ccb_halfedge_circulator h2,Halfedge_handle e)2673 void _notify_before_merge_inner_ccb(Face_handle f, 2674 Ccb_halfedge_circulator h1, 2675 Ccb_halfedge_circulator h2, 2676 Halfedge_handle e) 2677 { 2678 Observers_iterator iter; 2679 Observers_iterator end = m_observers.end(); 2680 for (iter = m_observers.begin(); iter != end; ++iter) 2681 (*iter)->before_merge_inner_ccb(f, h1, h2, e); 2682 } 2683 _notify_after_merge_inner_ccb(Face_handle f,Ccb_halfedge_circulator h)2684 void _notify_after_merge_inner_ccb(Face_handle f, 2685 Ccb_halfedge_circulator h) 2686 { 2687 Observers_rev_iterator iter; 2688 Observers_rev_iterator end = m_observers.rend(); 2689 for (iter = m_observers.rbegin(); iter != end; ++iter) 2690 (*iter)->after_merge_inner_ccb(f, h); 2691 } 2692 _notify_before_move_outer_ccb(Face_handle from_f,Face_handle to_f,Ccb_halfedge_circulator h)2693 void _notify_before_move_outer_ccb(Face_handle from_f, 2694 Face_handle to_f, 2695 Ccb_halfedge_circulator h) 2696 { 2697 Observers_iterator iter; 2698 Observers_iterator end = m_observers.end(); 2699 for (iter = m_observers.begin(); iter != end; ++iter) 2700 (*iter)->before_move_outer_ccb(from_f, to_f, h); 2701 } 2702 _notify_after_move_outer_ccb(Ccb_halfedge_circulator h)2703 void _notify_after_move_outer_ccb(Ccb_halfedge_circulator h) 2704 { 2705 Observers_rev_iterator iter; 2706 Observers_rev_iterator end = m_observers.rend(); 2707 for (iter = m_observers.rbegin(); iter != end; ++iter) 2708 (*iter)->after_move_outer_ccb(h); 2709 } 2710 _notify_before_move_inner_ccb(Face_handle from_f,Face_handle to_f,Ccb_halfedge_circulator h)2711 void _notify_before_move_inner_ccb(Face_handle from_f, 2712 Face_handle to_f, 2713 Ccb_halfedge_circulator h) 2714 { 2715 Observers_iterator iter; 2716 Observers_iterator end = m_observers.end(); 2717 for (iter = m_observers.begin(); iter != end; ++iter) 2718 (*iter)->before_move_inner_ccb(from_f, to_f, h); 2719 } 2720 _notify_after_move_inner_ccb(Ccb_halfedge_circulator h)2721 void _notify_after_move_inner_ccb(Ccb_halfedge_circulator h) 2722 { 2723 Observers_rev_iterator iter; 2724 Observers_rev_iterator end = m_observers.rend(); 2725 for (iter = m_observers.rbegin(); iter != end; ++iter) 2726 (*iter)->after_move_inner_ccb(h); 2727 } 2728 _notify_before_move_isolated_vertex(Face_handle from_f,Face_handle to_f,Vertex_handle v)2729 void _notify_before_move_isolated_vertex(Face_handle from_f, 2730 Face_handle to_f, 2731 Vertex_handle v) 2732 { 2733 Observers_iterator iter; 2734 Observers_iterator end = m_observers.end(); 2735 for (iter = m_observers.begin(); iter != end; ++iter) 2736 (*iter)->before_move_isolated_vertex(from_f, to_f, v); 2737 } 2738 2739 _notify_after_move_isolated_vertex(Vertex_handle v)2740 void _notify_after_move_isolated_vertex(Vertex_handle v) 2741 { 2742 Observers_rev_iterator iter; 2743 Observers_rev_iterator end = m_observers.rend(); 2744 for (iter = m_observers.rbegin(); iter != end; ++iter) 2745 (*iter)->after_move_isolated_vertex(v); 2746 } 2747 _notify_before_remove_vertex(Vertex_handle v)2748 void _notify_before_remove_vertex(Vertex_handle v) 2749 { 2750 Observers_iterator iter; 2751 Observers_iterator end = m_observers.end(); 2752 for (iter = m_observers.begin(); iter != end; ++iter) 2753 (*iter)->before_remove_vertex(v); 2754 } 2755 _notify_after_remove_vertex()2756 void _notify_after_remove_vertex() 2757 { 2758 Observers_rev_iterator iter; 2759 Observers_rev_iterator end = m_observers.rend(); 2760 for (iter = m_observers.rbegin(); iter != end; ++iter) 2761 (*iter)->after_remove_vertex(); 2762 } 2763 _notify_before_remove_edge(Halfedge_handle e)2764 void _notify_before_remove_edge(Halfedge_handle e) 2765 { 2766 Observers_iterator iter; 2767 Observers_iterator end = m_observers.end(); 2768 for (iter = m_observers.begin(); iter != end; ++iter) 2769 (*iter)->before_remove_edge(e); 2770 } 2771 _notify_after_remove_edge()2772 void _notify_after_remove_edge() 2773 { 2774 Observers_rev_iterator iter; 2775 Observers_rev_iterator end = m_observers.rend(); 2776 for (iter = m_observers.rbegin(); iter != end; ++iter) 2777 (*iter)->after_remove_edge(); 2778 } 2779 _notify_before_remove_outer_ccb(Face_handle f,Ccb_halfedge_circulator h)2780 void _notify_before_remove_outer_ccb(Face_handle f, Ccb_halfedge_circulator h) 2781 { 2782 Observers_iterator iter; 2783 Observers_iterator end = m_observers.end(); 2784 for (iter = m_observers.begin(); iter != end; ++iter) 2785 (*iter)->before_remove_outer_ccb(f, h); 2786 } 2787 _notify_after_remove_outer_ccb(Face_handle f)2788 void _notify_after_remove_outer_ccb(Face_handle f) 2789 { 2790 Observers_rev_iterator iter; 2791 Observers_rev_iterator end = m_observers.rend(); 2792 for (iter = m_observers.rbegin(); iter != end; ++iter) 2793 (*iter)->after_remove_outer_ccb(f); 2794 } 2795 _notify_before_remove_inner_ccb(Face_handle f,Ccb_halfedge_circulator h)2796 void _notify_before_remove_inner_ccb(Face_handle f, Ccb_halfedge_circulator h) 2797 { 2798 Observers_iterator iter; 2799 Observers_iterator end = m_observers.end(); 2800 for (iter = m_observers.begin(); iter != end; ++iter) 2801 (*iter)->before_remove_inner_ccb(f, h); 2802 } 2803 _notify_after_remove_inner_ccb(Face_handle f)2804 void _notify_after_remove_inner_ccb(Face_handle f) 2805 { 2806 Observers_rev_iterator iter; 2807 Observers_rev_iterator end = m_observers.rend(); 2808 for (iter = m_observers.rbegin(); iter != end; ++iter) 2809 (*iter)->after_remove_inner_ccb(f); 2810 } 2811 //@} 2812 }; 2813 2814 //----------------------------------------------------------------------------- 2815 // Declarations of the various global insertion and removal functions. 2816 //----------------------------------------------------------------------------- 2817 2818 // In some compilers there is a template deduction disambiguity between this 2819 // function and the following function receiving two InputIterator. 2820 // For now the solution is to add a dummy variable at the end (referring 2821 // to point-location). Maybe the proper solution is to use boost::enable_if 2822 // together with appropriate tag. 2823 /*! 2824 * Insert a curve or x-monotone curve into the arrangement (incremental 2825 * insertion). 2826 * The inserted curve can be x-monotone (or not) and may intersect the 2827 * existing arrangement. 2828 * \param arr The arrangement. 2829 * \param cv The curve to be inserted. 2830 * \param pl A point-location object associated with the arrangement. 2831 */ 2832 template <typename GeomTraits, typename TopTraits, typename Curve, 2833 typename PointLocation> 2834 void insert(Arrangement_on_surface_2<GeomTraits, TopTraits>& arr, 2835 const Curve& c, const PointLocation& pl, 2836 typename PointLocation::Point_2* = 0); 2837 2838 /*! 2839 * Insert a curve or x-monotone curve into the arrangement (incremental 2840 * insertion). 2841 * The inserted curve can be x-monotone (or not) and may intersect the 2842 * existing arrangement. The default "walk" point-location strategy is used 2843 * for the curve insertion. 2844 * \param arr The arrangement. 2845 * \param cv The curve to be inserted. 2846 */ 2847 template <typename GeomTraits, typename TopTraits, typename Curve> 2848 void insert(Arrangement_on_surface_2<GeomTraits, TopTraits>& arr, 2849 const Curve& c); 2850 2851 /*! 2852 * Insert a range of curves or x-monotone curves into the arrangement 2853 * (aggregated insertion). 2854 * The inserted curves may intersect one another and may also intersect the 2855 * existing arrangement. 2856 * \param arr The arrangement. 2857 * \param begin An iterator for the first curve in the range. 2858 * \param end A past-the-end iterator for the curve range. 2859 * \pre The value type of the iterators must be Curve_2. 2860 */ 2861 template <typename GeomTraits, typename TopTraits, typename InputIterator> 2862 void insert(Arrangement_on_surface_2<GeomTraits, TopTraits>& arr, 2863 InputIterator begin, InputIterator end); 2864 2865 /*! 2866 * Insert an x-monotone curve into the arrangement (incremental insertion) 2867 * when the location of the left endpoint of the curve is known and is 2868 * given as an isertion hint. 2869 * The inserted x-monotone curve may intersect the existing arrangement. 2870 * \param arr The arrangement. 2871 * \param cv The x-monotone curve to be inserted. 2872 * \param obj An object that represents the location of cv's left endpoint 2873 * in the arrangement. 2874 */ 2875 2876 template <typename GeomTraits, typename TopTraits> 2877 void insert(Arrangement_on_surface_2<GeomTraits, TopTraits>& arr, 2878 const typename GeomTraits::X_monotone_curve_2& c, 2879 typename Arr_point_location_result< 2880 Arrangement_on_surface_2<GeomTraits, TopTraits> >::type obj); 2881 2882 /*! 2883 * Insert an x-monotone curve into the arrangement, such that the curve 2884 * interior does not intersect with any existing edge or vertex in the 2885 * arragement (incremental insertion). 2886 * \param arr The arrangement. 2887 * \param c The x-monotone curve to be inserted. 2888 * \param pl A point-location object associated with the arrangement. 2889 * \pre The interior of c does not intersect any existing edge or vertex. 2890 * \return A handle for one of the new halfedges corresponding to the 2891 * inserted curve, directed (lexicographically) from left to right. 2892 */ 2893 template <typename GeomTraits, typename TopTraits, typename PointLocation> 2894 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Halfedge_handle 2895 insert_non_intersecting_curve 2896 (Arrangement_on_surface_2<GeomTraits, TopTraits>& arr, 2897 const typename GeomTraits::X_monotone_curve_2& c, 2898 const PointLocation& pl); 2899 2900 /*! 2901 * Insert an x-monotone curve into the arrangement, such that the curve 2902 * interior does not intersect with any existing edge or vertex in the 2903 * arragement (incremental insertion). The default point-location strategy 2904 * is used for the curve insertion. 2905 * \param arr The arrangement. 2906 * \param c The x-monotone curve to be inserted. 2907 * \pre The interior of c does not intersect any existing edge or vertex. 2908 * \return A handle for one of the new halfedges corresponding to the inserted 2909 * curve, directed (lexicographically) from left to right. 2910 */ 2911 template <typename GeomTraits, typename TopTraits> 2912 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Halfedge_handle 2913 insert_non_intersecting_curve 2914 (Arrangement_on_surface_2<GeomTraits, TopTraits>& arr, 2915 const typename GeomTraits::X_monotone_curve_2& c); 2916 2917 /*! 2918 * Insert a range of pairwise interior-disjoint x-monotone curves into 2919 * the arrangement, such that the curve interiors do not intersect with 2920 * any existing edge or vertex in the arragement (aggregated insertion). 2921 * \param arr The arrangement. 2922 * \param begin An iterator for the first x-monotone curve in the range. 2923 * \param end A past-the-end iterator for the x-monotone curve range. 2924 * \pre The value type of the iterators must be X_monotone_curve_2. 2925 * The curves in the range are pairwise interior-disjoint, and their 2926 * interiors do not intersect any existing edge or vertex. 2927 */ 2928 template <typename GeomTraits, typename TopTraits, typename InputIterator> 2929 void insert_non_intersecting_curves 2930 (Arrangement_on_surface_2<GeomTraits, TopTraits>& arr, 2931 InputIterator begin, InputIterator end); 2932 2933 /*! 2934 * Remove an edge from the arrangement. In case it is possible to merge 2935 * the edges incident to the end-vertices of the removed edge after its 2936 * deletion, the function performs these merges as well. 2937 * \param arr The arrangement. 2938 * \param e The edge to remove (one of the pair of twin halfegdes). 2939 * \return A handle for the remaining face. 2940 */ 2941 template <typename GeomTraits, typename TopTraits> 2942 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Face_handle 2943 remove_edge(Arrangement_on_surface_2<GeomTraits, TopTraits>& arr, 2944 typename Arrangement_on_surface_2<GeomTraits, 2945 TopTraits>::Halfedge_handle e); 2946 2947 /*! 2948 * Insert a vertex that corresponds to a given point into the arrangement. 2949 * The inserted point may lie on any existing arrangement feature. 2950 * \param arr The arrangement. 2951 * \param p The point to be inserted. 2952 * \param pl A point-location object associated with the arrangement. 2953 * \return A handle to the vertex that corresponds to the given point. 2954 */ 2955 template <typename GeomTraits, typename TopTraits, typename PointLocation> 2956 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Vertex_handle 2957 insert_point(Arrangement_on_surface_2<GeomTraits, TopTraits>& arr, 2958 const typename GeomTraits::Point_2& p, 2959 const PointLocation& pl); 2960 2961 /*! 2962 * Insert a vertex that corresponds to a given point into the arrangement. 2963 * The inserted point may lie on any existing arrangement feature. 2964 * \param arr The arrangement. 2965 * \param p The point to be inserted. 2966 * \return A handle to the vertex that corresponds to the given point. 2967 */ 2968 template <typename GeomTraits, typename TopTraits> 2969 typename Arrangement_on_surface_2<GeomTraits, TopTraits>::Vertex_handle 2970 insert_point(Arrangement_on_surface_2<GeomTraits, TopTraits>& arr, 2971 const typename GeomTraits::Point_2& p); 2972 2973 /*! 2974 * Remove a vertex from the arrangement. 2975 * \param arr The arrangement. 2976 * \param v The vertex to remove. 2977 * \return Whether the vertex has been removed or not. 2978 */ 2979 template <typename GeomTraits, typename TopTraits> 2980 bool 2981 remove_vertex(Arrangement_on_surface_2<GeomTraits, TopTraits>& arr, 2982 typename Arrangement_on_surface_2<GeomTraits, 2983 TopTraits>::Vertex_handle v); 2984 2985 2986 /*! 2987 * Check the validity of the arrangement. In particular, check that the 2988 * edegs are disjoint-interior, and the holes are located in their proper 2989 * position. 2990 * \param arr The arrangement. 2991 * \return Whether the arrangement is valid. 2992 */ 2993 template <typename GeomTraits, typename TopTraits> 2994 bool is_valid(const Arrangement_on_surface_2<GeomTraits, TopTraits>& arr); 2995 2996 /*! Compute the zone of the given x-monotone curve in the existing arrangement. 2997 * Meaning, it output the arrangment's vertices, edges and faces that the 2998 * x-monotone curve intersects. 2999 * \param arr The arrangement. 3000 * \param c the x-monotone curve that its zone is computed. 3001 * \param oi the output iterator for the resulting zone elements. Its 3002 * dereference type is a variant that wraps a \c Vertex_handle, a 3003 * \c Halfedge_handle, or a \c Face_handle. 3004 * \param pl the point location strategy used to locate the starting point. 3005 * \return the past-the-end output iterator. 3006 */ 3007 template <typename GeomTraits, typename TopTraits, 3008 typename OutputIterator, typename PointLocation> 3009 OutputIterator zone(Arrangement_on_surface_2<GeomTraits, TopTraits>& arr, 3010 const typename GeomTraits::X_monotone_curve_2& c, 3011 OutputIterator oi, 3012 const PointLocation& pl); 3013 3014 /*! 3015 * Compute the zone of the given x-monotone curve in the existing arrangement. 3016 * Overloaded version with no point location object - the walk point-location 3017 * strategy is used as default. 3018 * \param arr The arrangement. 3019 * \param c the x-monotone curve that its zone was computed. 3020 * \param oi the output iterator for the resulting zone elements. Its 3021 * dereference type is a variant that wraps a \c Vertex_handle, a 3022 * \c Halfedge_handle, or a \c Face_handle. 3023 * \return the past-the-end output iterator. 3024 */ 3025 template <typename GeomTraits, typename TopTraits, typename OutputIterator> 3026 OutputIterator zone(Arrangement_on_surface_2<GeomTraits, TopTraits>& arr, 3027 const typename GeomTraits::X_monotone_curve_2& c, 3028 OutputIterator oi); 3029 3030 /*! 3031 * Checks if the given curve/x-monotone curve intersects the existing 3032 * arrangement. 3033 * \param arr The arrangement. 3034 * \param c The curve/x-monotone curve. 3035 * \param pi The point location strategy that is used to locate the starting 3036 * point. 3037 * \return True if the curve intersect the arrangement, false otherwise. 3038 */ 3039 template <typename GeomTraits, typename TopTraits, typename Curve, 3040 typename PointLocation> 3041 bool do_intersect(Arrangement_on_surface_2<GeomTraits, TopTraits>& arr, 3042 const Curve& c, const PointLocation& pl); 3043 3044 /*! 3045 * Checks if the given curve/x-monotone curve intersects the existing 3046 * arrangement. 3047 * Overloaded version with no point location object - the walk point-location 3048 * strategy is used as default. 3049 * \param arr The arrangement. 3050 * \param c The x-monotone curve/curve. 3051 * \return True if the curve intersect the arrangement, false otherwise. 3052 */ 3053 template <typename GeomTraits, typename TopTraits, typename Curve> 3054 bool do_intersect(Arrangement_on_surface_2<GeomTraits, TopTraits>& arr, 3055 const Curve& c); 3056 3057 } //namespace CGAL 3058 3059 // The function definitions can be found under: 3060 #include <CGAL/Arrangement_2/Arrangement_on_surface_2_impl.h> 3061 #include <CGAL/Arrangement_2/Arrangement_on_surface_2_global.h> 3062 3063 #include <CGAL/enable_warnings.h> 3064 #endif 3065