1 // Copyright (c) 1997 ETH Zurich (Switzerland). 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/Polyhedron/include/CGAL/Polyhedron_3.h $ 7 // $Id: Polyhedron_3.h f55ef7d 2020-10-09T18:36:17+02:00 Mael Rouxel-Labbé 8 // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // 11 // Author(s) : Lutz Kettner <kettner@mpi-sb.mpg.de>) 12 13 #ifndef CGAL_POLYHEDRON_3_H 14 #define CGAL_POLYHEDRON_3_H 1 15 16 #include <CGAL/license/Polyhedron.h> 17 18 #include <CGAL/Polyhedron_3_fwd.h> 19 20 #include <CGAL/HalfedgeDS_iterator.h> 21 #include <CGAL/Iterator_project.h> 22 #include <CGAL/function_objects.h> 23 #include <CGAL/N_step_adaptor_derived.h> 24 #include <CGAL/Polyhedron_items_3.h> 25 #include <CGAL/HalfedgeDS_default.h> 26 #include <CGAL/HalfedgeDS_const_decorator.h> 27 #include <CGAL/HalfedgeDS_decorator.h> 28 #include <CGAL/Modifier_base.h> 29 #include <CGAL/IO/Verbose_ostream.h> 30 #include <CGAL/Polyhedron_traits_3.h> 31 #include <CGAL/iterator.h> 32 33 #include <algorithm> 34 #include <cstddef> 35 36 namespace CGAL { 37 38 template <class VertexBase> 39 class I_Polyhedron_vertex : public VertexBase { 40 public: 41 typedef VertexBase Base; 42 //typedef typename Base::HalfedgeDS HDS; 43 typedef typename Base::Point Point; 44 typedef Point Point_3; 45 46 // Handles have to explicitly repeated, although they are derived 47 typedef typename Base::Vertex_handle Vertex_handle; 48 typedef typename Base::Halfedge_handle Halfedge_handle; 49 typedef typename Base::Face_handle Face_handle; 50 typedef typename Base::Face_handle Facet_handle; 51 typedef typename Base::Vertex_const_handle Vertex_const_handle; 52 typedef typename Base::Halfedge_const_handle Halfedge_const_handle; 53 typedef typename Base::Face_const_handle Face_const_handle; 54 typedef typename Base::Face_const_handle Facet_const_handle; 55 typedef typename Base::Halfedge Halfedge; 56 typedef typename Base::Face Face; 57 typedef typename Base::Face Facet; 58 59 // Supported options by HDS. 60 typedef typename Base::Supports_vertex_halfedge 61 Supports_vertex_halfedge; 62 typedef typename Base::Supports_vertex_point Supports_vertex_point; 63 64 // Circulator category. 65 typedef typename Halfedge::Supports_halfedge_prev Supports_prev; 66 67 public: 68 // Circulator category. 69 typedef HalfedgeDS_circulator_traits<Supports_prev> Ctr; 70 typedef typename Ctr::iterator_category circulator_category; 71 72 // Circulators around a vertex and around a facet. 73 typedef I_HalfedgeDS_facet_circ< Halfedge_handle, circulator_category> 74 Halfedge_around_facet_circulator; 75 76 typedef I_HalfedgeDS_vertex_circ< Halfedge_handle, circulator_category> 77 Halfedge_around_vertex_circulator; 78 79 typedef I_HalfedgeDS_facet_circ< 80 Halfedge_const_handle, 81 circulator_category> Halfedge_around_facet_const_circulator; 82 83 typedef I_HalfedgeDS_vertex_circ< 84 Halfedge_const_handle, 85 circulator_category> Halfedge_around_vertex_const_circulator; 86 87 88 89 typedef typename Halfedge_around_vertex_circulator::size_type 90 size_type; 91 typedef typename Halfedge_around_vertex_circulator::difference_type 92 difference_type; 93 94 public: 95 // We need to repeat the constructors here. I_Polyhedron_vertex()96 I_Polyhedron_vertex() {} I_Polyhedron_vertex(const VertexBase & b)97 I_Polyhedron_vertex( const VertexBase& b) : VertexBase(b) {} I_Polyhedron_vertex(const Point_3 & p)98 I_Polyhedron_vertex( const Point_3& p) : VertexBase(p) {} 99 100 // New Access Functions (not provided in VertexBase). 101 vertex_begin()102 Halfedge_around_vertex_circulator vertex_begin() { 103 // a circulator of halfedges around the vertex (clockwise). 104 return Halfedge_around_vertex_circulator( this->halfedge()); 105 } vertex_begin()106 Halfedge_around_vertex_const_circulator vertex_begin() const { 107 // a circulator of halfedges around the vertex (clockwise). 108 return Halfedge_around_vertex_const_circulator( this->halfedge()); 109 } 110 111 // the degree of the vertex, i.e., edges emanating from this vertex vertex_degree()112 std::size_t vertex_degree() const { 113 return this->halfedge()->vertex_degree(); 114 } degree()115 size_type degree() const { return vertex_degree(); } //backwards compatible 116 117 // returns true if the vertex has exactly two incident edges is_bivalent()118 bool is_bivalent() const { return this->halfedge()->is_bivalent(); } 119 120 // returns true if the vertex has exactly three incident edges is_trivalent()121 bool is_trivalent() const { return this->halfedge()->is_trivalent(); } 122 123 // No longer hidden. Now the restricted version with precondition. 124 // sets incident halfedge to h. Precondition: h is incident, i.e., 125 // h->vertex() == v. set_halfedge(Halfedge_handle hh)126 void set_halfedge( Halfedge_handle hh) { 127 CGAL_assertion( &*(hh->vertex()) == this); 128 Base::set_halfedge(hh); 129 } 130 }; 131 132 // A halfedge is an oriented edge. Both orientations exist, i.e. 133 // an edge is represented by two opposite halfedges. The geometric 134 // relations are as follows: 135 // 136 // _ _ _ . 137 // / |\. 138 // | \. 139 // / \ next half 140 // \ edge 141 // / \. 142 // 143 // | O incident vertex 144 // facet , 145 // | /| | 146 // / | | opposite 147 // \ | | half edge 148 // half | | 149 // \ edge | | / 150 // | |/ 151 // \_ _ _ _ _ _ ' 152 // 153 154 template <class HalfedgeBase> 155 class I_Polyhedron_halfedge : public HalfedgeBase { 156 public: 157 typedef HalfedgeBase Base; 158 typedef typename Base::HalfedgeDS HDS; 159 160 // Handles have to explicitly repeated, although they are derived 161 typedef typename Base::Vertex_handle Vertex_handle; 162 typedef typename Base::Halfedge_handle Halfedge_handle; 163 typedef typename Base::Face_handle Face_handle; 164 typedef typename Base::Face_handle Facet_handle; 165 typedef typename Base::Vertex_const_handle Vertex_const_handle; 166 typedef typename Base::Halfedge_const_handle Halfedge_const_handle; 167 typedef typename Base::Face_const_handle Face_const_handle; 168 typedef typename Base::Face_const_handle Facet_const_handle; 169 170 typedef typename Base::Vertex Vertex; 171 typedef typename Base::Face Face; 172 typedef typename Base::Face Facet; 173 174 // Supported options by HDS. 175 typedef typename Base::Supports_halfedge_prev Supports_halfedge_prev; 176 typedef typename Base::Supports_halfedge_vertex 177 Supports_halfedge_vertex; 178 typedef typename Base::Supports_halfedge_face Supports_halfedge_face; 179 180 // Circulator category. 181 typedef typename Base::Supports_halfedge_prev Supports_prev; 182 183 public: 184 // Circulator category. 185 typedef HalfedgeDS_circulator_traits<Supports_prev> Ctr; 186 typedef typename Ctr::iterator_category circulator_category; 187 188 // Circulators around a vertex and around a facet. 189 typedef I_HalfedgeDS_facet_circ< Halfedge_handle, circulator_category> 190 Halfedge_around_facet_circulator; 191 192 typedef I_HalfedgeDS_vertex_circ< Halfedge_handle, circulator_category> 193 Halfedge_around_vertex_circulator; 194 195 typedef I_HalfedgeDS_facet_circ< 196 Halfedge_const_handle, 197 circulator_category> Halfedge_around_facet_const_circulator; 198 199 typedef I_HalfedgeDS_vertex_circ< 200 Halfedge_const_handle, 201 circulator_category> Halfedge_around_vertex_const_circulator; 202 203 204 205 public: I_Polyhedron_halfedge()206 I_Polyhedron_halfedge() {} I_Polyhedron_halfedge(const HalfedgeBase & b)207 I_Polyhedron_halfedge( const HalfedgeBase& b) : HalfedgeBase(b) {} 208 209 // New Access Functions (not provided in HalfedgeBase). 210 211 // Change semantic of prev: it is always available at this level. 212 // If the HDS does not provide a prev-function, the previous 213 // halfedge will be searched around the incident facet. 214 private: find_prev(Halfedge_handle,Tag_true)215 Halfedge_handle find_prev( Halfedge_handle, Tag_true) { 216 return Base::prev(); 217 } find_prev(Halfedge_const_handle,Tag_true)218 Halfedge_const_handle find_prev( Halfedge_const_handle, Tag_true) const { 219 return Base::prev(); 220 } find_prev(Halfedge_handle h,Tag_false)221 Halfedge_handle find_prev( Halfedge_handle h, Tag_false) const { 222 CGAL_precondition( &*h != this); // we have at least 2-gons 223 while ( &*(h->next()) != this) 224 h = h->next(); 225 return h; 226 } find_prev(Halfedge_const_handle h,Tag_false)227 Halfedge_const_handle find_prev( Halfedge_const_handle h, Tag_false) const{ 228 CGAL_precondition( &*h != this); // we have at least 2-gons 229 while ( &*(h->next()) != this) 230 h = h->next(); 231 return h; 232 } 233 234 public: prev()235 Halfedge_handle prev() { 236 return find_prev( this->next(), Supports_halfedge_prev()); 237 } prev()238 Halfedge_const_handle prev() const { 239 return find_prev( this->next(), Supports_halfedge_prev()); 240 } 241 242 // Make face-functions also available as facet-functions. facet()243 Face_handle facet() { return this->face();} facet()244 Face_const_handle facet() const { return this->face();} 245 246 247 // the next halfedge around the vertex (clockwise). This is equal to 248 // `h.next()->opposite()'. next_on_vertex()249 Halfedge_handle next_on_vertex() { return this->next()->opposite(); } next_on_vertex()250 Halfedge_const_handle next_on_vertex() const { 251 return this->next()->opposite(); 252 } 253 254 // the previous halfedge around the vertex (counterclockwise). Is 255 // equal to `h.opposite()->prev()'. prev_on_vertex()256 Halfedge_handle prev_on_vertex() { return this->opposite()->prev(); } prev_on_vertex()257 Halfedge_const_handle prev_on_vertex() const { 258 return this->opposite()->prev(); 259 } 260 is_border_edge()261 bool is_border_edge() const { 262 // is true if `h' or `h.opposite()' is a border halfedge. 263 return (this->opposite()->is_border() || this->is_border()); 264 } 265 266 // a circulator of halfedges around the vertex (clockwise). vertex_begin()267 Halfedge_around_vertex_circulator vertex_begin() { 268 return Halfedge_around_vertex_circulator( 269 HDS::halfedge_handle(this)); 270 } vertex_begin()271 Halfedge_around_vertex_const_circulator vertex_begin() const { 272 return Halfedge_around_vertex_const_circulator( 273 HDS::halfedge_handle(this)); 274 } 275 276 // a circulator of halfedges around the facet (counterclockwise). facet_begin()277 Halfedge_around_facet_circulator facet_begin() { 278 return Halfedge_around_facet_circulator( 279 HDS::halfedge_handle(this)); 280 } facet_begin()281 Halfedge_around_facet_const_circulator facet_begin() const { 282 return Halfedge_around_facet_const_circulator( 283 HDS::halfedge_handle(this)); 284 } 285 286 // the degree of the incident vertex, i.e., edges emanating from this 287 // vertex vertex_degree()288 std::size_t vertex_degree() const { 289 return circulator_size( vertex_begin()); 290 } 291 292 // the degree of the incident facet, i.e., edges on the boundary of this 293 // facet facet_degree()294 std::size_t facet_degree() const { 295 return circulator_size( facet_begin()); 296 } 297 298 // returns true if the incident vertex has exactly two incident edges is_bivalent()299 bool is_bivalent() const { 300 CGAL_precondition( this != &* (this->next()->opposite())); 301 return (this == &* (this->next()->opposite()->next()->opposite())); 302 } 303 304 // returns true if the incident vertex has exactly three incident edges is_trivalent()305 bool is_trivalent() const { 306 CGAL_precondition( this != &* (this->next()->opposite())); 307 return ( this != &* (this->next()->opposite()->next()->opposite()) 308 && this == &* (this->next()->opposite()->next()->opposite() 309 ->next()->opposite())); 310 } 311 312 // returns true if the incident facet is a triangle. is_triangle()313 bool is_triangle() const { 314 CGAL_precondition( this != &* (this->next())); 315 CGAL_precondition( this != &* (this->next()->next())); 316 return (this == &* (this->next()->next()->next())); 317 } 318 319 // returns true if the incident facet is a quadrilateral. is_quad()320 bool is_quad() const { 321 CGAL_precondition( this != &* (this->next())); 322 CGAL_precondition( this != &* (this->next()->next())); 323 return (this == &* (this->next()->next()->next()->next())); 324 } 325 326 327 private: 328 // Hide some other functions of H. set_next(Halfedge_handle hh)329 void set_next( Halfedge_handle hh) { Base::set_next(hh);} set_prev(Halfedge_handle hh)330 void set_prev( Halfedge_handle hh) { Base::set_prev(hh);} set_vertex(Vertex_handle vv)331 void set_vertex( Vertex_handle vv) { Base::set_vertex(vv);} set_face(Face_handle ff)332 void set_face( Face_handle ff) { Base::set_face(ff);} set_facet(Face_handle ff)333 void set_facet( Face_handle ff) { set_face(ff);} 334 }; 335 336 337 template <class FacetBase> 338 class I_Polyhedron_facet : public FacetBase { 339 public: 340 typedef FacetBase Base; 341 //typedef typename Base::HalfedgeDS HDS; 342 typedef typename Base::Plane Plane; 343 typedef Plane Plane_3; 344 345 // Handles have to explicitly repeated, although they are derived 346 typedef typename Base::Vertex_handle Vertex_handle; 347 typedef typename Base::Halfedge_handle Halfedge_handle; 348 typedef typename Base::Face_handle Face_handle; 349 typedef typename Base::Face_handle Facet_handle; 350 typedef typename Base::Vertex_const_handle Vertex_const_handle; 351 typedef typename Base::Halfedge_const_handle Halfedge_const_handle; 352 typedef typename Base::Face_const_handle Face_const_handle; 353 typedef typename Base::Face_const_handle Facet_const_handle; 354 typedef typename Base::Vertex Vertex; 355 typedef typename Base::Halfedge Halfedge; 356 357 // Supported options by HDS. 358 typedef typename Base::Supports_face_halfedge Supports_face_halfedge; 359 typedef typename Base::Supports_face_plane Supports_face_plane; 360 361 // No longer required. 362 typedef Tag_false Supports_face_normal; 363 364 // Circulator category. 365 typedef typename Halfedge::Supports_halfedge_prev Supports_prev; 366 367 public: 368 // Circulator category. 369 typedef HalfedgeDS_circulator_traits<Supports_prev> Ctr; 370 typedef typename Ctr::iterator_category circulator_category; 371 372 // Circulators around a vertex and around a facet. 373 typedef I_HalfedgeDS_facet_circ< Halfedge_handle, circulator_category> 374 Halfedge_around_facet_circulator; 375 376 typedef I_HalfedgeDS_vertex_circ< Halfedge_handle, circulator_category> 377 Halfedge_around_vertex_circulator; 378 379 typedef I_HalfedgeDS_facet_circ< 380 Halfedge_const_handle, 381 circulator_category> Halfedge_around_facet_const_circulator; 382 383 typedef I_HalfedgeDS_vertex_circ< 384 Halfedge_const_handle, 385 circulator_category> Halfedge_around_vertex_const_circulator; 386 387 388 389 typedef typename Halfedge_around_vertex_circulator::size_type 390 size_type; 391 typedef typename Halfedge_around_vertex_circulator::difference_type 392 difference_type; 393 394 public: 395 // We need to repeat the constructors here. I_Polyhedron_facet()396 I_Polyhedron_facet() {} I_Polyhedron_facet(const FacetBase & b)397 I_Polyhedron_facet( const FacetBase& b) : FacetBase(b) {} 398 399 // New Access Functions (not provided in FacetBase). 400 facet_begin()401 Halfedge_around_facet_circulator facet_begin() { 402 // a circulator of halfedges around the facet (counterclockwise). 403 return Halfedge_around_facet_circulator( this->halfedge()); 404 } facet_begin()405 Halfedge_around_facet_const_circulator facet_begin() const { 406 // a circulator of halfedges around the facet (counterclockwise). 407 return Halfedge_around_facet_const_circulator( this->halfedge()); 408 } 409 410 // the degree of the incident facet, i.e., edges on the boundary of this 411 // facet facet_degree()412 std::size_t facet_degree() const {return this->halfedge()->facet_degree();} size()413 size_type size() const { return facet_degree(); } // backwards compatible 414 415 // returns true if the facet is a triangle. is_triangle()416 bool is_triangle() const { return this->halfedge()->is_triangle(); } 417 418 // returns true if the facet is a quadrilateral. is_quad()419 bool is_quad() const { return this->halfedge()->is_quad(); } 420 421 // No longer hidden. Now the restricted version with precondition. 422 // sets incident halfedge to h. Precondition: h is incident, i.e., 423 // h->face() == v. set_halfedge(Halfedge_handle hh)424 void set_halfedge( Halfedge_handle hh) { 425 CGAL_assertion( &*(hh->facet()) == this); 426 Base::set_halfedge(hh); 427 } 428 }; 429 430 431 template < class Items> 432 class I_Polyhedron_derived_items_3 { 433 public: 434 template < class Refs, class Traits> 435 class Vertex_wrapper { 436 public: 437 typedef typename Items::template Vertex_wrapper<Refs,Traits> VWrap; 438 typedef typename VWrap::Vertex Vertex_base; 439 typedef I_Polyhedron_vertex< Vertex_base> Vertex; 440 }; 441 template < class Refs, class Traits> 442 class Halfedge_wrapper { 443 public: 444 typedef typename Items::template Halfedge_wrapper<Refs,Traits> HWrap; 445 typedef typename HWrap::Halfedge Halfedge_base; 446 typedef I_Polyhedron_halfedge< Halfedge_base> Halfedge; 447 }; 448 template < class Refs, class Traits> 449 class Face_wrapper { 450 public: 451 typedef typename Items::template Face_wrapper<Refs,Traits> FWrap; 452 typedef typename FWrap::Face Face_base; 453 typedef I_Polyhedron_facet< Face_base> Face; 454 }; 455 }; 456 457 458 template < class PolyhedronTraits_3, 459 class PolyhedronItems_3, 460 template < class T, class I, class A> 461 class T_HDS, 462 class Alloc> 463 class Polyhedron_3 { 464 // 465 // DEFINITION 466 // 467 // The boundary representation of a 3d-polyhedron P of the type 468 // Polyhedron consists of vertices, edges and facets. The 469 // vertices are points in space. The edges are straight line 470 // segments. The facets are planar polygons. We restrict here 471 // the facets to be simple planar polygons without holes and the 472 // boundary of the polyhedron to be an oriented 2-manifold. Thus 473 // facets are consistently oriented and an edge is incident to 474 // exactly two facets. We restrict the representation further 475 // that an edge has two distinct incident endpoints and 476 // following duality that an edge has two distinct incident 477 // facets. The class Polyhedron is able to guarantee 478 // the combinatorial properties, but not all geometric 479 // properties. Support functions are provided for testing 480 // geometric properties, e.g. test for self intersections which 481 // is too expensive to be guaranteed as a class invariant. 482 public: 483 typedef Polyhedron_3< PolyhedronTraits_3, PolyhedronItems_3, T_HDS, Alloc> 484 Self; 485 typedef PolyhedronTraits_3 Traits; 486 typedef PolyhedronItems_3 Items; 487 typedef I_Polyhedron_derived_items_3<Items> Derived_items; 488 typedef T_HDS< Traits, Derived_items, Alloc> HDS; 489 typedef HDS HalfedgeDS; 490 491 // portability with older CGAL release 492 typedef HDS Halfedge_data_structure; 493 494 typedef Alloc Allocator; 495 typedef Alloc allocator_type; // STL name 496 497 // Container stuff. 498 typedef typename HDS::size_type size_type; 499 typedef typename HDS::difference_type difference_type; 500 typedef typename HDS::iterator_category iterator_category; 501 typedef typename HDS::Supports_removal Supports_removal; 502 503 // Geometry 504 typedef typename Traits::Point_3 Point_3; 505 typedef Point_3 Point; 506 typedef typename Traits::Plane_3 Plane_3; 507 // No longer required. 508 //typedef typename Traits::Normal Normal; 509 510 // Items 511 typedef typename HDS::Vertex Vertex; 512 typedef typename HDS::Halfedge Halfedge; 513 typedef typename HDS::Face Face; 514 515 typedef typename Vertex::Base VBase; 516 typedef typename Halfedge::Base HBase; 517 typedef typename Face::Base FBase; 518 519 // Handles and Iterators 520 typedef typename HDS::Vertex_handle Vertex_handle; 521 typedef typename HDS::Halfedge_handle Halfedge_handle; 522 typedef typename HDS::Face_handle Face_handle; 523 typedef typename HDS::Vertex_iterator Vertex_iterator; 524 typedef typename HDS::Halfedge_iterator Halfedge_iterator; 525 typedef typename HDS::Face_iterator Face_iterator; 526 527 typedef Iterator_range< Prevent_deref<Vertex_iterator> > Vertex_handles; 528 typedef Iterator_range< Prevent_deref<Halfedge_iterator> > Halfedge_handles; 529 530 typedef typename HDS::Vertex_const_handle Vertex_const_handle; 531 typedef typename HDS::Halfedge_const_handle Halfedge_const_handle; 532 typedef typename HDS::Face_const_handle Face_const_handle; 533 typedef typename HDS::Vertex_const_iterator Vertex_const_iterator; 534 typedef typename HDS::Halfedge_const_iterator Halfedge_const_iterator; 535 typedef typename HDS::Face_const_iterator Face_const_iterator; 536 537 typedef Iterator_range< Prevent_deref<Vertex_const_iterator> > Vertex_const_handles; 538 typedef Iterator_range< Prevent_deref<Halfedge_const_iterator> > Halfedge_const_handles; 539 540 // Auxiliary iterators for convenience 541 typedef Project_point<Vertex> Proj_point; 542 typedef Iterator_project<Vertex_iterator, Proj_point> 543 Point_iterator; 544 typedef Iterator_project<Vertex_const_iterator, Proj_point, 545 const Point_3&, const Point_3*> Point_const_iterator; 546 547 typedef Iterator_range< Point_iterator > Points; 548 typedef Iterator_range< Point_const_iterator > Const_points; 549 550 typedef Project_plane<Face> Proj_plane; 551 typedef Iterator_project<Face_iterator, Proj_plane> 552 Plane_iterator; 553 typedef Iterator_project<Face_const_iterator, Proj_plane, 554 const Plane_3&, const Plane_3*> Plane_const_iterator; 555 556 typedef Iterator_range< Plane_iterator > Planes; 557 typedef Iterator_range< Plane_const_iterator > Const_planes; 558 559 typedef typename HDS::Edge_iterator Edge_iterator; 560 typedef typename HDS::Edge_const_iterator Edge_const_iterator; 561 /* 562 typedef N_step_adaptor_derived<Halfedge_iterator, 2> 563 Edge_iterator; 564 typedef N_step_adaptor_derived<Halfedge_const_iterator, 2> 565 Edge_const_iterator; 566 */ 567 568 typedef Iterator_range< Edge_iterator > Edges; 569 typedef Iterator_range< Edge_const_iterator > Const_edges; 570 571 // All face related types get a related facet type name. 572 typedef Face Facet; 573 typedef Face_handle Facet_handle; 574 typedef Face_iterator Facet_iterator; 575 typedef Face_const_handle Facet_const_handle; 576 typedef Face_const_iterator Facet_const_iterator; 577 578 typedef Iterator_range< Prevent_deref<Facet_iterator> > Facet_handles; 579 typedef Iterator_range< Prevent_deref<Facet_const_iterator> > Facet_const_handles; 580 581 // Supported options by HDS. 582 typedef typename VBase::Supports_vertex_halfedge 583 Supports_vertex_halfedge; 584 typedef typename HBase::Supports_halfedge_prev Supports_halfedge_prev; 585 typedef typename HBase::Supports_halfedge_prev Supports_prev; 586 typedef typename HBase::Supports_halfedge_vertex 587 Supports_halfedge_vertex; 588 typedef typename HBase::Supports_halfedge_face Supports_halfedge_face; 589 typedef typename FBase::Supports_face_halfedge Supports_face_halfedge; 590 591 // Supported options especially for Polyhedron_3. 592 typedef typename VBase::Supports_vertex_point Supports_vertex_point; 593 typedef typename FBase::Supports_face_plane Supports_face_plane; 594 595 // No longer required. 596 typedef Tag_false Supports_face_normal; 597 598 // Renamed versions for facet 599 typedef Supports_halfedge_face Supports_halfedge_facet; 600 typedef Supports_face_halfedge Supports_facet_halfedge; 601 typedef Supports_face_plane Supports_facet_plane; 602 // No longer required. 603 typedef Supports_face_normal Supports_facet_normal; 604 605 public: 606 // Circulator category. 607 typedef HalfedgeDS_circulator_traits<Supports_prev> Ctr; 608 typedef typename Ctr::iterator_category circulator_category; 609 610 // Circulators around a vertex and around a facet. 611 typedef I_HalfedgeDS_facet_circ< Halfedge_handle, circulator_category> 612 Halfedge_around_facet_circulator; 613 614 typedef I_HalfedgeDS_vertex_circ< Halfedge_handle, circulator_category> 615 Halfedge_around_vertex_circulator; 616 617 typedef I_HalfedgeDS_facet_circ< 618 Halfedge_const_handle, 619 circulator_category> Halfedge_around_facet_const_circulator; 620 621 typedef I_HalfedgeDS_vertex_circ< 622 Halfedge_const_handle, 623 circulator_category> Halfedge_around_vertex_const_circulator; 624 625 626 627 protected: 628 HDS hds_; // the boundary representation. 629 Traits m_traits; 630 631 public: hds()632 HDS& hds() { return hds_; } hds()633 const HDS& hds() const { return hds_; } 634 635 // CREATION 636 public: 637 m_traits(trts)638 Polyhedron_3( const Traits& trts = Traits()) : m_traits(trts) {} 639 // the empty polyhedron `P'. 640 641 Polyhedron_3( size_type v, size_type h, size_type f, 642 const Traits& traits = Traits()) hds_(v,h,f)643 : hds_(v,h,f), m_traits(traits) {} 644 // a polyhedron `P' with storage reserved for v vertices, h 645 // halfedges, and f facets. The reservation sizes are a hint for 646 // optimizing storage allocation. 647 reserve(size_type v,size_type h,size_type f)648 void reserve( size_type v, size_type h, size_type f) { 649 // reserve storage for v vertices, h halfedges, and f facets. The 650 // reservation sizes are a hint for optimizing storage allocation. 651 // If the `capacity' is already greater than the requested size 652 // nothing happens. If the `capacity' changes all iterators and 653 // circulators invalidates. 654 hds_.reserve(v,h,f); 655 } 656 657 protected: 658 Halfedge_handle make_triangle(Vertex_handle v1,Vertex_handle v2,Vertex_handle v3)659 make_triangle( Vertex_handle v1, Vertex_handle v2, Vertex_handle v3) { 660 HalfedgeDS_decorator<HDS> decorator(hds_); 661 Halfedge_handle h = hds_.edges_push_back( Halfedge(), Halfedge()); 662 h->HBase::set_next( hds_.edges_push_back( Halfedge(), Halfedge())); 663 h->next()->HBase::set_next( hds_.edges_push_back( Halfedge(), 664 Halfedge())); 665 h->next()->next()->HBase::set_next( h); 666 decorator.set_prev( h, h->next()->next()); 667 decorator.set_prev( h->next(), h); 668 decorator.set_prev( h->next()->next(), h->next()); 669 h->opposite()->HBase::set_next( h->next()->next()->opposite()); 670 h->next()->opposite()->HBase::set_next( h->opposite()); 671 h->next()->next()->opposite()->HBase::set_next( 672 h->next()->opposite()); 673 decorator.set_prev( h->opposite(), h->next()->opposite()); 674 decorator.set_prev( h->next()->opposite(), 675 h->next()->next()->opposite()); 676 decorator.set_prev( h->next()->next()->opposite(), h->opposite()); 677 // the vertices 678 decorator.set_vertex( h, v1); 679 decorator.set_vertex( h->next(), v2); 680 decorator.set_vertex( h->next()->next(), v3); 681 decorator.set_vertex( h->opposite(), v3); 682 decorator.set_vertex( h->next()->opposite(), v1); 683 decorator.set_vertex( h->next()->next()->opposite(), v2); 684 decorator.set_vertex_halfedge( h); 685 decorator.set_vertex_halfedge( h->next()); 686 decorator.set_vertex_halfedge( h->next()->next()); 687 // the facet 688 Facet_handle f = decorator.faces_push_back( Facet()); 689 decorator.set_face( h, f); 690 decorator.set_face( h->next(), f); 691 decorator.set_face( h->next()->next(), f); 692 decorator.set_face_halfedge( h); 693 return h; 694 } 695 696 Halfedge_handle make_tetrahedron(Vertex_handle v1,Vertex_handle v2,Vertex_handle v3,Vertex_handle v4)697 make_tetrahedron( Vertex_handle v1, 698 Vertex_handle v2, 699 Vertex_handle v3, 700 Vertex_handle v4) { 701 HalfedgeDS_decorator<HDS> decorator(hds_); 702 Halfedge_handle h = make_triangle(v1,v2,v3); 703 // The remaining tip. 704 Halfedge_handle g = hds_.edges_push_back( Halfedge(), Halfedge()); 705 decorator.insert_tip( g->opposite(), h->opposite()); 706 decorator.close_tip( g); 707 decorator.set_vertex( g, v4); 708 Halfedge_handle e = hds_.edges_push_back( Halfedge(), Halfedge()); 709 Halfedge_handle d = hds_.edges_push_back( Halfedge(), Halfedge()); 710 decorator.insert_tip( e->opposite(), h->next()->opposite()); 711 decorator.insert_tip( e, g); 712 decorator.insert_tip( d->opposite(),h->next()->next()->opposite()); 713 decorator.insert_tip( d, e); 714 decorator.set_vertex_halfedge( g); 715 // facets 716 Facet_handle f = decorator.faces_push_back( Facet()); 717 decorator.set_face( h->opposite(), f); 718 decorator.set_face( g, f); 719 decorator.set_face( e->opposite(), f); 720 decorator.set_face_halfedge( g); 721 f = decorator.faces_push_back( Facet()); 722 decorator.set_face( h->next()->opposite(), f); 723 decorator.set_face( e, f); 724 decorator.set_face( d->opposite(), f); 725 decorator.set_face_halfedge( e); 726 f = decorator.faces_push_back( Facet()); 727 decorator.set_face( h->next()->next()->opposite(), f); 728 decorator.set_face( d, f); 729 decorator.set_face( g->opposite(), f); 730 decorator.set_face_halfedge( d); 731 return h; 732 } 733 734 public: make_tetrahedron()735 Halfedge_handle make_tetrahedron() { 736 // the combinatorial structure of a tetrahedron is added to the 737 // actual polyhedral surface. Returns an arbitrary halfedge of 738 // this structure. 739 reserve( 4 + size_of_vertices(), 740 12 + size_of_halfedges(), 741 4 + size_of_facets()); 742 HalfedgeDS_decorator<HDS> decorator(hds_); 743 return make_tetrahedron( decorator.vertices_push_back( Vertex()), 744 decorator.vertices_push_back( Vertex()), 745 decorator.vertices_push_back( Vertex()), 746 decorator.vertices_push_back( Vertex())); 747 } 748 make_tetrahedron(const Point_3 & p1,const Point_3 & p2,const Point_3 & p3,const Point_3 & p4)749 Halfedge_handle make_tetrahedron( const Point_3& p1, 750 const Point_3& p2, 751 const Point_3& p3, 752 const Point_3& p4) { 753 reserve( 4 + size_of_vertices(), 754 12 + size_of_halfedges(), 755 4 + size_of_facets()); 756 HalfedgeDS_decorator<HDS> decorator(hds_); 757 return make_tetrahedron( decorator.vertices_push_back( Vertex(p1)), 758 decorator.vertices_push_back( Vertex(p2)), 759 decorator.vertices_push_back( Vertex(p3)), 760 decorator.vertices_push_back( Vertex(p4))); 761 762 } 763 make_triangle()764 Halfedge_handle make_triangle() { 765 // the combinatorial structure of a single triangle with border 766 // edges is added to the actual polyhedral surface. Returns an 767 // arbitrary halfedge of this structure. 768 reserve( 3 + size_of_vertices(), 769 6 + size_of_halfedges(), 770 1 + size_of_facets()); 771 HalfedgeDS_decorator<HDS> decorator(hds_); 772 return make_triangle( decorator.vertices_push_back( Vertex()), 773 decorator.vertices_push_back( Vertex()), 774 decorator.vertices_push_back( Vertex())); 775 } 776 make_triangle(const Point_3 & p1,const Point_3 & p2,const Point_3 & p3)777 Halfedge_handle make_triangle( const Point_3& p1, 778 const Point_3& p2, 779 const Point_3& p3) { 780 // the single triangle p_1, p_2, p_3 with border edges is added to 781 // the actual polyhedral surface. Returns an arbitrary halfedge of 782 // this structure. 783 reserve( 3 + size_of_vertices(), 784 6 + size_of_halfedges(), 785 1 + size_of_facets()); 786 HalfedgeDS_decorator<HDS> decorator(hds_); 787 return make_triangle( decorator.vertices_push_back( Vertex(p1)), 788 decorator.vertices_push_back( Vertex(p2)), 789 decorator.vertices_push_back( Vertex(p3))); 790 } 791 792 // Access Member Functions 793 get_allocator()794 allocator_type get_allocator() const { return hds_.get_allocator(); } 795 size_of_vertices()796 size_type size_of_vertices() const { return hds_.size_of_vertices();} 797 // number of vertices. 798 size_of_halfedges()799 size_type size_of_halfedges() const { return hds_.size_of_halfedges();} 800 // number of all halfedges (including border halfedges). 801 size_of_facets()802 size_type size_of_facets() const { return hds_.size_of_faces();} 803 // number of facets. 804 empty()805 bool empty() const { return size_of_halfedges() == 0; } 806 is_empty()807 bool is_empty() const { return size_of_halfedges() == 0; } 808 capacity_of_vertices()809 size_type capacity_of_vertices() const { 810 // space reserved for vertices. 811 return hds_.capacity_of_vertices(); 812 } 813 capacity_of_halfedges()814 size_type capacity_of_halfedges() const { 815 // space reserved for halfedges. 816 return hds_.capacity_of_halfedges(); 817 } 818 capacity_of_facets()819 size_type capacity_of_facets() const { 820 // space reserved for facets. 821 return hds_.capacity_of_faces(); 822 } 823 bytes()824 std::size_t bytes() const { 825 // bytes used for the polyhedron. 826 return sizeof(Self) - sizeof(HDS) + hds_.bytes(); 827 } 828 bytes_reserved()829 std::size_t bytes_reserved() const { 830 // bytes reserved for the polyhedron. 831 return sizeof(Self) - sizeof(HDS) + hds_.bytes_reserved(); 832 } 833 vertices_begin()834 Vertex_iterator vertices_begin() { return hds_.vertices_begin();} 835 // iterator over all vertices. 836 vertices_end()837 Vertex_iterator vertices_end() { return hds_.vertices_end();} 838 vertex_handles()839 Vertex_handles vertex_handles() { 840 return make_prevent_deref_range(vertices_begin(), vertices_end()); 841 } 842 halfedges_begin()843 Halfedge_iterator halfedges_begin() { return hds_.halfedges_begin();} 844 // iterator over all halfedges 845 halfedges_end()846 Halfedge_iterator halfedges_end() { return hds_.halfedges_end();} 847 halfedge_handles()848 Halfedge_handles halfedge_handles() { 849 return make_prevent_deref_range(halfedges_begin(), halfedges_end()); 850 } 851 facets_begin()852 Facet_iterator facets_begin() { return hds_.faces_begin();} 853 // iterator over all facets 854 facets_end()855 Facet_iterator facets_end() { return hds_.faces_end();} 856 facet_handles()857 Facet_handles facet_handles() { 858 return make_prevent_deref_range(facets_begin(), facets_end()); 859 } 860 861 // The constant iterators and circulators. 862 vertices_begin()863 Vertex_const_iterator vertices_begin() const { 864 return hds_.vertices_begin(); 865 } vertices_end()866 Vertex_const_iterator vertices_end() const { 867 return hds_.vertices_end(); 868 } 869 vertex_handles()870 Vertex_const_handles vertex_handles() const { 871 return make_prevent_deref_range(vertices_begin(), vertices_end()); 872 } 873 halfedges_begin()874 Halfedge_const_iterator halfedges_begin() const { 875 return hds_.halfedges_begin(); 876 } halfedges_end()877 Halfedge_const_iterator halfedges_end() const { 878 return hds_.halfedges_end(); 879 } 880 halfedge_handles()881 Halfedge_const_handles halfedge_handles() const { 882 return make_prevent_deref_range(halfedges_begin(), halfedges_end()); 883 } 884 facets_begin()885 Facet_const_iterator facets_begin() const { return hds_.faces_begin();} facets_end()886 Facet_const_iterator facets_end() const { return hds_.faces_end();} 887 facet_handles()888 Facet_const_handles facet_handles() const { 889 return make_prevent_deref_range(facets_begin(), facets_end()); 890 } 891 892 // Auxiliary iterators for convinience points_begin()893 Point_iterator points_begin() { return vertices_begin();} points_end()894 Point_iterator points_end() { return vertices_end();} 895 points()896 Points points() { 897 return Points(points_begin(), points_end()); 898 } 899 points_begin()900 Point_const_iterator points_begin() const { return vertices_begin();} points_end()901 Point_const_iterator points_end() const { return vertices_end();} 902 points()903 Const_points points() const { 904 return Const_points(points_begin(), points_end()); 905 } 906 planes_begin()907 Plane_iterator planes_begin() { return facets_begin();} planes_end()908 Plane_iterator planes_end() { return facets_end();} 909 planes()910 Planes planes() { 911 return Planes(planes_begin(), planes_end()); 912 } 913 planes_begin()914 Plane_const_iterator planes_begin() const { return facets_begin();} planes_end()915 Plane_const_iterator planes_end() const { return facets_end();} 916 planes()917 Const_planes planes() const { 918 return Const_planes(planes_begin(), planes_end()); 919 } 920 edges_begin()921 Edge_iterator edges_begin() { return halfedges_begin();} 922 // iterator over all edges. The iterator refers to halfedges, but 923 // enumerates only one of the two corresponding opposite 924 // halfedges. edges_end()925 Edge_iterator edges_end() { return halfedges_end();} 926 // end of the range over all edges. 927 edges()928 Edges edges() { 929 return Edges(edges_begin(), edges_end()); 930 } 931 edges_begin()932 Edge_const_iterator edges_begin() const { return halfedges_begin();} edges_end()933 Edge_const_iterator edges_end() const { return halfedges_end();} 934 edges()935 Const_edges edges() const { 936 return Const_edges(edges_begin(), edges_end()); 937 } 938 traits()939 Traits& traits() { return m_traits; } traits()940 const Traits& traits() const { return m_traits; } 941 942 943 // Combinatorial Predicates 944 is_closed()945 bool is_closed() const { 946 for ( Halfedge_const_iterator i = halfedges_begin(); 947 i != halfedges_end(); ++i) { 948 if ( i->is_border()) 949 return false; 950 } 951 return true; 952 } 953 954 private: is_pure_bivalent(Tag_true)955 bool is_pure_bivalent( Tag_true) const { 956 for ( Vertex_const_iterator i = vertices_begin(); 957 i != vertices_end(); ++i) 958 if ( ! i->is_bivalent()) 959 return false; 960 return true; 961 } is_pure_bivalent(Tag_false)962 bool is_pure_bivalent( Tag_false) const { 963 for ( Halfedge_const_iterator i = halfedges_begin(); 964 i != halfedges_end(); ++i) 965 if ( ! i->is_bivalent()) 966 return false; 967 return true; 968 } 969 970 public: 971 // returns true if all vertices have exactly two incident edges is_pure_bivalent()972 bool is_pure_bivalent() const { 973 return is_pure_bivalent( Supports_vertex_halfedge()); 974 } 975 976 private: is_pure_trivalent(Tag_true)977 bool is_pure_trivalent( Tag_true) const { 978 for ( Vertex_const_iterator i = vertices_begin(); 979 i != vertices_end(); ++i) 980 if ( ! i->is_trivalent()) 981 return false; 982 return true; 983 } is_pure_trivalent(Tag_false)984 bool is_pure_trivalent( Tag_false) const { 985 for ( Halfedge_const_iterator i = halfedges_begin(); 986 i != halfedges_end(); ++i) 987 if ( ! i->is_trivalent()) 988 return false; 989 return true; 990 } 991 992 public: 993 // returns true if all vertices have exactly three incident edges is_pure_trivalent()994 bool is_pure_trivalent() const { 995 return is_pure_trivalent( Supports_vertex_halfedge()); 996 } 997 998 private: is_pure_triangle(Tag_true)999 bool is_pure_triangle( Tag_true) const { 1000 for ( Facet_const_iterator i = facets_begin(); 1001 i != facets_end(); ++i) 1002 if ( ! i->is_triangle()) 1003 return false; 1004 return true; 1005 } is_pure_triangle(Tag_false)1006 bool is_pure_triangle( Tag_false) const { 1007 for ( Halfedge_const_iterator i = halfedges_begin(); 1008 i != halfedges_end(); ++i) 1009 if ( ! i->is_border() && ! i->is_triangle()) 1010 return false; 1011 return true; 1012 } 1013 1014 public: 1015 // returns true if all facets are triangles is_pure_triangle()1016 bool is_pure_triangle() const { 1017 return is_pure_triangle( Supports_facet_halfedge()); 1018 } 1019 1020 private: is_pure_quad(Tag_true)1021 bool is_pure_quad( Tag_true) const { 1022 for ( Facet_const_iterator i = facets_begin(); 1023 i != facets_end(); ++i) 1024 if ( ! i->is_quad()) 1025 return false; 1026 return true; 1027 } is_pure_quad(Tag_false)1028 bool is_pure_quad( Tag_false) const { 1029 for ( Halfedge_const_iterator i = halfedges_begin(); 1030 i != halfedges_end(); ++i) 1031 if ( ! i->is_border() && ! i->is_quad()) 1032 return false; 1033 return true; 1034 } 1035 1036 public: 1037 // returns true if all facets are quadrilaterals is_pure_quad()1038 bool is_pure_quad() const { 1039 return is_pure_quad( Supports_facet_halfedge()); 1040 } 1041 1042 1043 // Geometric Predicates 1044 1045 bool is_triangle(Halfedge_const_handle h1)1046 is_triangle( Halfedge_const_handle h1) const { 1047 Halfedge_const_handle h2 = h1->next(); 1048 Halfedge_const_handle h3 = h1->next()->next(); 1049 // check halfedge combinatorics. 1050 // exact two edges at vertices 1, 2, 3. 1051 if ( h1->opposite()->next() != h3->opposite()) return false; 1052 if ( h2->opposite()->next() != h1->opposite()) return false; 1053 if ( h3->opposite()->next() != h2->opposite()) return false; 1054 // The facet is a triangle. 1055 if ( h1->next()->next()->next() != h1) return false; 1056 1057 if ( check_tag( Supports_halfedge_face()) 1058 && ! h1->is_border_edge()) 1059 return false; // implies h2 and h3 1060 CGAL_assertion( ! h1->is_border() || ! h1->opposite()->is_border()); 1061 1062 // Assert consistency. 1063 CGAL_assertion( h1 != h2); 1064 CGAL_assertion( h1 != h3); 1065 CGAL_assertion( h3 != h2); 1066 1067 // check prev pointer. 1068 CGAL_assertion_code( HalfedgeDS_items_decorator<HDS> D;) 1069 CGAL_assertion(D.get_prev(h1) == Halfedge_handle() || 1070 D.get_prev(h1) == h3); 1071 CGAL_assertion(D.get_prev(h2) == Halfedge_handle() || 1072 D.get_prev(h2) == h1); 1073 CGAL_assertion(D.get_prev(h3) == Halfedge_handle() || 1074 D.get_prev(h3) == h2); 1075 1076 // check vertices. 1077 CGAL_assertion( D.get_vertex(h1) == D.get_vertex( h2->opposite())); 1078 CGAL_assertion( D.get_vertex(h2) == D.get_vertex( h3->opposite())); 1079 CGAL_assertion( D.get_vertex(h3) == D.get_vertex( h1->opposite())); 1080 1081 CGAL_assertion( ! check_tag( Supports_halfedge_vertex()) || 1082 D.get_vertex(h1) != D.get_vertex(h2)); 1083 CGAL_assertion( ! check_tag( Supports_halfedge_vertex()) || 1084 D.get_vertex(h1) != D.get_vertex(h3)); 1085 CGAL_assertion( ! check_tag( Supports_halfedge_vertex()) || 1086 D.get_vertex(h2) != D.get_vertex(h3)); 1087 1088 // check facets. 1089 CGAL_assertion( D.get_face(h1) == D.get_face(h2)); 1090 CGAL_assertion( D.get_face(h1) == D.get_face(h3)); 1091 1092 return true; 1093 } 1094 1095 bool is_tetrahedron(Halfedge_const_handle h1)1096 is_tetrahedron( Halfedge_const_handle h1) const { 1097 Halfedge_const_handle h2 = h1->next(); 1098 Halfedge_const_handle h3 = h1->next()->next(); 1099 Halfedge_const_handle h4 = h1->opposite()->next(); 1100 Halfedge_const_handle h5 = h2->opposite()->next(); 1101 Halfedge_const_handle h6 = h3->opposite()->next(); 1102 // check halfedge combinatorics. 1103 // at least three edges at vertices 1, 2, 3. 1104 if ( h4 == h3->opposite()) return false; 1105 if ( h5 == h1->opposite()) return false; 1106 if ( h6 == h2->opposite()) return false; 1107 // exact three edges at vertices 1, 2, 3. 1108 if ( h4->opposite()->next() != h3->opposite()) return false; 1109 if ( h5->opposite()->next() != h1->opposite()) return false; 1110 if ( h6->opposite()->next() != h2->opposite()) return false; 1111 // three edges at v4. 1112 if ( h4->next()->opposite() != h5) return false; 1113 if ( h5->next()->opposite() != h6) return false; 1114 if ( h6->next()->opposite() != h4) return false; 1115 // All facets are triangles. 1116 if ( h1->next()->next()->next() != h1) return false; 1117 if ( h4->next()->next()->next() != h4) return false; 1118 if ( h5->next()->next()->next() != h5) return false; 1119 if ( h6->next()->next()->next() != h6) return false; 1120 // all edges are non-border edges. 1121 if ( h1->is_border()) return false; // implies h2 and h3 1122 CGAL_assertion( ! h2->is_border()); 1123 CGAL_assertion( ! h3->is_border()); 1124 if ( h4->is_border()) return false; 1125 if ( h5->is_border()) return false; 1126 if ( h6->is_border()) return false; 1127 1128 // Assert consistency. 1129 CGAL_assertion( h1 != h2); 1130 CGAL_assertion( h1 != h3); 1131 CGAL_assertion( h3 != h2); 1132 CGAL_assertion( h4 != h5); 1133 CGAL_assertion( h5 != h6); 1134 CGAL_assertion( h6 != h4); 1135 1136 // check prev pointer. 1137 CGAL_assertion_code( HalfedgeDS_items_decorator<HDS> D;) 1138 CGAL_assertion(D.get_prev(h1) == Halfedge_handle() || 1139 D.get_prev(h1) == h3); 1140 CGAL_assertion(D.get_prev(h2) == Halfedge_handle() || 1141 D.get_prev(h2) == h1); 1142 CGAL_assertion(D.get_prev(h3) == Halfedge_handle() || 1143 D.get_prev(h3) == h2); 1144 CGAL_assertion(D.get_prev(h4) == Halfedge_handle() || 1145 D.get_prev(h4) == h1->opposite()); 1146 CGAL_assertion(D.get_prev(h5) == Halfedge_handle() || 1147 D.get_prev(h5) == h2->opposite()); 1148 CGAL_assertion(D.get_prev(h6) == Halfedge_handle() || 1149 D.get_prev(h6) == h3->opposite()); 1150 1151 // check vertices. 1152 CGAL_assertion( D.get_vertex(h1) == D.get_vertex( h2->opposite())); 1153 CGAL_assertion( D.get_vertex(h1) == D.get_vertex( h5->opposite())); 1154 CGAL_assertion( D.get_vertex(h2) == D.get_vertex( h3->opposite())); 1155 CGAL_assertion( D.get_vertex(h2) == D.get_vertex( h6->opposite())); 1156 CGAL_assertion( D.get_vertex(h3) == D.get_vertex( h1->opposite())); 1157 CGAL_assertion( D.get_vertex(h3) == D.get_vertex( h4->opposite())); 1158 CGAL_assertion( D.get_vertex(h4) == D.get_vertex( h5)); 1159 CGAL_assertion( D.get_vertex(h4) == D.get_vertex( h6)); 1160 1161 CGAL_assertion( ! check_tag( Supports_halfedge_vertex()) || 1162 D.get_vertex(h1) != D.get_vertex(h2)); 1163 CGAL_assertion( ! check_tag( Supports_halfedge_vertex()) || 1164 D.get_vertex(h1) != D.get_vertex(h3)); 1165 CGAL_assertion( ! check_tag( Supports_halfedge_vertex()) || 1166 D.get_vertex(h1) != D.get_vertex(h4)); 1167 CGAL_assertion( ! check_tag( Supports_halfedge_vertex()) || 1168 D.get_vertex(h2) != D.get_vertex(h3)); 1169 CGAL_assertion( ! check_tag( Supports_halfedge_vertex()) || 1170 D.get_vertex(h2) != D.get_vertex(h4)); 1171 CGAL_assertion( ! check_tag( Supports_halfedge_vertex()) || 1172 D.get_vertex(h3) != D.get_vertex(h4)); 1173 1174 // check facets. 1175 CGAL_assertion( D.get_face(h1) == D.get_face(h2)); 1176 CGAL_assertion( D.get_face(h1) == D.get_face(h3)); 1177 CGAL_assertion( D.get_face(h4) == D.get_face(h4->next())); 1178 CGAL_assertion( D.get_face(h4) == D.get_face(h1->opposite())); 1179 CGAL_assertion( D.get_face(h5) == D.get_face(h5->next())); 1180 CGAL_assertion( D.get_face(h5) == D.get_face(h2->opposite())); 1181 CGAL_assertion( D.get_face(h6) == D.get_face(h6->next())); 1182 CGAL_assertion( D.get_face(h6) == D.get_face(h3->opposite())); 1183 1184 CGAL_assertion( ! check_tag( Supports_halfedge_face()) || 1185 D.get_face(h1) != D.get_face(h4)); 1186 CGAL_assertion( ! check_tag( Supports_halfedge_face()) || 1187 D.get_face(h1) != D.get_face(h5)); 1188 CGAL_assertion( ! check_tag( Supports_halfedge_face()) || 1189 D.get_face(h1) != D.get_face(h6)); 1190 CGAL_assertion( ! check_tag( Supports_halfedge_face()) || 1191 D.get_face(h4) != D.get_face(h5)); 1192 CGAL_assertion( ! check_tag( Supports_halfedge_face()) || 1193 D.get_face(h4) != D.get_face(h6)); 1194 CGAL_assertion( ! check_tag( Supports_halfedge_face()) || 1195 D.get_face(h5) != D.get_face(h6)); 1196 1197 return true; 1198 } 1199 1200 // Euler Operators (Combinatorial Modifications) 1201 // 1202 // The following Euler operations modify consistently the combinatorial 1203 // structure of the polyhedral surface. The geometry remains unchanged. 1204 split_facet(Halfedge_handle h,Halfedge_handle g)1205 Halfedge_handle split_facet( Halfedge_handle h, Halfedge_handle g) { 1206 // split the facet incident to `h' and `g' into two facets with 1207 // new diagonal between the two vertices denoted by `h' and `g' 1208 // respectively. The second (new) facet is a copy of the first 1209 // facet. It returns the new diagonal. The time is proportional to 1210 // the distance from `h' to `g' around the facet. Precondition: 1211 // `h' and `g' are incident to the same facet. `h != g' (no 1212 // loops). `h->next() != g' and `g->next() != h' (no multi-edges). 1213 reserve( size_of_vertices(), 1214 2 + size_of_halfedges(), 1215 1 + size_of_facets()); 1216 HalfedgeDS_decorator<HDS> D(hds_); 1217 CGAL_precondition( D.get_face(h) == D.get_face(g)); 1218 CGAL_precondition( h != g); 1219 CGAL_precondition( h != g->next()); 1220 CGAL_precondition( h->next() != g); 1221 return D.split_face( h, g); 1222 } 1223 join_facet(Halfedge_handle h)1224 Halfedge_handle join_facet( Halfedge_handle h) { 1225 // join the two facets incident to h. The facet incident to 1226 // `h->opposite()' gets removed. Both facets might be holes. 1227 // Returns the predecessor of h. The invariant `join_facet( 1228 // split_facet( h, g))' returns h and keeps the polyhedron 1229 // unchanged. The time is proportional to the size of the facet 1230 // removed and the time to compute `h.prev()'. Precondition: 1231 // `HDS' supports removal of facets. The degree of both 1232 // vertices incident to h is at least three (no antennas). 1233 HalfedgeDS_decorator<HDS> D(hds_); 1234 CGAL_precondition( circulator_size(h->vertex_begin()) 1235 >= size_type(3)); 1236 CGAL_precondition( circulator_size(h->opposite()->vertex_begin()) 1237 >= size_type(3)); 1238 return D.join_face(h); 1239 } 1240 split_vertex(Halfedge_handle h,Halfedge_handle g)1241 Halfedge_handle split_vertex( Halfedge_handle h, Halfedge_handle g) { 1242 // split the vertex incident to `h' and `g' into two vertices and 1243 // connects them with a new edge. The second (new) vertex is a 1244 // copy of the first vertex. It returns the new edge. The time is 1245 // proportional to the distance from `h' to `g' around the vertex. 1246 // Precondition: `h' and `g' are incident to the same vertex. `h 1247 // != g' (no antennas). `h->next() != g' and `g->next() != h'. 1248 reserve( 1 + size_of_vertices(), 1249 2 + size_of_halfedges(), 1250 size_of_facets()); 1251 HalfedgeDS_decorator<HDS> D(hds_); 1252 CGAL_precondition( D.get_vertex(h) == D.get_vertex(g)); 1253 CGAL_precondition( h != g); 1254 return D.split_vertex( h, g); 1255 } 1256 join_vertex(Halfedge_handle h)1257 Halfedge_handle join_vertex( Halfedge_handle h) { 1258 // join the two vertices incident to h. The vertex denoted by 1259 // `h->opposite()' gets removed. Returns the predecessor of h. The 1260 // invariant `join_vertex( split_vertex( h, g))' returns h and 1261 // keeps the polyhedron unchanged. The time is proportional to 1262 // the degree of the vertex removed and the time to compute 1263 // `h.prev()'. 1264 // Precondition: `HDS' supports removal of vertices. The size of 1265 // both facets incident to h is at least four (no multi-edges) 1266 HalfedgeDS_decorator<HDS> D(hds_); 1267 CGAL_precondition( circulator_size( h->facet_begin()) 1268 >= size_type(4)); 1269 CGAL_precondition( circulator_size( h->opposite()->facet_begin()) 1270 >= size_type(4)); 1271 return D.join_vertex(h); 1272 } 1273 split_edge(Halfedge_handle h)1274 Halfedge_handle split_edge( Halfedge_handle h) { 1275 return split_vertex( h->prev(), h->opposite())->opposite(); 1276 } 1277 flip_edge(Halfedge_handle h)1278 Halfedge_handle flip_edge( Halfedge_handle h) { 1279 HalfedgeDS_items_decorator<HDS> D; 1280 return D.flip_edge(h); 1281 } 1282 create_center_vertex(Halfedge_handle h)1283 Halfedge_handle create_center_vertex( Halfedge_handle h) { 1284 HalfedgeDS_decorator<HDS> D(hds_); 1285 CGAL_assertion( circulator_size( h->facet_begin()) 1286 >= size_type(3)); 1287 return D.create_center_vertex(h); 1288 } 1289 erase_center_vertex(Halfedge_handle h)1290 Halfedge_handle erase_center_vertex( Halfedge_handle h) { 1291 HalfedgeDS_decorator<HDS> D(hds_); 1292 return D.erase_center_vertex(h); 1293 } 1294 1295 // Euler Operators Modifying Genus 1296 split_loop(Halfedge_handle h,Halfedge_handle i,Halfedge_handle j)1297 Halfedge_handle split_loop( Halfedge_handle h, 1298 Halfedge_handle i, 1299 Halfedge_handle j) { 1300 // cut the polyhedron into two parts along the cycle (h,i,j). 1301 // Three copies of the vertices and two new triangles will be 1302 // created. h,i,j will be incident to the first new triangle. The 1303 // returnvalue will be an halfedge iterator denoting the new 1304 // halfegdes of the second new triangle which was h beforehand. 1305 // Precondition: h,i,j are distinct, consecutive vertices of the 1306 // polyhedron and form a cycle: i.e. `h->vertex() == i->opposite() 1307 // ->vertex()', ..., `j->vertex() == h->opposite()->vertex()'. The 1308 // six facets incident to h,i,j are all distinct. 1309 reserve( 3 + size_of_vertices(), 1310 6 + size_of_halfedges(), 1311 2 + size_of_facets()); 1312 HalfedgeDS_decorator<HDS> D(hds_); 1313 CGAL_precondition( h != i); 1314 CGAL_precondition( h != j); 1315 CGAL_precondition( i != j); 1316 CGAL_precondition( D.get_vertex(h) == D.get_vertex(i->opposite())); 1317 CGAL_precondition( D.get_vertex(i) == D.get_vertex(j->opposite())); 1318 CGAL_precondition( D.get_vertex(j) == D.get_vertex(h->opposite())); 1319 CGAL_precondition( D.get_face(h) == Facet_handle() || 1320 D.get_face(h) != D.get_face(i)); 1321 CGAL_precondition( D.get_face(h) == Facet_handle() || 1322 D.get_face(h) != D.get_face(j)); 1323 CGAL_precondition( D.get_face(i) == Facet_handle() || 1324 D.get_face(i) != D.get_face(j)); 1325 CGAL_precondition( D.get_face(h) == Facet_handle() || 1326 D.get_face(h) != D.get_face(h->opposite())); 1327 CGAL_precondition( D.get_face(h) == Facet_handle() || 1328 D.get_face(h) != D.get_face(i->opposite())); 1329 CGAL_precondition( D.get_face(h) == Facet_handle() || 1330 D.get_face(h) != D.get_face(j->opposite())); 1331 CGAL_precondition( D.get_face(i) == Facet_handle() || 1332 D.get_face(i) != D.get_face(h->opposite())); 1333 CGAL_precondition( D.get_face(i) == Facet_handle() || 1334 D.get_face(i) != D.get_face(i->opposite())); 1335 CGAL_precondition( D.get_face(i) == Facet_handle() || 1336 D.get_face(i) != D.get_face(j->opposite())); 1337 CGAL_precondition( D.get_face(j) == Facet_handle() || 1338 D.get_face(j) != D.get_face(h->opposite())); 1339 CGAL_precondition( D.get_face(j) == Facet_handle() || 1340 D.get_face(j) != D.get_face(i->opposite())); 1341 CGAL_precondition( D.get_face(j) == Facet_handle() || 1342 D.get_face(j) != D.get_face(j->opposite())); 1343 CGAL_precondition( D.get_face(h->opposite()) == Facet_handle() || 1344 D.get_face(h->opposite()) != D.get_face(i->opposite())); 1345 CGAL_precondition( D.get_face(h->opposite()) == Facet_handle() || 1346 D.get_face(h->opposite()) != D.get_face(j->opposite())); 1347 CGAL_precondition( D.get_face(i->opposite()) == Facet_handle() || 1348 D.get_face(i->opposite()) != D.get_face(j->opposite())); 1349 return D.split_loop( h, i, j); 1350 } 1351 join_loop(Halfedge_handle h,Halfedge_handle g)1352 Halfedge_handle join_loop( Halfedge_handle h, Halfedge_handle g) { 1353 // glues the boundary of two facets together. Both facets and the 1354 // vertices of g gets removed. Returns an halfedge iterator for h. 1355 // The invariant `join_loop( h, split_loop( h, i, j))' returns h 1356 // and keeps the polyhedron unchanged. Precondition: `HDS' 1357 // supports removal of vertices and facets. The facets denoted by 1358 // h and g have equal size. 1359 HalfedgeDS_decorator<HDS> D(hds_); 1360 CGAL_precondition( D.get_face(h) == Facet_handle() || 1361 D.get_face(h) != D.get_face(g)); 1362 CGAL_precondition( circulator_size( h->facet_begin()) 1363 >= size_type(3)); 1364 CGAL_precondition( circulator_size( h->facet_begin()) 1365 == circulator_size( g->facet_begin())); 1366 return D.join_loop( h, g); 1367 } 1368 1369 // Modifying Facets and Holes 1370 make_hole(Halfedge_handle h)1371 Halfedge_handle make_hole( Halfedge_handle h) { 1372 // removes incident facet and makes all halfedges incident to the 1373 // facet to border edges. Returns h. Precondition: `HDS' 1374 // supports removal of facets. `! h.is_border()'. 1375 HalfedgeDS_decorator<HDS> D(hds_); 1376 return D.make_hole(h); 1377 } 1378 fill_hole(Halfedge_handle h)1379 Halfedge_handle fill_hole( Halfedge_handle h) { 1380 // fill a hole with a new created facet. Makes all border 1381 // halfedges of the hole denoted by h incident to the new facet. 1382 // Returns h. Precondition: `h.is_border()'. 1383 reserve( size_of_vertices(), 1384 size_of_halfedges(), 1385 1 + size_of_facets()); 1386 HalfedgeDS_decorator<HDS> D(hds_); 1387 return D.fill_hole(h); 1388 } 1389 add_vertex_and_facet_to_border(Halfedge_handle h,Halfedge_handle g)1390 Halfedge_handle add_vertex_and_facet_to_border( Halfedge_handle h, 1391 Halfedge_handle g) { 1392 // creates a new facet within the hole incident to h and g by 1393 // connecting the tip of g with the tip of h with two new 1394 // halfedges and a new vertex and filling this separated part of 1395 // the hole with a new facet. Returns the new halfedge incident to 1396 // the new facet and the new vertex. Precondition: `h->is_border( 1397 // )', `g->is_border()', `h != g', and g can be reached along the 1398 // same hole starting with h. 1399 CGAL_precondition( h != g); 1400 reserve( 1 + size_of_vertices(), 1401 4 + size_of_halfedges(), 1402 1 + size_of_facets()); 1403 HalfedgeDS_decorator<HDS> D(hds_); 1404 Halfedge_handle hh = D.add_face_to_border( h, g); 1405 CGAL_assertion( hh == g->next()); 1406 D.split_vertex( g, hh->opposite()); 1407 return g->next(); 1408 } 1409 add_facet_to_border(Halfedge_handle h,Halfedge_handle g)1410 Halfedge_handle add_facet_to_border( Halfedge_handle h, 1411 Halfedge_handle g) { 1412 // creates a new facet within the hole incident to h and g by 1413 // connecting the tip of g with the tip of h with a new halfedge 1414 // and filling this separated part of the hole with a new facet. 1415 // Returns the new halfedge incident to the new facet. 1416 // Precondition: `h->is_border()', `g->is_border()', `h != g', 1417 // `h->next() != g', and g can be reached along the same hole 1418 // starting with h. 1419 CGAL_precondition( h != g); 1420 CGAL_precondition( h->next() != g); 1421 reserve( size_of_vertices(), 1422 2 + size_of_halfedges(), 1423 1 + size_of_facets()); 1424 HalfedgeDS_decorator<HDS> D(hds_); 1425 return D.add_face_to_border( h, g); 1426 } 1427 1428 // Erasing 1429 erase_facet(Halfedge_handle h)1430 void erase_facet( Halfedge_handle h) { 1431 // removes the incident facet of h and changes all halfedges 1432 // incident to the facet into border edges or removes them from 1433 // the polyhedral surface if they were already border edges. See 1434 // `make_hole(h)' for a more specialized variant. Precondition: 1435 // `Traits' supports removal. 1436 HalfedgeDS_decorator<HDS> D(hds_); 1437 D.erase_face(h); 1438 } 1439 erase_connected_component(Halfedge_handle h)1440 void erase_connected_component( Halfedge_handle h) { 1441 // removes the vertices, halfedges, and facets that belong to the 1442 // connected component of h. Precondition: `Traits' supports 1443 // removal. 1444 HalfedgeDS_decorator<HDS> D(hds_); 1445 D.erase_connected_component(h); 1446 } 1447 1448 /// Erases the small connected components and the isolated vertices. 1449 /// 1450 /// @commentheading Preconditions: 1451 /// supports vertices, halfedges, and removal operation. 1452 /// 1453 /// @commentheading Template Parameters: 1454 /// @param nb_components_to_keep the number of large connected components to keep. 1455 /// 1456 /// @return the number of connected components erased (ignoring isolated vertices). keep_largest_connected_components(unsigned int nb_components_to_keep)1457 unsigned int keep_largest_connected_components(unsigned int nb_components_to_keep) 1458 { 1459 HalfedgeDS_decorator<HDS> D(hds_); 1460 return D.keep_largest_connected_components(nb_components_to_keep); 1461 } 1462 clear()1463 void clear() { hds_.clear(); } 1464 // removes all vertices, halfedges, and facets. 1465 erase_all()1466 void erase_all() { clear(); } 1467 // equivalent to `clear()'. Depricated. 1468 1469 // Special Operations on Polyhedral Surfaces 1470 delegate(Modifier_base<HDS> & modifier)1471 void delegate( Modifier_base<HDS>& modifier) { 1472 // calls the `operator()' of the `modifier'. Precondition: The 1473 // `modifier' returns a consistent representation. 1474 modifier( hds_); 1475 CGAL_expensive_postcondition( is_valid()); 1476 } 1477 1478 // Operations with Border Halfedges 1479 size_of_border_halfedges()1480 size_type size_of_border_halfedges() const { 1481 // number of border halfedges. An edge with no incident facet 1482 // counts as two border halfedges. Precondition: `normalize_border 1483 // ()' has been called and no halfedge insertion or removal and no 1484 // change in border status of the halfedges have occurred since 1485 // then. 1486 return hds_.size_of_border_halfedges(); 1487 } 1488 size_of_border_edges()1489 size_type size_of_border_edges() const { 1490 // number of border edges. If `size_of_border_edges() == 1491 // size_of_border_halfedges()' all border edges are incident to a 1492 // facet on one side and to a hole on the other side. 1493 // Precondition: `normalize_border()' has been called and no 1494 // halfedge insertion or removal and no change in border status of 1495 // the halfedges have occurred since then. 1496 return hds_.size_of_border_edges(); 1497 } 1498 border_halfedges_begin()1499 Halfedge_iterator border_halfedges_begin() { 1500 // halfedge iterator starting with the border edges. The range [ 1501 // `halfedges_begin(), border_halfedges_begin()') denotes all 1502 // non-border edges. The range [`border_halfedges_begin(), 1503 // halfedges_end()') denotes all border edges. Precondition: 1504 // `normalize_border()' has been called and no halfedge insertion 1505 // or removal and no change in border status of the halfedges have 1506 // occurred since then. 1507 return hds_.border_halfedges_begin(); 1508 } border_halfedges_begin()1509 Halfedge_const_iterator border_halfedges_begin() const { 1510 return hds_.border_halfedges_begin(); 1511 } 1512 1513 // Convenient edge iterator border_edges_begin()1514 Edge_iterator border_edges_begin() { return border_halfedges_begin(); } border_edges_begin()1515 Edge_const_iterator border_edges_begin() const { 1516 return border_halfedges_begin(); 1517 } 1518 1519 bool normalized_border_is_valid( bool verbose = false) const { 1520 // checks whether all non-border edges precedes the border edges. 1521 HalfedgeDS_const_decorator<HDS> decorator(hds_); 1522 bool valid = decorator.normalized_border_is_valid( verbose); 1523 for ( Halfedge_const_iterator i = border_halfedges_begin(); 1524 valid && (i != halfedges_end()); (++i, ++i)) { 1525 if ( i->is_border()) { 1526 Verbose_ostream verr(verbose); 1527 verr << " both halfedges of an edge are border " 1528 "halfedges." << std::endl; 1529 valid = false; 1530 } 1531 } 1532 return valid; 1533 } 1534 normalize_border()1535 void normalize_border() { 1536 // sorts halfedges such that the non-border edges precedes the 1537 // border edges. 1538 hds_.normalize_border(); 1539 CGAL_postcondition( normalized_border_is_valid()); 1540 } 1541 1542 protected: // Supports_face_plane inside_out_geometry(Tag_false)1543 void inside_out_geometry( Tag_false) {} inside_out_geometry(Tag_true)1544 void inside_out_geometry( Tag_true) { 1545 typename Traits::Construct_opposite_plane_3 opp 1546 = traits().construct_opposite_plane_3_object(); 1547 std::transform( planes_begin(), planes_end(), planes_begin(), opp); 1548 } 1549 1550 public: inside_out()1551 void inside_out() { 1552 // reverse facet orientation. 1553 HalfedgeDS_decorator<HDS> decorator(hds_); 1554 decorator.inside_out(); 1555 inside_out_geometry( Supports_face_plane()); 1556 } 1557 1558 bool is_valid( bool verb = false, int level = 0) const { 1559 // checks the combinatorial consistency. 1560 Verbose_ostream verr(verb); 1561 verr << "begin CGAL::Polyhedron_3<...>::is_valid( verb=true, " 1562 "level = " << level << "):" << std::endl; 1563 HalfedgeDS_const_decorator<HDS> D(hds_); 1564 bool valid = D.is_valid( verb, level + 3); 1565 // All halfedges. 1566 Halfedge_const_iterator i = halfedges_begin(); 1567 Halfedge_const_iterator end = halfedges_end(); 1568 size_type n = 0; 1569 for( ; valid && (i != end); ++i) { 1570 verr << "halfedge " << n << std::endl; 1571 // At least triangular facets and distinct geometry. 1572 valid = valid && ( i->next() != i); 1573 valid = valid && ( i->next()->next() != i); 1574 valid = valid && ( ! check_tag( Supports_halfedge_vertex()) || 1575 D.get_vertex(i) != D.get_vertex(i->opposite())); 1576 valid = valid && ( ! check_tag( Supports_halfedge_vertex()) || 1577 D.get_vertex(i) != D.get_vertex(i->next())); 1578 valid = valid && ( ! check_tag( Supports_halfedge_vertex()) || 1579 D.get_vertex(i) != D.get_vertex(i->next()->next())); 1580 if ( ! valid) { 1581 verr << " incident facet is not at least a triangle." 1582 << std::endl; 1583 break; 1584 } 1585 // Distinct facets on each side of an halfegde. 1586 valid = valid && ( ! check_tag( Supports_halfedge_face()) || 1587 D.get_face(i) != D.get_face(i->opposite())); 1588 if ( ! valid) { 1589 verr << " both incident facets are equal." << std::endl; 1590 break; 1591 } 1592 ++n; 1593 } 1594 valid = valid && (n == size_of_halfedges()); 1595 if ( n != size_of_halfedges()) 1596 verr << "counting halfedges failed." << std::endl; 1597 1598 verr << "end of CGAL::Polyhedron_3<...>::is_valid(): structure is " 1599 << ( valid ? "valid." : "NOT VALID.") << std::endl; 1600 return valid; 1601 } 1602 }; 1603 1604 } //namespace CGAL 1605 1606 #include <CGAL/boost/graph/graph_traits_Polyhedron_3.h> 1607 1608 #include <CGAL/IO/Polyhedron_iostream.h> 1609 1610 #endif // CGAL_POLYHEDRON_3_H // 1611