1 // Copyright (c) 2011 CNRS and LIRIS' Establishments (France). 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/Linear_cell_complex/include/CGAL/Linear_cell_complex_base.h $ 7 // $Id: Linear_cell_complex_base.h daab969 2020-04-08T09:23:59+02:00 Guillaume Damiand 8 // SPDX-License-Identifier: LGPL-3.0-or-later OR LicenseRef-Commercial 9 // 10 // Author(s) : Guillaume Damiand <guillaume.damiand@liris.cnrs.fr> 11 // 12 #ifndef CGAL_LINEAR_CELL_COMPLEX_BASE_H 13 #define CGAL_LINEAR_CELL_COMPLEX_BASE_H 1 14 15 #include <CGAL/Linear_cell_complex_fwd.h> 16 #include <CGAL/Combinatorial_map_functors.h> 17 #include <CGAL/internal/Combinatorial_map_internal_functors.h> 18 #include <CGAL/Linear_cell_complex_operations.h> 19 #include <CGAL/Origin.h> 20 21 #include<map> 22 23 namespace CGAL { 24 25 // Tags allowing to make some template specialization for CMap and GMap, 26 // if necessary. 27 struct Combinatorial_map_tag; 28 struct Generalized_map_tag; 29 30 31 /** @file Linear_cell_complex_base.h 32 * Definition of a linear cell complex, i.e. a combinatorial data structure 33 * (cmap or gmap) with points associated to all vertices. 34 */ 35 36 /** Linear_cell_complex_base class. 37 * The Linear_cell_complex a nD object with linear geometry, ie 38 * an nD map with point associated to each vertex. 39 */ 40 template < unsigned int d_, unsigned int ambient_dim, 41 class Traits_, 42 class Items_, 43 class Alloc_, 44 template<unsigned int,class,class,class,class> 45 class Map, 46 class Refs_, 47 class Storage_> 48 class Linear_cell_complex_base: 49 public Map<d_, Refs_, Items_, Alloc_, Storage_> 50 { 51 public: 52 typedef Linear_cell_complex_base<d_, ambient_dim, 53 Traits_, Items_, Alloc_, Map, 54 Refs_, Storage_> Self; 55 typedef Map<d_, Refs_, Items_, Alloc_, Storage_> Base; 56 57 typedef Traits_ Traits; 58 typedef Items_ Items; 59 typedef Alloc_ Alloc; 60 typedef Storage_ Storage; 61 typedef Refs_ Refs; 62 63 static const unsigned int ambient_dimension = ambient_dim; 64 static const unsigned int dimension = Base::dimension; 65 66 typedef typename Storage::Dart_handle Dart_handle; 67 typedef typename Storage::Dart_const_handle Dart_const_handle; 68 typedef typename Storage::Helper Helper; 69 70 typedef typename Storage::Point Point; 71 typedef typename Storage::Vector Vector; 72 typedef typename Storage::FT FT; 73 74 typedef typename Base::Dart_range Dart_range; 75 76 /// Typedef for attributes 77 template<int i> 78 struct Attribute_type: public Base::template Attribute_type<i> 79 {}; 80 template<int i> 81 struct Attribute_handle: public Base::template Attribute_handle<i> 82 {}; 83 template<int i> 84 struct Attribute_const_handle: 85 public Base::template Attribute_const_handle<i> 86 {}; 87 template<int i> 88 struct Attribute_range: public Base::template Attribute_range<i> 89 {}; 90 template<int i> 91 struct Attribute_const_range: 92 public Base::template Attribute_const_range<i> 93 {}; 94 95 typedef typename Base::template Attribute_type<0>::type Vertex_attribute; 96 typedef typename Base::template Attribute_handle<0>::type 97 Vertex_attribute_handle; 98 typedef typename Base::template Attribute_const_handle<0>::type 99 Vertex_attribute_const_handle; 100 101 typedef typename Base::template Attribute_range<0>::type 102 Vertex_attribute_range; 103 typedef typename Base::template Attribute_const_range<0>::type 104 Vertex_attribute_const_range; 105 106 typedef typename Base::size_type size_type; 107 typedef typename Base::Use_index Use_index; 108 typedef typename Base::Exception_no_more_available_mark 109 Exception_no_more_available_mark; 110 111 /// To use previous definition of create_dart methods. 112 using Base::create_dart; 113 using Base::attribute; 114 using Base::null_handle; 115 using Base::null_dart_handle; 116 using Base::point_of_vertex_attribute; 117 using Base::other_extremity; 118 using Base::darts; 119 120 using Base::are_attributes_automatically_managed; 121 using Base::mark; 122 using Base::is_marked; 123 using Base::unmark; 124 using Base::free_mark; 125 using Base::get_new_mark; 126 using Base::next; 127 using Base::previous; 128 using Base::opposite; 129 using Base::is_next_exist; 130 using Base::is_previous_exist; 131 132 using Base::make_segment; 133 using Base::make_triangle; 134 using Base::make_quadrangle; 135 136 using Base::insert_cell_0_in_cell_1; 137 using Base::insert_cell_0_in_cell_2; 138 using Base::insert_dangling_cell_1_in_cell_2; 139 using Base::insert_cell_1_in_cell_2; 140 using Base::insert_cell_2_in_cell_3; 141 Linear_cell_complex_base()142 Linear_cell_complex_base() : Base() 143 {} 144 145 /** Copy the given linear cell complex into *this. 146 * Note that both LCC can have different dimensions and/or non void attributes. 147 * @param alcc the linear cell complex to copy. 148 * @post *this is valid. 149 */ Linear_cell_complex_base(const Self & alcc)150 Linear_cell_complex_base(const Self& alcc) : Base(alcc) 151 {} 152 153 template <unsigned int d2, unsigned int ambient_dim2, class Traits2, 154 class Items2, class Alloc2, 155 template<unsigned int,class,class,class,class> class CMap2, 156 class Refs2, class Storage2> Linear_cell_complex_base(const Linear_cell_complex_base<d2,ambient_dim2,Traits2,Items2,Alloc2,CMap2,Refs2,Storage2> & alcc)157 Linear_cell_complex_base 158 (const Linear_cell_complex_base<d2, ambient_dim2, 159 Traits2, Items2, Alloc2, CMap2, Refs2, Storage2>& alcc) : Base(alcc) 160 {} 161 162 template <unsigned int d2, unsigned int ambient_dim2, class Traits2, 163 class Items2, class Alloc2, 164 template<unsigned int,class,class,class,class> class CMap2, 165 class Refs2, 166 class Storage2, typename Converters> Linear_cell_complex_base(const Linear_cell_complex_base<d2,ambient_dim2,Traits2,Items2,Alloc2,CMap2,Refs2,Storage2> & alcc,Converters & converters)167 Linear_cell_complex_base 168 (const Linear_cell_complex_base<d2, ambient_dim2, Traits2, Items2, 169 Alloc2, CMap2, Refs2, Storage2>& alcc, Converters& converters) : 170 Base(alcc, converters) 171 {} 172 173 template <unsigned int d2, unsigned int ambient_dim2, class Traits2, 174 class Items2, class Alloc2, 175 template<unsigned int,class,class,class,class> class CMap2, 176 class Refs2, class Storage2, typename Converters, 177 typename DartInfoConverter> Linear_cell_complex_base(const Linear_cell_complex_base<d2,ambient_dim2,Traits2,Items2,Alloc2,CMap2,Refs2,Storage2> & alcc,Converters & converters,const DartInfoConverter & dartinfoconverter)178 Linear_cell_complex_base 179 (const Linear_cell_complex_base<d2, ambient_dim2, Traits2, Items2, 180 Alloc2, CMap2, Refs2, Storage2>& alcc, Converters& converters, 181 const DartInfoConverter& dartinfoconverter) : 182 Base(alcc, converters, dartinfoconverter) 183 {} 184 185 template <unsigned int d2, unsigned int ambient_dim2, class Traits2, 186 class Items2, class Alloc2, 187 template<unsigned int,class,class,class,class> class CMap2, 188 class Refs2, class Storage2, typename Converters, 189 typename DartInfoConverter, typename Pointconverter> Linear_cell_complex_base(const Linear_cell_complex_base<d2,ambient_dim2,Traits2,Items2,Alloc2,CMap2,Refs2,Storage2> & alcc,Converters & converters,const DartInfoConverter & dartinfoconverter,const Pointconverter & pointconverter)190 Linear_cell_complex_base 191 (const Linear_cell_complex_base<d2, ambient_dim2, Traits2, Items2, 192 Alloc2, CMap2, Refs2, Storage2>& alcc, Converters& converters, 193 const DartInfoConverter& dartinfoconverter, 194 const Pointconverter& pointconverter) : 195 Base(alcc, converters, dartinfoconverter, pointconverter) 196 {} 197 198 /** Affectation operation. Copies one map to the other. 199 * @param amap a lcc. 200 * @return A copy of that lcc. 201 */ 202 Self & operator= (const Self & alcc) 203 { 204 if (this!=&alcc) 205 { 206 Self tmp(alcc); 207 this->swap(tmp); 208 } 209 return *this; 210 } 211 212 /** Create a vertex attribute. 213 * @return an handle on the new attribute. 214 */ 215 template<typename ...Args> create_vertex_attribute(const Args &...args)216 Vertex_attribute_handle create_vertex_attribute(const Args&... args) 217 { return Base::template create_attribute<0>(args...); } 218 219 /** 220 * Create a new dart associated with an handle through an attribute. 221 * @param ahandle the point handle to associated with the dart. 222 * @return a Dart_handle on the new dart. 223 */ create_dart(Vertex_attribute_handle ahandle)224 Dart_handle create_dart(Vertex_attribute_handle ahandle) 225 { 226 Dart_handle res = create_dart(); 227 set_vertex_attribute_of_dart(res,ahandle); 228 return res; 229 } 230 231 /** Create a new dart associated with a point. 232 * @param apoint the point to associated with the dart. 233 * @return a Dart_handle on the new dart. 234 */ create_dart(const Point & apoint)235 Dart_handle create_dart(const Point& apoint) 236 { return create_dart(create_vertex_attribute(apoint)); } 237 238 /** Erase a given vertex attribute. 239 * @param ahandle the handle to the vertex attribute to erase. 240 */ erase_vertex_attribute(Vertex_attribute_handle ahandle)241 void erase_vertex_attribute(Vertex_attribute_handle ahandle) 242 { Base::template erase_attribute<0>(ahandle); } 243 244 /** Set the vertex attribute of the given dart. 245 * @param adart a dart. 246 * @param ah the attribute to set. 247 */ set_vertex_attribute_of_dart(Dart_handle adart,Vertex_attribute_handle ah)248 void set_vertex_attribute_of_dart(Dart_handle adart, 249 Vertex_attribute_handle ah) 250 { 251 return CGAL::internal::Set_i_attribute_of_dart_functor<Self, 0>:: 252 run(*this, adart, ah); 253 } 254 255 /** Set the vertex attribute of all the darts of the vertex. 256 * @param adart a dart of the vertex. 257 * @param ah the attribute to set. 258 */ set_vertex_attribute(Dart_handle adart,Vertex_attribute_handle ah)259 void set_vertex_attribute(Dart_handle adart, 260 Vertex_attribute_handle ah) 261 { return CGAL::Set_i_attribute_functor<Self, 0>::run(*this, adart, ah); } 262 263 /// @return the Vertex_attribute_range for all vertex_attributes. vertex_attributes()264 Vertex_attribute_range& vertex_attributes() 265 { return this->template attributes<0>(); } 266 267 /// @return the Vertex_attribute_const_range for all vertex_attributes. vertex_attributes()268 Vertex_attribute_const_range& vertex_attributes() const 269 { return this->template attributes<0>(); } 270 271 /// @return the size of the vertex_attribute container. number_of_vertex_attributes()272 typename Base::size_type number_of_vertex_attributes() const 273 { return Base::template number_of_attributes<0>(); } 274 275 /// Get the vertex_attribute associated with a dart. 276 /// @param a dart 277 /// @return the vertex_attribute. vertex_attribute(Dart_handle adart)278 Vertex_attribute_handle vertex_attribute(Dart_handle adart) 279 { return this->template attribute<0>(adart); } 280 281 /// Get the vertex_attribute associated with a const dart. 282 /// @param a dart 283 /// @return the vertex_const_attribute. 284 Vertex_attribute_const_handle vertex_attribute(Dart_const_handle adart)285 vertex_attribute(Dart_const_handle adart) const 286 { return this->template attribute<0>(adart); } 287 288 /// Get the point associated with a dart. 289 /// @param a dart 290 /// @return the point. point(Dart_handle adart)291 Point& point(Dart_handle adart) 292 { 293 CGAL_assertion(this->template attribute<0>(adart)!=null_handle ); 294 return point_of_vertex_attribute(this->template attribute<0>(adart)); 295 } 296 297 /// Get the point associated with a const dart. 298 /// @param a dart 299 /// @return the point. point(Dart_const_handle adart)300 const Point& point(Dart_const_handle adart) const 301 { 302 CGAL_assertion(this->template attribute<0>(adart)!=null_handle ); 303 return point_of_vertex_attribute(this->template attribute<0>(adart)); 304 } 305 306 /** Test if the lcc is valid. 307 * A Linear_cell_complex is valid if it is a valid Combinatorial_map with 308 * an attribute associated to each dart. 309 * @return true iff the map is valid. 310 */ is_valid()311 bool is_valid() const 312 { 313 bool valid = Base::is_valid(); 314 for (typename Dart_range::const_iterator it(darts().begin()), 315 itend(darts().end()); valid && it != itend; ++it) 316 { 317 if ( vertex_attribute(it)==null_handle ) 318 { 319 std::cerr << "Map not valid: dart "<<&(*it) 320 <<" does not have a vertex."<< std::endl; 321 valid = false; 322 } 323 } 324 return valid; 325 } 326 327 /** validate the lcc 328 */ correct_invalid_attributes()329 void correct_invalid_attributes() 330 { 331 // Copy of the code in Map::correct_invalid_attributes() to avoid 332 // 2 iterations through the darts of the map. 333 334 std::vector<size_type> marks(dimension+1); 335 for ( unsigned int i=0; i<=dimension; ++i) 336 marks[i] = Base::INVALID_MARK; 337 338 Helper::template 339 Foreach_enabled_attributes<Reserve_mark_functor<Self> >:: 340 run(*this, marks); 341 342 for ( typename Dart_range::iterator it(darts().begin()), 343 itend(darts().end()); it!=itend; ++it) 344 { 345 Helper::template Foreach_enabled_attributes 346 <internal::Correct_invalid_attributes_functor<Self> >:: 347 run(*this, it, marks); 348 349 if ( vertex_attribute(it)==null_handle ) 350 { 351 // If a dart don't have a 0-attribute, we create a Point at the origin 352 set_vertex_attribute(it, create_vertex_attribute(CGAL::ORIGIN)); 353 } 354 } 355 356 for ( unsigned int i=0; i<=dimension; ++i) 357 if ( marks[i]!=Base::INVALID_MARK ) 358 { 359 CGAL_assertion( this->is_whole_map_marked(marks[i]) ); 360 free_mark(marks[i]); 361 } 362 363 Helper::template 364 Foreach_enabled_attributes<internal::Cleanup_useless_attributes<Self> >:: 365 run(*this); 366 } 367 368 /** test if the two given facets have the same geometry 369 * @return true iff the two facets have the same geometry. 370 */ are_facets_same_geometry(Dart_const_handle d1,Dart_const_handle d2)371 bool are_facets_same_geometry(Dart_const_handle d1, 372 Dart_const_handle d2) const 373 { 374 Dart_const_handle s1=d1; 375 Dart_const_handle s2=d2; 376 while (is_previous_exist(d1) && previous(s1)!=d1) 377 { 378 s1=previous(s1); 379 if (!is_previous_exist(d2)) return false; 380 s2=previous(s2); 381 } 382 383 d1=s1; 384 d2=s2; 385 do 386 { 387 if (is_next_exist(d1)!=is_next_exist(d2)) 388 return false; 389 390 if (point(d1)!=point(d2)) 391 return false; 392 393 d1=next(d1); 394 d2=next(d2); 395 } 396 while(is_next_exist(d1) && d1!=s1); 397 398 if (is_next_exist(d1)!=is_next_exist(d2)) 399 return false; 400 401 if (d1==s1 && d2!=s2) return false; 402 403 return true; 404 } 405 406 /** test if the two given facets have the same geometry but with 407 * opposite orientations. 408 * @return true iff the two facets have the same geometry with opposite 409 * orientation. 410 */ are_facets_opposite_and_same_geometry(Dart_const_handle d1,Dart_const_handle d2)411 bool are_facets_opposite_and_same_geometry(Dart_const_handle d1, 412 Dart_const_handle d2) const 413 { 414 Dart_const_handle s1=d1; 415 Dart_const_handle s2=d2; 416 while (is_previous_exist(d1) && previous(s1)!=d1) 417 { 418 s1=previous(s1); 419 if (!is_next_exist(d2)) return false; 420 s2=next(s2); 421 } 422 423 d1=s1; 424 d2=s2; 425 do 426 { 427 if (is_next_exist(d1)!=is_previous_exist(d2)) 428 return false; 429 430 if (other_extremity(d2)!=null_handle && 431 point(d1)!=point(other_extremity(d2))) 432 return false; 433 434 // The only case where d2 could have no other_extremity 435 // is the end of an open path. In this case d1 is the 436 // beginning of an open path and we do not compare points 437 // but this is the correct thing to do. 438 439 d1=next(d1); 440 d2=previous(d2); 441 } 442 while(is_next_exist(d1) && d1!=s1); 443 444 if (is_next_exist(d1)!=is_previous_exist(d2)) 445 return false; 446 447 if (d1==s1 && d2!=s2) return false; 448 449 return true; 450 } 451 452 /// Sew3 the marked facets having same geometry 453 /// (a facet is considered marked if one of its dart is marked). sew3_same_facets(size_type AMark)454 unsigned int sew3_same_facets(size_type AMark) 455 { 456 unsigned int res = 0; 457 458 std::map<Point, std::vector<Dart_handle> > one_dart_per_facet; 459 size_type mymark = get_new_mark(); 460 461 // First we fill the std::map by one dart per facet, and by using 462 // the minimal point as index. 463 for (typename Dart_range::iterator it(darts().begin()), 464 itend(darts().end()); it!=itend; ++it ) 465 { 466 if ( !is_marked(it, mymark) && is_marked(it, AMark) ) 467 { 468 Point min_point=point(it); 469 Dart_handle min_dart = it; 470 mark(it, mymark); 471 typename Base::template 472 Dart_of_cell_range<2>::iterator it2(*this,it); 473 ++it2; 474 for ( ; it2.cont(); ++it2 ) 475 { 476 Point cur_point=point(it2); 477 this->mark(it2, mymark); 478 if ( cur_point < min_point ) 479 { 480 min_point = cur_point; 481 min_dart = it2; 482 } 483 } 484 one_dart_per_facet[min_point].push_back(min_dart); 485 } 486 else 487 this->mark(it, mymark); 488 } 489 490 // Second we run through the map: candidates for sew3 have necessary the 491 // same minimal point. 492 typename std::map<Point, std::vector<Dart_handle> >::iterator 493 itmap=one_dart_per_facet.begin(), 494 itmapend=one_dart_per_facet.end(); 495 496 for (; itmap!=itmapend; ++itmap) 497 { 498 for (typename std::vector<Dart_handle>::iterator 499 it1=(itmap->second).begin(), 500 it1end=(itmap->second).end(); it1!=it1end; ++it1) 501 { 502 typename std::vector<Dart_handle>::iterator it2=it1; 503 for (++it2; it2!=it1end; ++it2) 504 { 505 if (*it1!=*it2 && 506 !this->template is_opposite_exist<3>(*it1) && 507 !this->template is_opposite_exist<3>(*it2) && 508 are_facets_opposite_and_same_geometry 509 (*it1, this->previous(*it2))) 510 { 511 ++res; 512 this->template sew<3>(*it1, 513 this->other_orientation(previous(*it2))); 514 } 515 } 516 } 517 } 518 519 CGAL_assertion( this->is_whole_map_marked(mymark) ); 520 this->free_mark(mymark); 521 return res; 522 } 523 524 /// Sew3 the facets having same geometry 525 /// (all the facets of the map are considered) sew3_same_facets()526 unsigned int sew3_same_facets() 527 { 528 size_type mark = this->get_new_mark(); 529 this->negate_mark(mark); 530 unsigned int res=sew3_same_facets(mark); 531 this->free_mark(mark); 532 return res; 533 } 534 535 /** Create a segment given 2 points. 536 * @param p0 the first point. 537 * @param p1 the second point. 538 * if closed==true, the edge has no 2-free dart. 539 * @return the dart of the new segment incident to p0. 540 */ 541 Dart_handle make_segment(const Point& p0,const Point& p1, 542 bool closed=false) 543 { 544 return make_segment(create_vertex_attribute(p0), 545 create_vertex_attribute(p1), 546 closed); 547 } 548 549 /** Create a triangle given 3 points. 550 * @param p0 the first point. 551 * @param p1 the second point. 552 * @param p2 the third point. 553 * @return the dart of the new triangle incident to p0 and edge p0p1. 554 */ make_triangle(const Point & p0,const Point & p1,const Point & p2)555 Dart_handle make_triangle(const Point& p0, 556 const Point& p1, 557 const Point& p2) 558 { 559 return make_triangle(create_vertex_attribute(p0), 560 create_vertex_attribute(p1), 561 create_vertex_attribute(p2)); 562 } 563 564 /** Create a quadrangle given 4 points. 565 * @param p0 the first point. 566 * @param p1 the second point. 567 * @param p2 the third point. 568 * @param p3 the fourth point. 569 * @return the dart of the new quadrangle incident to p0 and edge p0p1. 570 */ make_quadrangle(const Point & p0,const Point & p1,const Point & p2,const Point & p3)571 Dart_handle make_quadrangle(const Point& p0, 572 const Point& p1, 573 const Point& p2, 574 const Point& p3) 575 { 576 return make_quadrangle(create_vertex_attribute(p0), 577 create_vertex_attribute(p1), 578 create_vertex_attribute(p2), 579 create_vertex_attribute(p3)); 580 } 581 582 583 /** Create a tetrahedron given 4 Vertex_attribute_handle. 584 * @param h0 the first vertex handle. 585 * @param h1 the second vertex handle. 586 * @param h2 the third vertex handle. 587 * @param h3 the fourth vertex handle. 588 * @return the dart of the new tetrahedron incident to h0, to edge 589 * h0,h1 and to facet h0,h1,h2. 590 */ make_tetrahedron(Vertex_attribute_handle h0,Vertex_attribute_handle h1,Vertex_attribute_handle h2,Vertex_attribute_handle h3)591 Dart_handle make_tetrahedron(Vertex_attribute_handle h0, 592 Vertex_attribute_handle h1, 593 Vertex_attribute_handle h2, 594 Vertex_attribute_handle h3) 595 { 596 Dart_handle d1 = make_triangle(h0, h1, h2); 597 Dart_handle d2 = make_triangle(h1, h0, h3); 598 Dart_handle d3 = make_triangle(h1, h3, h2); 599 Dart_handle d4 = make_triangle(h3, h0, h2); 600 601 return this->make_combinatorial_tetrahedron(d1, d2, d3, d4); 602 } 603 604 /** Create a tetrahedron given 4 points. 605 * @param p0 the first point. 606 * @param p1 the second point. 607 * @param p2 the third point. 608 * @param p3 the fourth point. 609 * @return the dart of the new tetrahedron incident to p0, to edge 610 * p0,p1 and to facet p0,p1,p2. 611 */ make_tetrahedron(const Point & p0,const Point & p1,const Point & p2,const Point & p3)612 Dart_handle make_tetrahedron(const Point& p0, 613 const Point& p1, 614 const Point& p2, 615 const Point& p3) 616 { 617 return make_tetrahedron(create_vertex_attribute(p0), 618 create_vertex_attribute(p1), 619 create_vertex_attribute(p2), 620 create_vertex_attribute(p3)); 621 } 622 623 /** Create an hexahedron given 8 Vertex_attribute_handle. 624 * (8 vertices, 12 edges and 6 facets) 625 * \verbatim 626 * 4----7 627 * /| /| 628 * 5----6 | 629 * | 3--|-2 630 * |/ |/ 631 * 0----1 632 * \endverbatim 633 * @param h0 the first vertex handle. 634 * @param h1 the second vertex handle. 635 * @param h2 the third vertex handle. 636 * @param h3 the fourth vertex handle. 637 * @param h4 the fifth vertex handle. 638 * @param h5 the sixth vertex handle. 639 * @param h6 the seventh vertex handle. 640 * @param h7 the height vertex handle. 641 * @return the dart of the new hexahedron incident to h0, to edge 642 * h0,h5 and to the facet (h0,h5,h6,h1). 643 */ make_hexahedron(Vertex_attribute_handle h0,Vertex_attribute_handle h1,Vertex_attribute_handle h2,Vertex_attribute_handle h3,Vertex_attribute_handle h4,Vertex_attribute_handle h5,Vertex_attribute_handle h6,Vertex_attribute_handle h7)644 Dart_handle make_hexahedron(Vertex_attribute_handle h0, 645 Vertex_attribute_handle h1, 646 Vertex_attribute_handle h2, 647 Vertex_attribute_handle h3, 648 Vertex_attribute_handle h4, 649 Vertex_attribute_handle h5, 650 Vertex_attribute_handle h6, 651 Vertex_attribute_handle h7) 652 { 653 Dart_handle d1 = make_quadrangle(h0, h5, h6, h1); 654 Dart_handle d2 = make_quadrangle(h1, h6, h7, h2); 655 Dart_handle d3 = make_quadrangle(h2, h7, h4, h3); 656 Dart_handle d4 = make_quadrangle(h3, h4, h5, h0); 657 Dart_handle d5 = make_quadrangle(h0, h1, h2, h3); 658 Dart_handle d6 = make_quadrangle(h5, h4, h7, h6); 659 660 return this->make_combinatorial_hexahedron(d1, d2, d3, d4, d5, d6); 661 } 662 663 /** Create an hexahedron given 8 points. 664 * \verbatim 665 * 4----7 666 * /| /| 667 * 5----6 | 668 * | 3--|-2 669 * |/ |/ 670 * 0----1 671 * \endverbatim 672 * @param p0 the first point. 673 * @param p1 the second point. 674 * @param p2 the third point. 675 * @param p3 the fourth point. 676 * @param p4 the fifth point. 677 * @param p5 the sixth point. 678 * @param p6 the seventh point. 679 * @param p7 the height point. 680 * @return the dart of the new hexahedron incident to p0, to edge 681 * p0,p5 and to the facet (p0,p5,p6,p1). 682 */ make_hexahedron(const Point & p0,const Point & p1,const Point & p2,const Point & p3,const Point & p4,const Point & p5,const Point & p6,const Point & p7)683 Dart_handle make_hexahedron(const Point& p0, 684 const Point& p1, 685 const Point& p2, 686 const Point& p3, 687 const Point& p4, 688 const Point& p5, 689 const Point& p6, 690 const Point& p7) 691 { 692 return make_hexahedron(create_vertex_attribute(p0), 693 create_vertex_attribute(p1), 694 create_vertex_attribute(p2), 695 create_vertex_attribute(p3), 696 create_vertex_attribute(p4), 697 create_vertex_attribute(p5), 698 create_vertex_attribute(p6), 699 create_vertex_attribute(p7)); 700 } 701 702 /** Compute the barycenter of a given cell. 703 * @param adart a dart incident to the cell. 704 * @param adim the dimension of the cell. 705 * @return the barycenter of the cell. 706 */ 707 template<unsigned int i> barycenter(Dart_const_handle adart)708 Point barycenter(Dart_const_handle adart) const 709 { 710 return CGAL::Barycenter_functor<Self, i>::run(*this, adart); 711 } 712 713 /** Insert a point in a given 1-cell. 714 * @param dh a dart handle to the 1-cell 715 * @param p the point to insert 716 * @param update_attributes a boolean to update the enabled attributes 717 * @return a dart handle to the new vertex containing p. 718 */ 719 Dart_handle insert_point_in_cell_1(Dart_handle dh, const Point& p, 720 bool update_attributes=true) 721 { 722 return this->insert_cell_0_in_cell_1(dh, 723 create_vertex_attribute(p), 724 update_attributes); 725 } 726 727 /** Insert a point in a given 2-cell. 728 * @param dh a dart handle to the 2-cell 729 * @param p the point to insert 730 * @param update_attributes a boolean to update the enabled attributes 731 * @return a dart handle to the new vertex containing p. 732 */ 733 Dart_handle insert_point_in_cell_2(Dart_handle dh, const Point& p, 734 bool update_attributes=true) 735 { 736 Vertex_attribute_handle v = create_vertex_attribute(p); 737 738 Dart_handle first = this->insert_cell_0_in_cell_2(dh, v, update_attributes); 739 740 if ( first==null_handle ) // If the triangulated facet was made of one dart 741 erase_vertex_attribute(v); 742 743 #ifdef CGAL_CMAP_TEST_VALID_INSERTIONS 744 CGAL_assertion( is_valid() ); 745 #endif 746 747 return first; 748 } 749 750 /** Insert a point in a given i-cell. 751 * @param dh a dart handle to the i-cell 752 * @param p the point to insert 753 * @param update_attributes a boolean to update the enabled attributes 754 * @return a dart handle to the new vertex containing p. 755 */ 756 template <unsigned int i> 757 Dart_handle insert_point_in_cell(Dart_handle dh, const Point& p, 758 bool update_attributes=true) 759 { 760 CGAL_static_assertion(1<=i && i<=2); 761 if (i==1) return insert_point_in_cell_1(dh, p, update_attributes); 762 return insert_point_in_cell_2(dh, p, update_attributes); 763 } 764 765 /** Insert a dangling edge in a given facet. 766 * @param dh a dart of the facet (!=nullptr). 767 * @param p the coordinates of the new vertex. 768 * @param update_attributes a boolean to update the enabled attributes 769 * @return a dart of the new edge, incident to the new vertex. 770 */ 771 Dart_handle insert_dangling_cell_1_in_cell_2(Dart_handle dh, 772 const Point& p, 773 bool update_attributes=true) 774 { 775 return this->insert_dangling_cell_1_in_cell_2 776 (dh, create_vertex_attribute(p), update_attributes); 777 } 778 779 /** Insert a point in a given i-cell. 780 * @param dh a dart handle to the i-cell 781 * @param p the point to insert 782 * @param update_attributes a boolean to update the enabled attributes 783 * @return a dart handle to the new vertex containing p. 784 */ 785 template <unsigned int i> 786 Dart_handle insert_barycenter_in_cell(Dart_handle dh, bool update_attributes=true) 787 { return insert_point_in_cell<i>(dh, barycenter<i>(dh), update_attributes); } 788 789 /** Compute the dual of a Linear_cell_complex. 790 * @param alcc the lcc in which we build the dual of this lcc. 791 * @param adart a dart of the initial lcc, nullptr by default. 792 * @return adart of the dual lcc, the dual of adart if adart!=nullptr, 793 * any dart otherwise. 794 * As soon as we don't modify this lcc and alcc lcc, we can iterate 795 * simultaneously through all the darts of the two lcc and we have 796 * each time of the iteration two "dual" darts. 797 */ 798 Dart_handle dual_points_at_barycenter(Self & alcc, Dart_handle adart=null_handle) 799 { 800 Dart_handle res = Base::dual(alcc, adart); 801 802 // Now the lcc alcc is topologically correct, we just need to add 803 // its geometry to each vertex (the barycenter of the corresponding 804 // dim-cell in the initial map). 805 typename Dart_range::iterator it2 = alcc.darts().begin(); 806 for (typename Dart_range::iterator it(darts().begin()); 807 it!=darts().end(); ++it, ++it2) 808 { 809 if (vertex_attribute(it2)==null_handle) 810 { 811 alcc.set_vertex_attribute(it2, alcc.create_vertex_attribute 812 (barycenter<dimension>(it))); 813 } 814 } 815 816 return res; 817 } 818 819 /** Set the status of the managment of the attributes of the Map 820 */ set_update_attributes(bool newval)821 void set_update_attributes(bool newval) 822 { 823 if (this->automatic_attributes_management == false && newval == true) 824 { 825 // We need to recode this function because correct_invalid_attributes 826 // is not a virtual function. 827 correct_invalid_attributes(); 828 } 829 830 this->automatic_attributes_management = newval; 831 } 832 }; 833 834 } // namespace CGAL 835 836 #endif // CGAL_LINEAR_CELL_COMPLEX_BASE_H // 837 // EOF // 838