// Copyright (c) 2003-2007 INRIA Sophia-Antipolis (France). // All rights reserved. // // This file is part of CGAL (www.cgal.org). // // $URL: https://github.com/CGAL/cgal/blob/v5.2/Surface_mesher/include/CGAL/Complex_2_in_triangulation_3.h $ // $Id: Complex_2_in_triangulation_3.h 0779373 2020-03-26T13:31:46+01:00 Sébastien Loriot // SPDX-License-Identifier: GPL-3.0-or-later OR LicenseRef-Commercial // // // Author(s) : Steve Oudot, David Rey, Mariette Yvinec, Laurent Rineau, Andreas Fabri #ifndef CGAL_COMPLEX_2_IN_TRIANGULATION_3_H #define CGAL_COMPLEX_2_IN_TRIANGULATION_3_H #include #include // TODO: add the iterators // TODO: document the output/input function of C2T3? #include #include #include #include #include #include #include namespace CGAL { namespace details { template class C2t3_helper_class { protected: typedef typename Tr::Vertex_handle Vertex_handle; typedef std::pair Pair_of_vertices; // computes and return an ordered pair of Vertex Pair_of_vertices make_ordered_pair(const Vertex_handle vh1, const Vertex_handle vh2) const { if (vh1 < vh2) { return std::make_pair(vh1, vh2); } else { return std::make_pair(vh2, vh1); } } }; template class C2t3_mark_edges_helper_class : public C2t3_helper_class { protected: typedef typename Tr::Vertex_handle Vertex_handle; typedef typename Tr::Cell_handle Cell_handle; typedef typename Tr::Edge Edge; typedef typename C2t3_helper_class::Pair_of_vertices Pair_of_vertices; typedef std::map Marked_edges; Marked_edges marked_edges; public: void mark(const Cell_handle& c, const int& i, const int& j, const Edge_info& info = Edge_info()) { marked_edges.insert(std::make_pair(this->make_ordered_pair(c->vertex(i), c->vertex(j)), info)); } void mark(const Edge& e, const Edge_info& info = Edge_info()) { mark(e.first, e.second, e.third, info); } bool unmark(const Cell_handle& c, const int& i, const int& j) { return marked_edges.erase(this->make_ordered_pair(c->vertex(i), c->vertex(j))) > 0; } bool unmark(const Edge& e) { return unmark(e.first, e.second, e.third); } Edge_info& get_info(const Edge& e) { return get_info(e.first, e.second, e.third); } Edge_info& get_info(const Cell_handle& c, const int& i, const int& j) { return this->marked_edges[this->make_ordered_pair(c->vertex(i), c->vertex(j))]; } }; // end of class C2t3_mark_edges_helper_class template class C2t3_mark_edges_helper_class : public C2t3_helper_class { protected: typedef typename Tr::Vertex_handle Vertex_handle; typedef typename Tr::Cell_handle Cell_handle; typedef typename Tr::Edge Edge; typedef typename C2t3_helper_class::Pair_of_vertices Pair_of_vertices; typedef std::set Marked_edges; Marked_edges marked_edges; public: void mark(const Cell_handle& c, const int& i, const int& j) { marked_edges.insert(this->make_ordered_pair(c->vertex(i), c->vertex(j))); } void mark(const Edge& e) { mark(e.first, e.second, e.third); } bool unmark(const Cell_handle& c, const int& i, const int& j) { return marked_edges.erase(this->make_ordered_pair(c->vertex(i), c->vertex(j))) > 0; } bool unmark(const Edge& e) { return unmark(e.first, e.second, e.third); } }; // end of specialiazation C2t3_mark_edges_helper_class } // end nested-namespace details (in CGAL::) namespace Surface_mesher { template < class Tr> typename Tr::size_type number_of_facets_on_surface(const Tr& T) { typename Tr::size_type result=0; for (typename Tr::Finite_facets_iterator fit = T.finite_facets_begin(); fit != T.finite_facets_end(); ++fit) if (fit->first->is_facet_on_surface (fit->second)) ++result; return result; } } // end nested-namespace Surface_mesher (in CGAL) template < class Tr, typename Edge_info_ = void > class Complex_2_in_triangulation_3 : public details::C2t3_mark_edges_helper_class { public: typedef Complex_2_in_triangulation_3 Self; typedef details::C2t3_mark_edges_helper_class Base; typedef typename Base::Marked_edges Marked_edges; typedef Tr Triangulation; typedef Edge_info_ Edge_info; typedef typename Triangulation::Vertex_handle Vertex_handle; typedef typename Triangulation::Cell_handle Cell_handle; typedef typename Triangulation::Facet Facet; typedef typename Triangulation::Edge Edge; typedef std::set Facets; typedef std::size_t size_type; typedef Const_circulator_from_container Facet_circulator; typedef typename Base::Pair_of_vertices Pair_of_vertices; typedef std::map > Edge_facet_counter; enum Face_status{ NOT_IN_COMPLEX = 0, ISOLATED = 1, // - An ISOLATED edge is a marked edge, // without any incident facets. BOUNDARY, // - An edge is on BOUNDARY if it has only // one incident facet. // - A vertex is on BOUNDARY if all its // incident edges are REGULAR or on // BOUNDARY, at least one is on // BOUNDARY, and the incident facets // form only one connected component. REGULAR, // - A facet that is in the complex is // REGULAR. // - An edge is REGULAR if it has // exactly two incident facets. // - A vertex is REGULAR if all it // incident edges are REGULAR, and the // incident facets form only one // connected component. SINGULAR}; // - SINGULAR is for all other cases. class Iterator_not_in_complex { const Self* self; public: Iterator_not_in_complex(const Self* self = 0) : self(self) { } template // Facet or Edges iterators bool operator()(Iterator it) const { if(self) return ! self->is_in_complex(*it); else return true; } }; // end struct Iterator_not_in_complex class Vertex_not_in_complex { Self* self; public: Vertex_not_in_complex(){} //added for SWIG wrapping Vertex_not_in_complex(Self* self) : self(self) { } bool operator()(Vertex_handle v) const { // Takes as argument an iterator to a // Vertex, convertible to Vertex_handle. return ! self->is_in_complex(v); } }; // end struct Vertex_not_in_complex class Facet_not_in_complex { Self* self; public: Facet_not_in_complex(Self* self) : self(self) { } bool operator()(Facet f) const { return ! self->is_in_complex(f); } }; // end struct Facet_not_in_complex class Iterator_not_on_boundary { Self* self; public: Iterator_not_on_boundary(){} //added for SWIG wrapping Iterator_not_on_boundary(Self* self) : self(self) { } template bool operator()(Edge_iterator eit) const { return self->face_status(*eit)!= BOUNDARY; } }; typedef Filter_iterator Facet_iterator; typedef Filter_iterator Edge_iterator; // class to ensure that Vertex_iterator is convertible to Vertex_handle class Vertex_iterator : public Filter_iterator { typedef typename Triangulation::Finite_vertices_iterator Tr_iterator; typedef Filter_iterator Base; typedef typename Base::Predicate Predicate; typedef Vertex_iterator Self; public: Vertex_iterator(){} //added for SWIG wrapping Vertex_iterator(Base i) : Base(i) { } Self & operator++() { Base::operator++(); return *this; } Self & operator--() { Base::operator--(); return *this; } Self operator++(int) { Self tmp(*this); ++(*this); return tmp; } Self operator--(int) { Self tmp(*this); --(*this); return tmp; } operator Vertex_handle() const // const added for SWIG wrapping { return Vertex_handle(this->base()); } }; typedef Filter_iterator Boundary_edges_iterator; protected: Triangulation& tr; Edge_facet_counter edge_facet_counter; size_type m_number_of_facets; public: Facet canonical_facet(Cell_handle c, int i) const { Cell_handle c2 = c->neighbor(i); return (c2 < c) ? std::make_pair(c2,c2->index(c)) : std::make_pair(c,i); } Facet opposite_facet(Facet f) const { Cell_handle c2 = f.first->neighbor(f.second); return std::make_pair(c2,c2->index(f.first)); } public: // Constructors Complex_2_in_triangulation_3 (Triangulation& t) : tr(t), m_number_of_facets(0) { } void clear() { m_number_of_facets = 0; edge_facet_counter.clear(); this->marked_edges.clear(); } // Access functions Triangulation& triangulation() { return tr; } const Triangulation& triangulation() const { return tr; } Face_status face_status (const Facet& f) const { return face_status (f.first, f.second); } Face_status face_status (const Cell_handle c, const int i) const { return (c->is_facet_on_surface(i)) ? REGULAR : NOT_IN_COMPLEX; } Face_status face_status (const Edge& e) const { return face_status(e.first->vertex(e.second), e.first->vertex(e.third)); } Face_status face_status (const Cell_handle c, const int i, const int j) const { return face_status(c->vertex(i), c->vertex(j)); } Face_status face_status (const Vertex_handle& va, const Vertex_handle& vb) const { typename Edge_facet_counter::const_iterator it = edge_facet_counter.find(this->make_ordered_pair(va, vb)); if (it == edge_facet_counter.end()) { if(is_marked(va, vb)) return ISOLATED; else return NOT_IN_COMPLEX; } switch (it->second.first) { case 0 : return ISOLATED; case 1 : return BOUNDARY; case 2 : return REGULAR; default : return SINGULAR; } } // end face_status(const Vertex_handle&, const Vertex_handle&) Face_status face_status (const Vertex_handle& v) { if(v->is_c2t3_cache_valid() && v->cached_number_of_incident_facets() == 0) return NOT_IN_COMPLEX; //test incident edges for REGULARITY and count BOUNDARY edges typename std::vector vertices; vertices.reserve(64); tr.incident_vertices(v, std::back_inserter(vertices)); int number_of_boundary_incident_edges = 0; //COULD BE a bool for (typename std::vector::iterator vit=vertices.begin(); vit != vertices.end(); vit++ ) { switch( face_status(v, *vit) ) { case NOT_IN_COMPLEX: case REGULAR: break; case BOUNDARY: ++number_of_boundary_incident_edges; break; default : return SINGULAR; } } // from now on incident edges (in complex) are REGULAR or BOUNDARY int nb_incident_facets, nb_components; union_find_of_incident_facets(v, nb_incident_facets, nb_components); if ( nb_incident_facets == 0 ) return NOT_IN_COMPLEX; else if ( nb_components > 1 ) return SINGULAR; else // REGULAR OR BOUNDARY { if (number_of_boundary_incident_edges != 0) return BOUNDARY; else return REGULAR; } } //end of face_status(Vertex_handle) bool is_marked(const Vertex_handle& va, const Vertex_handle& vb) const { typename Marked_edges::const_iterator it = this->marked_edges.find(this->make_ordered_pair(va, vb)); return it != this->marked_edges.end(); } bool is_marked(const Cell_handle& c, const int& i, const int& j) const { return is_marked(c->vertex(i),c->vertex(j)); } bool is_marked(const Edge& e) const { return is_marked(e.first, e.second, e.third); } // This function should be called only when incident edges // are known to be REGULAR OR BOUNDARY bool is_regular_or_boundary_for_vertices(Vertex_handle v) { int i,j; union_find_of_incident_facets(v,i,j); return (j == 1); } bool is_in_complex (Vertex_handle v) { int i,j; union_find_of_incident_facets(v,i,j); return ( i != 0); } // extract the subset F of facets of the complex incident to v // set i to the number of facets in F // set j to the number of connected component of the adjacency graph // of F void union_find_of_incident_facets(const Vertex_handle v, int& i, int& j) { if( v->is_c2t3_cache_valid() ) { i = v->cached_number_of_incident_facets(); j = v->cached_number_of_components(); return; } Union_find facets; incident_facets(v, std::back_inserter(facets)); typedef std::map::handle> Vertex_Set_map; typedef typename Vertex_Set_map::iterator Vertex_Set_map_iterator; Vertex_Set_map vsmap; for(typename Union_find::iterator it = facets.begin(); it != facets.end(); ++it){ const Cell_handle& ch = (*it).first; const int& i = (*it).second; for(int j=0; j < 3; ++j){ const Vertex_handle w = ch->vertex(tr.vertex_triple_index(i,j)); if(w != v){ Vertex_Set_map_iterator vsm_it = vsmap.find(w); if(vsm_it != vsmap.end()){ facets.unify_sets(vsm_it->second, it); } else { vsmap.insert(std::make_pair(w, it)); } } } } i = static_cast(facets.size()); // we cast as it cannot be too many j = static_cast(facets.number_of_sets()); v->set_c2t3_cache(i, j); return; } bool is_in_complex (const Facet& f) const { return is_in_complex (f.first, f.second); } bool is_in_complex (const Cell_handle c, const int i) const { return face_status(c,i) != NOT_IN_COMPLEX; } bool is_in_complex (const Cell_handle& c,const int i, const int j) const { return face_status(c,i,j) != NOT_IN_COMPLEX; } bool is_in_complex (const Edge& e) const { return face_status(e) != NOT_IN_COMPLEX; } size_type number_of_facets() const { return m_number_of_facets; } size_type number_of_edges() const { return edge_facet_counter.size(); } size_type number_of_marked_edges() const { return this->marked_edges.size(); } Facet_circulator incident_facets (const Edge& e) { typename Edge_facet_counter::iterator it = edge_facet_counter.find(this->make_ordered_pair(e.first->vertex(e.second), e.first->vertex(e.third))); if( it == edge_facet_counter.end() ) return Facet_circulator(); else { // position the circulator on the first element of the facets set Facets& lof = it->second.second; return Facet_circulator(&lof); } } /** @TODO: document this class in the SurfaceMeshComplex_2InTriangulation_3 concept. */ template OutputIterator incident_facets(const Vertex_handle v, OutputIterator it) { // TODO: review this function (Laurent Rineau) // We assume that for the generated facets the Cell_handle is smaller than the opposite one tr.incident_facets(v, CGAL::filter_output_iterator(it, Facet_not_in_complex(this))); return it; } /** This function assumes that the edge is regular. */ Facet neighbor(Cell_handle ch, int index, int j) const { const int i1 = tr.vertex_triple_index(index, tr. cw(j)); const int i2 = tr.vertex_triple_index(index, tr.ccw(j)); Edge edge = Edge(ch, i1, i2); CGAL_assertion(face_status(edge) == REGULAR); typename Tr::Facet_circulator facet_circ = tr.incident_facets(edge, ch,index); do { ++facet_circ; } while(! is_in_complex(*facet_circ) ); return opposite_facet(*facet_circ); } /** This function assumes that the edge is regular. */ Facet neighbor(Facet f, int j) const { return neighbor(f.first,f.second,j); } // Setting functions void add_to_complex (const Facet& f) { add_to_complex (f.first, f.second); } void add_to_complex (const Cell_handle c, const int i) { change_in_complex_status(c, i); } // backward compatibility with implementation of CGAL-3.2 void set_in_complex (const Facet& f) { add_to_complex(f); } // backward compatibility with implementation of CGAL-3.2 void set_in_complex (const Cell_handle c, const int i) { add_to_complex(c, i); } template void change_in_complex_status(const Cell_handle c, const int i) { // if not already in the complex if ( force_modification || (in_complex ? face_status (c, i) == NOT_IN_COMPLEX : face_status (c, i) != NOT_IN_COMPLEX) ) { if(in_complex) ++m_number_of_facets; else --m_number_of_facets; const Facet f = canonical_facet(c, i); c->set_facet_on_surface(i, in_complex); switch( tr.dimension() ) { case 3: { const Cell_handle& c2 = c->neighbor(i); const int& i2 = c2->index(c); c2->set_facet_on_surface(i2, in_complex); } break; case 2: break; default: CGAL_error(); } const int dimension_plus_1 = tr.dimension() + 1; // update c2t3 for edges of f // We consider only pairs made by vertices without i for (int j = 0; j < dimension_plus_1; j++) { for (int k = j + 1; k < dimension_plus_1; k++) { if ( (i != j) && (i != k) ){ const Pair_of_vertices e = this->make_ordered_pair(c->vertex(j), c->vertex(k)); if(in_complex) { ++(edge_facet_counter[e].first); edge_facet_counter[e].second.insert(f); // @TODO: beurk. // Recode this! } else { typename Edge_facet_counter::iterator it = edge_facet_counter.find(e); CGAL_assertion( it != edge_facet_counter.end() ); it->second.second.erase(f); --(it->second.first); CGAL_assertion(it->second.first >= 0); if(it->second.first == 0) { // if the edge is marked, leave it ISOLATED. if(!is_marked(e.first, e.second)) edge_facet_counter.erase(it); } } } } } // update c2t3 for vertices of f for (int j = 0; j < dimension_plus_1; j++) { if (j != i) c->vertex(j)->invalidate_c2t3_cache(); } } } void remove_from_complex (const Facet& f) { remove_from_complex (f.first, f.second); } void remove_from_complex (const Cell_handle c, const int i) { change_in_complex_status(c, i); } Facet_iterator facets_begin() const { return CGAL::filter_iterator(tr.finite_facets_end(), Iterator_not_in_complex(this), tr.finite_facets_begin()); } Facet_iterator facets_end() const { return CGAL::filter_iterator(tr.finite_facets_end(), Iterator_not_in_complex(this)); } Edge_iterator edges_begin(){ return CGAL::filter_iterator(tr.finite_edges_end(), Iterator_not_in_complex(this), tr.finite_edges_begin()); } Edge_iterator edges_end(){ return CGAL::filter_iterator(tr.finite_edges_end(), Iterator_not_in_complex(this)); } Vertex_iterator vertices_begin(){ return CGAL::filter_iterator(tr.finite_vertices_end(), Vertex_not_in_complex(this), tr.finite_vertices_begin()); } Vertex_iterator vertices_end(){ return CGAL::filter_iterator(tr.finite_vertices_end(), Vertex_not_in_complex(this)); } Boundary_edges_iterator boundary_edges_begin() { return CGAL::filter_iterator(tr.finite_edges_end(), Iterator_not_on_boundary(this), tr.finite_edges_begin()); } Boundary_edges_iterator boundary_edges_end() { return CGAL::filter_iterator(tr.finite_edges_end(), Iterator_not_on_boundary(this)); } bool is_valid(bool verbose = false) { const typename Tr::size_type nb = number_of_facets_on_surface(tr); if(number_of_facets() != nb) { if(verbose) { std::cerr << boost::format("C2t3: Invalid number of facet: %1% (should be %2%)!\n") % number_of_facets() % nb; } return false; } for(Facet_iterator it = facets_begin(), end = facets_end(); it != end; ++it) { CGAL_assertion(it->first->is_facet_on_surface(it->second)); const Facet& f = tr.mirror_facet(*it); if(!f.first->is_facet_on_surface(f.second)) { if(verbose) { std::cerr << boost::format("C2t3: facet (%1%, %2%) is marked on surface" "will its mirror facet (%3, %4) is not!\n") % &*it->first % it->second % &*f.first % f.second; } return false; } } return true; } #ifdef CGAL_MESH_3_IO_H static std::string io_signature() { return Get_io_signature()(); } #endif }; // end Complex_2_in_triangulation_3 template < class Tr, typename Edge_info> std::istream & operator>> (std::istream& is, Complex_2_in_triangulation_3& c2t3) { c2t3.clear(); is >> c2t3.triangulation(); // restore datas of c2t3 for(typename Tr::Finite_facets_iterator fit = c2t3.triangulation().finite_facets_begin(); fit != c2t3.triangulation().finite_facets_end(); ++fit) if(fit->first->is_facet_on_surface(fit->second)) c2t3.template change_in_complex_status(fit->first, fit->second); return is; } template < class Tr, typename Edge_info> std::ostream & operator<< (std::ostream& os, const Complex_2_in_triangulation_3 &c2t3) { return os << c2t3.triangulation(); } } // end namespace CGAL #include #endif // CGAL_COMPLEX_2_IN_TRIANGULATION_3_H