diff options
Diffstat (limited to 'include/gudhi_patches/CGAL/Triangulation_data_structure.h')
| -rw-r--r-- | include/gudhi_patches/CGAL/Triangulation_data_structure.h | 1603 |
1 files changed, 1603 insertions, 0 deletions
diff --git a/include/gudhi_patches/CGAL/Triangulation_data_structure.h b/include/gudhi_patches/CGAL/Triangulation_data_structure.h new file mode 100644 index 00000000..2493c712 --- /dev/null +++ b/include/gudhi_patches/CGAL/Triangulation_data_structure.h @@ -0,0 +1,1603 @@ +// Copyright (c) 2009-2014 INRIA Sophia-Antipolis (France). +// All rights reserved. +// +// This file is part of CGAL (www.cgal.org). +// You can redistribute it and/or modify it under the terms of the GNU +// General Public License as published by the Free Software Foundation, +// either version 3 of the License, or (at your option) any later version. +// +// Licensees holding a valid commercial license may use this file in +// accordance with the commercial license agreement provided with the software. +// +// This file is provided AS IS with NO WARRANTY OF ANY KIND, INCLUDING THE +// WARRANTY OF DESIGN, MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE. +// +// $URL$ +// $Id$ +// +// Author(s) : Samuel Hornus + +#ifndef CGAL_TRIANGULATION_DATA_STRUCTURE_H +#define CGAL_TRIANGULATION_DATA_STRUCTURE_H + +#include <CGAL/basic.h> +#include <CGAL/Default.h> +#include <CGAL/iterator.h> +#include <CGAL/Compact_container.h> +#include <CGAL/Triangulation_face.h> +#include <CGAL/Triangulation_ds_vertex.h> +#include <CGAL/Triangulation_ds_full_cell.h> +#include <CGAL/internal/Combination_enumerator.h> +#include <CGAL/internal/Triangulation/utilities.h> +#include <CGAL/internal/Triangulation/Triangulation_ds_iterators.h> + +#include <algorithm> +#include <vector> +#include <queue> +#include <set> + +namespace CGAL { + +template< class Dimen, + class Vb = Default, + class Fcb = Default > +class Triangulation_data_structure +{ + typedef Triangulation_data_structure<Dimen, Vb, Fcb> Self; + typedef typename Default::Get<Vb, Triangulation_ds_vertex<> >::type V_base; + typedef typename Default::Get<Fcb, Triangulation_ds_full_cell<> >::type FC_base; + +public: + typedef typename V_base::template Rebind_TDS<Self>::Other Vertex; /* Concept */ + typedef typename FC_base::template Rebind_TDS<Self>::Other Full_cell; /* Concept */ + + // Tools to change the Vertex and Cell types of the TDS. + template < typename Vb2 > + struct Rebind_vertex { + typedef Triangulation_data_structure<Dimen, Vb2, Fcb> Other; + }; + + template < typename Fcb2 > + struct Rebind_full_cell { + typedef Triangulation_data_structure<Dimen, Vb, Fcb2> Other; + }; + + + + // we want to store an object of this class in every Full_cell: + class Full_cell_data + { + unsigned char bits_; + public: + Full_cell_data() : bits_(0) {} + Full_cell_data(const Full_cell_data & fcd) : bits_(fcd.bits_) {} + + void clear() { bits_ = 0; } + void mark_visited() { bits_ = 1; } + void clear_visited() { bits_ = 0; } + + bool is_clear() const { return bits_ == 0; } + bool is_visited() const { return bits_ == 1; } + // WARNING: if we use more bits and several bits can be set at once, + // then make sure to use bitwise operation above, instead of direct + // affectation. + }; + +protected: + typedef Compact_container<Vertex> Vertex_container; + typedef Compact_container<Full_cell> Full_cell_container; + +public: + typedef Dimen Maximal_dimension; + + typedef typename Vertex_container::size_type size_type; /* Concept */ + typedef typename Vertex_container::difference_type difference_type; /* Concept */ + + typedef typename Vertex_container::iterator Vertex_handle; /* Concept */ + typedef typename Vertex_container::iterator Vertex_iterator; /* Concept */ + typedef typename Vertex_container::const_iterator Vertex_const_handle; + typedef typename Vertex_container::const_iterator Vertex_const_iterator; + + typedef typename Full_cell_container::iterator Full_cell_handle; /* Concept */ + typedef typename Full_cell_container::iterator Full_cell_iterator; /* Concept */ + typedef typename Full_cell_container::const_iterator Full_cell_const_handle; + typedef typename Full_cell_container::const_iterator Full_cell_const_iterator; + + typedef internal::Triangulation:: + Triangulation_ds_facet_iterator<Self> Facet_iterator; /* Concept */ + + /* The 2 types defined below, |Facet| and |Rotor| are used when traversing + the boundary `B' of the union of a set of full cells. |Rotor| makes it + easy to rotate around itself, in the search of neighbors in `B' (see + |rotate_rotor| and |insert_in_tagged_hole|) */ + + // A co-dimension 1 sub-simplex. + class Facet /* Concept */ + { + Full_cell_handle full_cell_; + int index_of_covertex_; + public: + Facet() : full_cell_(), index_of_covertex_(0) {} + Facet(Full_cell_handle f, int i) : full_cell_(f), index_of_covertex_(i) {} + Full_cell_handle full_cell() const { return full_cell_; } + int index_of_covertex() const { return index_of_covertex_; } + }; + + // A co-dimension 2 sub-simplex. called a Rotor because we can rotate + // the two "covertices" around the sub-simplex. Useful for traversing the + // boundary of a hole. NOT DOCUMENTED + class Rotor : public Facet + { + int index_of_second_covertex_; + public: + Rotor() : Facet(), index_of_second_covertex_(0) {} + Rotor(Full_cell_handle f, int first, int second) : Facet(f, first), index_of_second_covertex_(second) {} + int index_of_second_covertex() const { return index_of_second_covertex_; } + }; + + typedef Triangulation_face<Self> Face; /* Concept */ + +protected: // DATA MEMBERS + + int dmax_, dcur_; // dimension of the current triangulation + Vertex_container vertices_; // list of all vertices + Full_cell_container full_cells_; // list of all full cells + +private: + + void clean_dynamic_memory() + { + vertices_.clear(); + full_cells_.clear(); + } + + template < class Dim_tag > + struct get_maximal_dimension + { + static int value(int D) { return D; } + }; + // specialization + template < int D > + struct get_maximal_dimension<Dimension_tag<D> > + { + static int value(int) { return D; } + }; + +public: + Triangulation_data_structure( int dim=0) /* Concept */ + : dmax_(get_maximal_dimension<Dimen>::value(dim)), dcur_(-2), + vertices_(), full_cells_() + { + CGAL_assertion_msg(dmax_ > 0, "maximal dimension must be positive."); + } + + ~Triangulation_data_structure() + { + clean_dynamic_memory(); + } + + Triangulation_data_structure(const Triangulation_data_structure & tds) + : dmax_(tds.dmax_), dcur_(tds.dcur_), + vertices_(tds.vertices_), full_cells_(tds.full_cells_) + { + typedef std::map<Vertex_const_handle, Vertex_handle> V_map; + typedef std::map<Full_cell_const_handle, Full_cell_handle> C_map; + V_map vmap; + C_map cmap; + Vertex_const_iterator vfrom = tds.vertices_begin(); + Vertex_iterator vto = vertices_begin(); + Full_cell_const_iterator cfrom = tds.full_cells_begin(); + Full_cell_iterator cto = full_cells_begin(); + while( vfrom != tds.vertices_end() ) + vmap[vfrom++] = vto++; + while( cfrom != tds.full_cells_end() ) + cmap[cfrom++] = cto++; + cto = full_cells_begin(); + while( cto != full_cells_end() ) + { + for( int i = 0; i <= (std::max)(0, current_dimension()); ++i ) + { + associate_vertex_with_full_cell(cto, i, vmap[cto->vertex(i)]); + cto->set_neighbor(i, cmap[cto->neighbor(i)]); + } + ++cto; + } + } + + // QUERIES + +protected: + + bool check_range(int i) const + { + if( current_dimension() < 0 ) + { + return (0 == i); + } + return ( (0 <= i) && (i <= current_dimension()) ); + } + +public: + + /* returns the current dimension of the full cells in the triangulation. */ + int maximal_dimension() const { return dmax_; } /* Concept */ + int current_dimension() const { return dcur_; } /* Concept */ + + size_type number_of_vertices() const /* Concept */ + { + return this->vertices_.size(); + } + size_type number_of_full_cells() const /* Concept */ + { + return this->full_cells_.size(); + } + + bool empty() const /* Concept */ + { + return current_dimension() == -2; + } + + Vertex_container & vertices() { return vertices_; } + const Vertex_container & vertices() const { return vertices_; } + Full_cell_container & full_cells() { return full_cells_; } + const Full_cell_container & full_cells() const { return full_cells_; } + + Vertex_handle vertex(Full_cell_handle s, int i) const /* Concept */ + { + CGAL_precondition(s != Full_cell_handle() && check_range(i)); + return s->vertex(i); + } + + Vertex_const_handle vertex(Full_cell_const_handle s, int i) const /* Concept */ + { + CGAL_precondition(s != Full_cell_handle() && check_range(i)); + return s->vertex(i); + } + + bool is_vertex(Vertex_const_handle v) const /* Concept */ + { + if( Vertex_const_handle() == v ) + return false; + Vertex_const_iterator vit = vertices_begin(); + while( vit != vertices_end() && ( v != vit ) ) + ++vit; + return v == vit; + } + + bool is_full_cell(Full_cell_const_handle s) const /* Concept */ + { + if( Full_cell_const_handle() == s ) + return false; + Full_cell_const_iterator sit = full_cells_begin(); + while( sit != full_cells_end() && ( s != sit ) ) + ++sit; + return s == sit; + } + + Full_cell_handle full_cell(Vertex_handle v) const /* Concept */ + { + CGAL_precondition(v != Vertex_handle()); + return v->full_cell(); + } + + Full_cell_const_handle full_cell(Vertex_const_handle v) const /* Concept */ + { + CGAL_precondition(Vertex_const_handle() != v); + return v->full_cell(); + } + + Full_cell_handle neighbor(Full_cell_handle s, int i) const /* Concept */ + { + CGAL_precondition(Full_cell_handle() != s && check_range(i)); + return s->neighbor(i); + } + + Full_cell_const_handle neighbor(Full_cell_const_handle s, int i) const/* Concept */ + { + CGAL_precondition(Full_cell_const_handle() != s && check_range(i)); + return s->neighbor(i); + } + + int mirror_index(Full_cell_handle s, int i) const /* Concept */ + { + CGAL_precondition(Full_cell_handle() != s && check_range(i)); + return s->mirror_index(i); + } + + int mirror_index(Full_cell_const_handle s, int i) const + { + CGAL_precondition(Full_cell_const_handle() != s && check_range(i)); /* Concept */ + return s->mirror_index(i); + } + + int mirror_vertex(Full_cell_handle s, int i) const /* Concept */ + { + CGAL_precondition(Full_cell_handle() != s && check_range(i)); + return s->mirror_vertex(i); + } + + // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - FACETS OPERATIONS + + // works for Face_ = Facet and Face_ = Rotor. + // NOT DOCUMENTED for the Rotor case... + template< typename Face_ > + Full_cell_handle full_cell(const Face_ & f) const /* Concept */ + { + return f.full_cell(); + } + + // works for Face_ = Facet and Face_ = Rotor. + // NOT DOCUMENTED for the Rotor case... + template< class Face_ > + int index_of_covertex(const Face_ & f) const /* Concept */ + { + return f.index_of_covertex(); + } + + // NOT DOCUMENTED + // A Rotor has two covertices + int index_of_second_covertex(const Rotor & f) const + { + return f.index_of_second_covertex(); + } + + // works for Face_ = Facet and Face_ = Rotor. + // NOT DOCUMENTED... + template< class Face_ > + bool is_boundary_facet(const Face_ & f) const + { + if( get_visited(neighbor(full_cell(f), index_of_covertex(f))) ) + return false; + if( ! get_visited(full_cell(f)) ) + return false; + return true; + } + + // NOT DOCUMENTED... + Rotor rotate_rotor(Rotor & f) + { + int opposite = mirror_index(full_cell(f), index_of_covertex(f)); + Full_cell_handle s = neighbor(full_cell(f), index_of_covertex(f)); + int new_second = s->index(vertex(full_cell(f), index_of_second_covertex(f))); + return Rotor(s, new_second, opposite); + } + + // NICE UPDATE OPERATIONS + +protected: + void do_insert_increase_dimension(Vertex_handle, Vertex_handle); +public: +// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - REMOVALS + + Vertex_handle collapse_face(const Face &); /* Concept */ + void remove_decrease_dimension(Vertex_handle, Vertex_handle); /* Concept */ + +// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - INSERTIONS + + Vertex_handle insert_in_full_cell(Full_cell_handle); /* Concept */ + Vertex_handle insert_in_face(const Face &); /* Concept */ + Vertex_handle insert_in_facet(const Facet &); /* Concept */ + template< typename Forward_iterator > + Vertex_handle insert_in_hole(Forward_iterator, Forward_iterator, Facet); /* Concept */ + template< typename Forward_iterator, typename OutputIterator > + Vertex_handle insert_in_hole(Forward_iterator, Forward_iterator, Facet, OutputIterator); /* Concept */ + + template< typename OutputIterator > + Full_cell_handle insert_in_tagged_hole(Vertex_handle, Facet, OutputIterator); + + Vertex_handle insert_increase_dimension(Vertex_handle=Vertex_handle()); /* Concept */ + +private: + + // Used by insert_in_tagged_hole + struct IITH_task + { + IITH_task( + Facet boundary_facet_, + int index_of_inside_cell_in_outside_cell_, + Full_cell_handle future_neighbor_ = Full_cell_handle(), + int new_cell_index_in_future_neighbor_ = -1, + int index_of_future_neighbor_in_new_cell_ = -1) + : boundary_facet(boundary_facet_), + index_of_inside_cell_in_outside_cell(index_of_inside_cell_in_outside_cell_), + future_neighbor(future_neighbor_), + new_cell_index_in_future_neighbor(new_cell_index_in_future_neighbor_), + index_of_future_neighbor_in_new_cell(index_of_future_neighbor_in_new_cell_) + {} + + // "new_cell" is the cell about to be created + Facet boundary_facet; + int index_of_inside_cell_in_outside_cell; + Full_cell_handle future_neighbor; + int new_cell_index_in_future_neighbor; + int index_of_future_neighbor_in_new_cell; + }; + + // NOT DOCUMENTED + void clear_visited_marks(Full_cell_handle) const; + + // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - DANGEROUS UPDATE OPERATIONS + +private: + + // NOT DOCUMENTED + template< typename FCH > // FCH = Full_cell_[const_]handle + bool get_visited(FCH c) const + { + return c->tds_data().is_visited(); + } + + // NOT DOCUMENTED + template< typename FCH > // FCH = Full_cell_[const_]handle + void set_visited(FCH c, bool m) const + { + if( m ) + c->tds_data().mark_visited(); + else + c->tds_data().clear_visited(); + } + +public: + + void clear() /* Concept */ + { + clean_dynamic_memory(); + dcur_ = -2; + } + + void set_current_dimension(int d) /* Concept */ + { + CGAL_precondition(-2<=d && d<=maximal_dimension()); + dcur_ = d; + } + + Full_cell_handle new_full_cell(Full_cell_handle s) + { + return full_cells_.emplace(*s); + } + + Full_cell_handle new_full_cell() /* Concept */ + { + return full_cells_.emplace(dmax_); + } + + void delete_full_cell(Full_cell_handle s) /* Concept */ + { + CGAL_precondition(Full_cell_handle() != s); + // CGAL_expensive_precondition(is_full_cell(s)); + full_cells_.erase(s); + } + + template< typename Forward_iterator > + void delete_full_cells(Forward_iterator start, Forward_iterator end) /* Concept */ + { + Forward_iterator s = start; + while( s != end ) + full_cells_.erase(*s++); + } + + template< class T > + Vertex_handle new_vertex( const T & t ) + { + return vertices_.emplace(t); + } + + Vertex_handle new_vertex() /* Concept */ + { + return vertices_.emplace(); + } + + void delete_vertex(Vertex_handle v) /* Concept */ + { + CGAL_precondition( Vertex_handle() != v ); + vertices_.erase(v); + } + + void associate_vertex_with_full_cell(Full_cell_handle s, int i, Vertex_handle v) /* Concept */ + { + CGAL_precondition(check_range(i)); + CGAL_precondition(s != Full_cell_handle()); + CGAL_precondition(v != Vertex_handle()); + s->set_vertex(i, v); + v->set_full_cell(s); + } + + void set_neighbors(Full_cell_handle s, int i, Full_cell_handle s1, int j) /* Concept */ + { + CGAL_precondition(check_range(i)); + CGAL_precondition(check_range(j)); + CGAL_precondition(s != Full_cell_handle()); + CGAL_precondition(s1 != Full_cell_handle()); + s->set_neighbor(i, s1); + s1->set_neighbor(j, s); + s->set_mirror_index(i, j); + s1->set_mirror_index(j, i); + } + + // SANITY CHECKS + + bool is_valid(bool = true, int = 0) const; /* Concept */ + + // NOT DOCUMENTED + template< class OutStream> void write_graph(OutStream &); + + Vertex_iterator vertices_begin() { return vertices_.begin(); } /* Concept */ + Vertex_iterator vertices_end() { return vertices_.end(); } /* Concept */ + Full_cell_iterator full_cells_begin() { return full_cells_.begin(); } /* Concept */ + Full_cell_iterator full_cells_end() { return full_cells_.end(); } /* Concept */ + + Vertex_const_iterator vertices_begin() const { return vertices_.begin(); } /* Concept */ + Vertex_const_iterator vertices_end() const { return vertices_.end(); } /* Concept */ + Full_cell_const_iterator full_cells_begin() const { return full_cells_.begin(); } /* Concept */ + Full_cell_const_iterator full_cells_end() const { return full_cells_.end(); } /* Concept */ + + Facet_iterator facets_begin() /* Concept */ + { + if( current_dimension() <= 0 ) + return facets_end(); + return Facet_iterator(*this); + } + Facet_iterator facets_end() /* Concept */ + { + return Facet_iterator(*this, 0); + } + +// - - - - - - - - - - - - - - - - - - - - - - - - - - - FULL CELL GATHERING + + // a traversal predicate for gathering full_cells incident to a given face + // ``incident'' means that the given face is a subface of the full_cell + class Incident_full_cell_traversal_predicate + { + const Face & f_; + int dim_; + const Triangulation_data_structure & tds_; + public: + Incident_full_cell_traversal_predicate(const Triangulation_data_structure & tds, + const Face & f) + : f_(f), tds_(tds) + { + dim_ = f.face_dimension(); + } + bool operator()(const Facet & facet) const + { + Vertex_handle v = tds_.full_cell(facet)->vertex(tds_.index_of_covertex(facet)); + for( int i = 0; i <= dim_; ++i ) + { + if( v == f_.vertex(i) ) + return false; + } + return true; + } + }; + + // a traversal predicate for gathering full_cells having a given face as subface + class Star_traversal_predicate + { + const Face & f_; + int dim_; + const Triangulation_data_structure & tds_; + public: + Star_traversal_predicate(const Triangulation_data_structure & tds, + const Face & f) + : f_(f), tds_(tds) + { + dim_ = f.face_dimension(); + } + bool operator()(const Facet & facet) const + { + Full_cell_handle s = tds_.full_cell(facet)->neighbor(tds_.index_of_covertex(facet)); + for( int j = 0; j <= tds_.current_dimension(); ++j ) + { + for( int i = 0; i <= dim_; ++i ) + if( s->vertex(j) == f_.vertex(i) ) + return true; + } + return false; + } + }; + + template< typename TraversalPredicate, typename OutputIterator > + Facet gather_full_cells(Full_cell_handle, TraversalPredicate &, OutputIterator &) const; /* Concept */ + template< typename OutputIterator > + OutputIterator incident_full_cells(const Face &, OutputIterator) const; /* Concept */ + template< typename OutputIterator > + OutputIterator incident_full_cells(Vertex_const_handle, OutputIterator) const; /* Concept */ + template< typename OutputIterator > + OutputIterator star(const Face &, OutputIterator) const; /* Concept */ +#ifndef CGAL_CFG_NO_CPP0X_DEFAULT_TEMPLATE_ARGUMENTS_FOR_FUNCTION_TEMPLATES + template< typename OutputIterator, typename Comparator = std::less<Vertex_const_handle> > + OutputIterator incident_upper_faces(Vertex_const_handle v, int dim, OutputIterator out, Comparator cmp = Comparator()) + { + return incident_faces(v, dim, out, cmp, true); + } + template< typename OutputIterator, typename Comparator = std::less<Vertex_const_handle> > + OutputIterator incident_faces(Vertex_const_handle, int, OutputIterator, Comparator = Comparator(), bool = false) const; +#else + template< typename OutputIterator, typename Comparator > + OutputIterator incident_upper_faces(Vertex_const_handle v, int dim, OutputIterator out, Comparator cmp = Comparator()) + { + return incident_faces(v, dim, out, cmp, true); + } + template< typename OutputIterator > + OutputIterator incident_upper_faces(Vertex_const_handle v, int dim, OutputIterator out) + { + return incident_faces(v, dim, out, std::less<Vertex_const_handle>(), true); + } + template< typename OutputIterator, typename Comparator > + OutputIterator incident_faces(Vertex_const_handle, int, OutputIterator, Comparator = Comparator(), bool = false) const; + template< typename OutputIterator > + OutputIterator incident_faces(Vertex_const_handle, int, OutputIterator, + std::less<Vertex_const_handle> = std::less<Vertex_const_handle>(), bool = false) const; +#endif + +// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - INPUT / OUTPUT + + std::istream & read_full_cells(std::istream &, const std::vector<Vertex_handle> &); + std::ostream & write_full_cells(std::ostream &, std::map<Vertex_const_handle, int> &) const; + +}; // end of ``declaration/definition'' of Triangulation_data_structure<...> + +// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = + +// FUNCTIONS THAT ARE MEMBER FUNCTIONS: + +// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - +// - - - - - - - - - - - - - - - - - - - - - - - - THE GATHERING METHODS + +template< class Dim, class Vb, class Fcb > +template< typename OutputIterator > +OutputIterator +Triangulation_data_structure<Dim, Vb, Fcb> +::incident_full_cells(const Face & f, OutputIterator out) const /* Concept */ +{ + // CGAL_expensive_precondition_msg(is_full_cell(f.full_cell()), "the facet does not belong to the Triangulation"); + Incident_full_cell_traversal_predicate tp(*this, f); + gather_full_cells(f.full_cell(), tp, out); + return out; +} + +template< class Dim, class Vb, class Fcb > +template< typename OutputIterator > +OutputIterator +Triangulation_data_structure<Dim, Vb, Fcb> +::incident_full_cells(Vertex_const_handle v, OutputIterator out) const /* Concept */ +{ +// CGAL_expensive_precondition(is_vertex(v)); + CGAL_precondition(Vertex_handle() != v); + Face f(v->full_cell()); + f.set_index(0, v->full_cell()->index(v)); + return incident_full_cells(f, out); +} + +template< class Dim, class Vb, class Fcb > +template< typename OutputIterator > +OutputIterator +Triangulation_data_structure<Dim, Vb, Fcb> +::star(const Face & f, OutputIterator out) const /* Concept */ +{ + // CGAL_precondition_msg(is_full_cell(f.full_cell()), "the facet does not belong to the Triangulation"); + Star_traversal_predicate tp(*this, f); + gather_full_cells(f.full_cell(), tp, out); + return out; +} + +template< class Dim, class Vb, class Fcb > +template< typename TraversalPredicate, typename OutputIterator > +typename Triangulation_data_structure<Dim, Vb, Fcb>::Facet +Triangulation_data_structure<Dim, Vb, Fcb> +::gather_full_cells(Full_cell_handle start, + TraversalPredicate & tp, + OutputIterator & out) const /* Concept */ +{ + std::queue<Full_cell_handle> queue; + set_visited(start, true); + queue.push(start); + const int cur_dim = current_dimension(); + Facet ft; + while( ! queue.empty() ) + { + Full_cell_handle s = queue.front(); + queue.pop(); + *out = s; + ++out; + for( int i = 0; i <= cur_dim; ++i ) + { + Full_cell_handle n = s->neighbor(i); + if( ! get_visited(n) ) + { + set_visited(n, true); + if( tp(Facet(s, i)) ) + queue.push(n); + else + ft = Facet(s, i); + } + } + } + clear_visited_marks(start); + return ft; +} + +#ifdef CGAL_CFG_NO_CPP0X_DEFAULT_TEMPLATE_ARGUMENTS_FOR_FUNCTION_TEMPLATES +template< class Dim, class Vb, class Fcb > +template< typename OutputIterator > +OutputIterator +Triangulation_data_structure<Dim, Vb, Fcb> +::incident_faces(Vertex_const_handle v, int dim, OutputIterator out, + std::less<Vertex_const_handle> cmp, bool upper_faces) const +{ + return incident_faces<OutputIterator, std::less<Vertex_const_handle> >(v, dim, out, cmp, upper_faces); +} +#endif + +template< class Dim, class Vb, class Fcb > +template< typename OutputIterator, typename Comparator > +OutputIterator +Triangulation_data_structure<Dim, Vb, Fcb> +::incident_faces(Vertex_const_handle v, int dim, OutputIterator out, Comparator cmp, bool upper_faces) const +{ + CGAL_precondition( 0 < dim ); + if( dim >= current_dimension() ) + return out; + typedef std::vector<Full_cell_handle> Simplices; + Simplices simps; + simps.reserve(64); + // gather incident full_cells + std::back_insert_iterator<Simplices> sout(simps); + incident_full_cells(v, sout); + // for storing the handles to the vertices of a full_cell + typedef std::vector<Vertex_const_handle> Vertices; + typedef std::vector<int> Indices; + Vertices vertices(1 + current_dimension()); + Indices sorted_idx(1 + current_dimension()); + // setup Face comparator and Face_set + typedef internal::Triangulation::Compare_faces_with_common_first_vertex<Self> + Upper_face_comparator; + Upper_face_comparator ufc(dim); + typedef std::set<Face, Upper_face_comparator> Face_set; + Face_set face_set(ufc); + for( typename Simplices::const_iterator s = simps.begin(); s != simps.end(); ++s ) + { + int v_idx(0); // the index of |v| in the sorted full_cell + // get the vertices of the full_cell and sort them + for( int i = 0; i <= current_dimension(); ++i ) + vertices[i] = (*s)->vertex(i); + if( upper_faces ) + { + std::sort(vertices.begin(), vertices.end(), cmp); + while( vertices[v_idx] != v ) + ++v_idx; + } + else + { + while( vertices[v_idx] != v ) + ++v_idx; + if( 0 != v_idx ) + std::swap(vertices[0], vertices[v_idx]); + v_idx = 0; + typename Vertices::iterator vbegin(vertices.begin()); + ++vbegin; + std::sort(vbegin, vertices.end(), cmp); + } + if( v_idx + dim > current_dimension() ) + continue; // |v| is too far to the right + // stores the index of the vertices of s in the same order + // as in |vertices|: + for( int i = 0; i <= current_dimension(); ++i ) + sorted_idx[i] = (*s)->index(vertices[i]); + // init state for enumerating all candidate faces: + internal::Combination_enumerator f_idx(dim, v_idx + 1, current_dimension()); + Face f(*s); + f.set_index(0, sorted_idx[v_idx]); + while( ! f_idx.end() ) + { + for( int i = 0; i < dim; ++i ) + f.set_index(1 + i, sorted_idx[f_idx[i]]); + face_set.insert(f); // checks if face has already been found + + // compute next sorted face (lexicographic enumeration) + ++f_idx; + } + } + typename Face_set::iterator fit = face_set.begin(); + while( fit != face_set.end() ) + *out++ = *fit++; + return out; +} + +// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - +// - - - - - - - - - - - - - - - - - - - - - - - - THE REMOVAL METHODS + +template <class Dim, class Vb, class Fcb> +typename Triangulation_data_structure<Dim, Vb, Fcb>::Vertex_handle +Triangulation_data_structure<Dim, Vb, Fcb> +::collapse_face(const Face & f) /* Concept */ +{ + const int fd = f.face_dimension(); + CGAL_precondition( (1 <= fd ) && (fd < current_dimension())); + std::vector<Full_cell_handle> simps; + // save the Face's vertices: + Full_cell s; + for( int i = 0; i <= fd; ++i ) + s.set_vertex(i, f.vertex(i)); + // compute the star of f + simps.reserve(64); + std::back_insert_iterator<std::vector<Full_cell_handle> > out(simps); + star(f, out); + Vertex_handle v = insert_in_hole(simps.begin(), simps.end(), Facet(f.full_cell(), f.index(0))); + for( int i = 0; i <= fd; ++i ) + delete_vertex(s.vertex(i)); + return v; +} + +template <class Dim, class Vb, class Fcb> +void +Triangulation_data_structure<Dim, Vb, Fcb> +::remove_decrease_dimension(Vertex_handle v, Vertex_handle star) /* Concept */ +{ + CGAL_assertion( current_dimension() >= -1 ); + if( -1 == current_dimension() ) + { + clear(); + return; + } + else if( 0 == current_dimension() ) + { + delete_full_cell(v->full_cell()); + delete_vertex(v); + star->full_cell()->set_neighbor(0, Full_cell_handle()); + set_current_dimension(-1); + return; + } + else if( 1 == current_dimension() ) + { + Full_cell_handle s = v->full_cell(); + int star_index; + if( s->has_vertex(star, star_index) ) + s = s->neighbor(star_index); + // Here, |star| is not a vertex of |s|, so it's the only finite + // full_cell + Full_cell_handle inf1 = s->neighbor(0); + Full_cell_handle inf2 = s->neighbor(1); + Vertex_handle v2 = s->vertex(1 - s->index(v)); + delete_vertex(v); + delete_full_cell(s); + inf1->set_vertex(1, Vertex_handle()); + inf1->set_vertex(1, Vertex_handle()); + inf2->set_neighbor(1, Full_cell_handle()); + inf2->set_neighbor(1, Full_cell_handle()); + associate_vertex_with_full_cell(inf1, 0, star); + associate_vertex_with_full_cell(inf2, 0, v2); + set_neighbors(inf1, 0, inf2, 0); + set_current_dimension(0); + return; + } + typedef std::vector<Full_cell_handle> Simplices; + Simplices simps; + incident_full_cells(v, std::back_inserter(simps)); + for( typename Simplices::iterator it = simps.begin(); it != simps.end(); ++it ) + { + int v_idx = (*it)->index(v); + if( ! (*it)->has_vertex(star) ) + { + delete_full_cell((*it)->neighbor(v_idx)); + for( int i = 0; i <= current_dimension(); ++i ) + (*it)->vertex(i)->set_full_cell(*it); + } + else + star->set_full_cell(*it); + if( v_idx != current_dimension() ) + { + (*it)->swap_vertices(v_idx, current_dimension()); + (*it)->swap_vertices(current_dimension() - 2, current_dimension() - 1); + } + (*it)->set_vertex(current_dimension(), Vertex_handle()); + (*it)->set_neighbor(current_dimension(), Full_cell_handle()); + } + set_current_dimension(current_dimension()-1); + delete_vertex(v); +} + +// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - +// - - - - - - - - - - - - - - - - - - - - - - - - THE INSERTION METHODS + +template <class Dim, class Vb, class Fcb> +typename Triangulation_data_structure<Dim, Vb, Fcb>::Vertex_handle +Triangulation_data_structure<Dim, Vb, Fcb> +::insert_in_full_cell(Full_cell_handle s) /* Concept */ +{ + CGAL_precondition(0 < current_dimension()); + CGAL_precondition(Full_cell_handle() != s); + // CGAL_expensive_precondition(is_full_cell(s)); + + const int cur_dim = current_dimension(); + Vertex_handle v = new_vertex(); + // the full_cell 'fc' is just used to store the handle to all the new full_cells. + Full_cell fc(maximal_dimension()); + for( int i = 1; i <= cur_dim; ++i ) + { + Full_cell_handle new_s = new_full_cell(s); + fc.set_neighbor(i, new_s); + associate_vertex_with_full_cell(new_s, i, v); + s->vertex(i-1)->set_full_cell(new_s); + set_neighbors(new_s, i, neighbor(s, i), mirror_index(s, i)); + } + fc.set_neighbor(0, s); + associate_vertex_with_full_cell(s, 0, v); + for( int i = 0; i <= cur_dim; ++i ) + for( int j = 0; j <= cur_dim; ++j ) + { + if( j == i ) continue; + set_neighbors(fc.neighbor(i), j, fc.neighbor(j), i); + } + return v; +} + +template <class Dim, class Vb, class Fcb > +typename Triangulation_data_structure<Dim, Vb, Fcb>::Vertex_handle +Triangulation_data_structure<Dim, Vb, Fcb> +::insert_in_face(const Face & f) /* Concept */ +{ + std::vector<Full_cell_handle> simps; + simps.reserve(64); + std::back_insert_iterator<std::vector<Full_cell_handle> > out(simps); + incident_full_cells(f, out); + return insert_in_hole(simps.begin(), simps.end(), Facet(f.full_cell(), f.index(0))); +} +template <class Dim, class Vb, class Fcb > +typename Triangulation_data_structure<Dim, Vb, Fcb>::Vertex_handle +Triangulation_data_structure<Dim, Vb, Fcb> +::insert_in_facet(const Facet & ft) /* Concept */ +{ + Full_cell_handle s[2]; + s[0] = full_cell(ft); + int i = index_of_covertex(ft); + s[1] = s[0]->neighbor(i); + i = ( i + 1 ) % current_dimension(); + return insert_in_hole(s, s+2, Facet(s[0], i)); +} + +template <class Dim, class Vb, class Fcb > +template < typename OutputIterator > +typename Triangulation_data_structure<Dim, Vb, Fcb>::Full_cell_handle +Triangulation_data_structure<Dim, Vb, Fcb> +::insert_in_tagged_hole(Vertex_handle v, Facet f, + OutputIterator new_full_cells) +{ + CGAL_assertion_msg(is_boundary_facet(f), "starting facet should be on the hole boundary"); + + const int cur_dim = current_dimension(); + Full_cell_handle new_s; + + std::queue<IITH_task> task_queue; + task_queue.push( + IITH_task(f, mirror_index(full_cell(f), index_of_covertex(f))) ); + + while (!task_queue.empty()) + { + IITH_task task = task_queue.front(); + task_queue.pop(); + + Full_cell_handle old_s = full_cell(task.boundary_facet); + const int facet_index = index_of_covertex(task.boundary_facet); + + Full_cell_handle outside_neighbor = neighbor(old_s, facet_index); + // Here, "new_s" might actually be a new cell, but it might also be "old_s" + // if it has not been treated already in the meantime + new_s = neighbor(outside_neighbor, task.index_of_inside_cell_in_outside_cell); + // If the cell has not been treated yet + if (old_s == new_s) + { + new_s = new_full_cell(); + + int i(0); + for ( ; i < facet_index ; ++i) + associate_vertex_with_full_cell(new_s, i, old_s->vertex(i)); + ++i; // skip facet_index + for ( ; i <= cur_dim ; ++i) + associate_vertex_with_full_cell(new_s, i, old_s->vertex(i)); + associate_vertex_with_full_cell(new_s, facet_index, v); + set_neighbors(new_s, + facet_index, + outside_neighbor, + mirror_index(old_s, facet_index)); + + // add the new full_cell to the list of new full_cells + *new_full_cells++ = new_s; + + // check all of |Facet f|'s neighbors + for (i = 0 ; i <= cur_dim ; ++i) + { + if (facet_index == i) + continue; + // we define a |Rotor| because it makes it easy to rotate around + // in a self contained fashion. The corresponding potential + // boundary facet is Facet(full_cell(rot), index_of_covertex(rot)) + Rotor rot(old_s, i, facet_index); + // |rot| on line above, stands for Candidate Facet + while (!is_boundary_facet(rot)) + rot = rotate_rotor(rot); + + // we did find the |i|-th neighbor of Facet(old_s, facet_index)... + // has it already been extruded to center point |v| ? + Full_cell_handle inside = full_cell(rot); + Full_cell_handle outside = neighbor(inside, index_of_covertex(rot)); + // "m" is the vertex of outside which is not on the boundary + Vertex_handle m = inside->mirror_vertex(index_of_covertex(rot), current_dimension()); // CJTODO: use mirror_index? + // "index" is the index of m in "outside" + int index = outside->index(m); + // new_neighbor is the inside cell which is registered as the neighbor + // of the outside cell => it's either a newly created inside cell or an + // old inside cell which we are about to delete + Full_cell_handle new_neighbor = outside->neighbor(index); + + // Is new_neighbor still the old neighbor? + if (new_neighbor == inside) + { + task_queue.push(IITH_task( + Facet(inside, index_of_covertex(rot)), // boundary facet + index, // index_of_inside_cell_in_outside_cell + new_s, // future_neighbor + i, // new_cell_index_in_future_neighbor + index_of_second_covertex(rot) // index_of_future_neighbor_in_new_cell + )); + } + } + } + + // If there is some neighbor stories to fix + if (task.future_neighbor != Full_cell_handle()) + { + // now the new neighboring full_cell exists, we link both + set_neighbors(new_s, + task.index_of_future_neighbor_in_new_cell, + task.future_neighbor, + task.new_cell_index_in_future_neighbor); + } + } + + return new_s; +} + +template< class Dim, class Vb, class Fcb > +template< typename Forward_iterator, typename OutputIterator > +typename Triangulation_data_structure<Dim, Vb, Fcb>::Vertex_handle +Triangulation_data_structure<Dim, Vb, Fcb> +::insert_in_hole(Forward_iterator start, Forward_iterator end, Facet f, + OutputIterator out) /* Concept */ +{ + CGAL_expensive_precondition( + ( std::distance(start, end) == 1 ) + || ( current_dimension() > 1 ) ); + Forward_iterator sit = start; + while( end != sit ) + set_visited(*sit++, true); + Vertex_handle v = new_vertex(); + insert_in_tagged_hole(v, f, out); + delete_full_cells(start, end); + return v; +} + +template< class Dim, class Vb, class Fcb > +template< typename Forward_iterator > +typename Triangulation_data_structure<Dim, Vb, Fcb>::Vertex_handle +Triangulation_data_structure<Dim, Vb, Fcb> +::insert_in_hole(Forward_iterator start, Forward_iterator end, Facet f) /* Concept */ +{ + Emptyset_iterator out; + return insert_in_hole(start, end, f, out); +} + +template <class Dim, class Vb, class Fcb> +void +Triangulation_data_structure<Dim, Vb, Fcb> +::clear_visited_marks(Full_cell_handle start) const // NOT DOCUMENTED +{ + CGAL_precondition(start != Full_cell_handle()); + + std::queue<Full_cell_handle> queue; + set_visited(start, false); + queue.push(start); + const int cur_dim = current_dimension(); + while( ! queue.empty() ) + { + Full_cell_handle s = queue.front(); + queue.pop(); + for( int i = 0; i <= cur_dim; ++i ) + { + if( get_visited(s->neighbor(i)) ) + { + set_visited(s->neighbor(i), false); + queue.push(s->neighbor(i)); + } + } + } +} + +template <class Dim, class Vb, class Fcb> +void Triangulation_data_structure<Dim, Vb, Fcb> +::do_insert_increase_dimension(Vertex_handle x, Vertex_handle star) +{ + Full_cell_handle start = full_cells_begin(); + Full_cell_handle swap_me; + const int cur_dim = current_dimension(); + for( Full_cell_iterator S = full_cells_begin(); S != full_cells_end(); ++S ) + { + if( Vertex_handle() != S->vertex(cur_dim) ) + continue; + set_visited(S, true); + // extends full_cell |S| to include the new vertex as the + // current_dimension()-th vertex + associate_vertex_with_full_cell(S, cur_dim, x); + if( ! S->has_vertex(star) ) + { // S is bounded, we create its unbounded "twin" full_cell + Full_cell_handle S_new = new_full_cell(); + set_neighbors(S, cur_dim, S_new, 0); + associate_vertex_with_full_cell(S_new, 0, star); + // here, we could be clever so as to get consistent orientation + for( int k = 1; k <= cur_dim; ++k ) + associate_vertex_with_full_cell(S_new, k, vertex(S, k - 1)); + } + } + // now we setup the neighbors + set_visited(start, false); + std::queue<Full_cell_handle> queue; + queue.push(start); + while( ! queue.empty() ) + { + Full_cell_handle S = queue.front(); + queue.pop(); + // here, the first visit above ensured that all neighbors exist now. + // Now we need to connect them with adjacency relation + int star_index; + if( S->has_vertex(star, star_index) ) + { + set_neighbors( S, cur_dim, neighbor(neighbor(S, star_index), cur_dim), + // this is tricky :-) : + mirror_index(S, star_index) + 1); + } + else + { + Full_cell_handle S_new = neighbor(S, cur_dim); + for( int k = 0 ; k < cur_dim ; ++k ) + { + Full_cell_handle S_opp = neighbor(S, k); + if( ! S_opp->has_vertex(star) ) + set_neighbors(S_new, k + 1, neighbor(S_opp, cur_dim), mirror_index(S, k) + 1); + // neighbor of S_new opposite to v is S_new' + // the vertex opposite to v remains the same but ... + // remember the shifting of the vertices one step to the right + } + } + for( int k = 0 ; k < cur_dim ; ++k ) + if( get_visited(neighbor(S, k)) ) + { + set_visited(neighbor(S, k), false); + queue.push(neighbor(S, k)); + } + } + if( ( ( cur_dim % 2 ) == 0 ) && ( cur_dim > 1 ) ) + { + for( Full_cell_iterator S = full_cells_begin(); S != full_cells_end(); ++S ) + { + if( x != S->vertex(cur_dim) ) + S->swap_vertices(cur_dim - 1, cur_dim); + } + } + if( Full_cell_handle() != swap_me ) + swap_me->swap_vertices(1, 2); +} + +template <class Dim, class Vb, class Fcb> +typename Triangulation_data_structure<Dim, Vb, Fcb>::Vertex_handle +Triangulation_data_structure<Dim, Vb, Fcb> +::insert_increase_dimension(Vertex_handle star) /* Concept */ +{ + const int prev_cur_dim = current_dimension(); + CGAL_precondition(prev_cur_dim < maximal_dimension()); + if( -2 != current_dimension() ) + { + CGAL_precondition( Vertex_handle() != star ); + CGAL_expensive_precondition(is_vertex(star)); + } + + set_current_dimension(prev_cur_dim + 1); + Vertex_handle v = new_vertex(); + switch( prev_cur_dim ) + { + case -2: + { // insertion of the first vertex + // ( geometrically : infinite vertex ) + Full_cell_handle s = new_full_cell(); + associate_vertex_with_full_cell(s, 0, v); + break; + } + case -1: + { // insertion of the second vertex + // ( geometrically : first finite vertex ) + //we create a triangulation of the 0-sphere, with + // vertices |star| and |v| + Full_cell_handle infinite_full_cell = star->full_cell(); + Full_cell_handle finite_full_cell = new_full_cell(); + associate_vertex_with_full_cell(finite_full_cell, 0, v); + set_neighbors(infinite_full_cell, 0, finite_full_cell, 0); + break; + } + default: + do_insert_increase_dimension(v, star); + break; + } + return v; +} + +// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - +// - - - - - - - - - - - - - - - - - - - - - - - - VALIDITY CHECKS + +template <class Dimen, class Vb, class Fcb> +bool Triangulation_data_structure<Dimen, Vb, Fcb> +::is_valid(bool verbose, int /* level */) const /* Concept */ +{ + Full_cell_const_handle s, t; + Vertex_const_handle v; + int i, j, k; + + if( current_dimension() == -2 ) + { + if( ! vertices_.empty() || ! full_cells_.empty() ) + { + if( verbose ) CGAL_warning_msg(false, "current dimension is -2 but there are vertices or full_cells"); + return false; + } + } + + if( current_dimension() == -1 ) + { + if ( (number_of_vertices() != 1) || (number_of_full_cells() != 1) ) + { + if( verbose ) CGAL_warning_msg(false, "current dimension is -1 but there isn't one vertex and one full_cell"); + return false; + } + } + + for( v = vertices_begin(); v != vertices_end(); ++v ) + { + if( ! v->is_valid(verbose) ) + return false; + } + + // FUTURE: for each vertex v, gather incident full_cells. then, check that + // any full_cell containing v is among those gathered full_cells... + + if( current_dimension() < 0 ) + return true; + + for( s = full_cells_begin(); s != full_cells_end(); ++s ) + { + if( ! s->is_valid(verbose) ) + return false; + // check that the full cell has no duplicate vertices + for( i = 0; i <= current_dimension(); ++i ) + for( j = i + 1; j <= current_dimension(); ++j ) + if( vertex(s,i) == vertex(s,j) ) + { + CGAL_warning_msg(false, "a full_cell has two equal vertices"); + return false; + } + } + + for( s = full_cells_begin(); s != full_cells_end(); ++s ) + { + for( i = 0; i <= current_dimension(); ++i ) + if( (t = neighbor(s,i)) != Full_cell_const_handle() ) + { + int l = mirror_index(s,i); + if( s != neighbor(t,l) || i != mirror_index(t,l) ) + { + if( verbose ) CGAL_warning_msg(false, "neighbor relation is not symmetric"); + return false; + } + for( j = 0; j <= current_dimension(); ++j ) + if( j != i ) + { + // j must also occur as a vertex of t + for( k = 0; k <= current_dimension() && ( vertex(s,j) != vertex(t,k) || k == l); ++k ) + ; + if( k > current_dimension() ) + { + if( verbose ) CGAL_warning_msg(false, "too few shared vertices between neighbors full_cells."); + return false; + } + } + } + else + { + if( verbose ) CGAL_warning_msg(false, "full_cell has a NULL neighbor"); + return false; + } + } + return true; +} + +// - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - +// - - - - - - - - - - - - - - - - - - - - - - - - INPUT / OUTPUT + +// NOT DOCUMENTED +template <class Dim, class Vb, class Fcb> +template <class OutStream> +void Triangulation_data_structure<Dim, Vb, Fcb> +::write_graph(OutStream & os) +{ + std::vector<std::set<int> > edges; + os << number_of_vertices() + 1; // add the vertex at infinity + int count(1); + for( Vertex_iterator vit = vertices_begin(); vit != vertices_end(); ++vit ) + vit->idx_ = count++; + edges.resize(number_of_vertices()+1); + for( Full_cell_iterator sit = full_cells_begin(); sit != full_cells_end(); ++sit ) + { + int v1 = 0; + while( v1 < current_dimension() ) + { + int v2 = v1 + 1; + while( v2 <= current_dimension() ) + { + int i1, i2; + if( Vertex_handle() != sit-> vertex(v1) ) + i1 = sit->vertex(v1)->idx_; + else + i1 = 0; + if( Vertex_handle() != sit-> vertex(v2) ) + i2 = sit->vertex(v2)->idx_; + else + i2 = 0; + edges[i1].insert(i2); + edges[i2].insert(i1); + ++v2; + } + ++v1; + } + } + for( std::size_t i = 0; i < edges.size(); ++i ) + { + os << std::endl << edges[i].size(); + for( std::set<int>::const_iterator nit = edges[i].begin(); + nit != edges[i].end(); ++nit ) + { + os << ' ' << (*nit); + } + } +} + +// NOT DOCUMENTED... +template<class Dimen, class Vb, class Fcb> +std::istream & +Triangulation_data_structure<Dimen, Vb, Fcb> +::read_full_cells(std::istream & is, const std::vector<Vertex_handle> & vertices) +{ + std::size_t m; // number of full_cells + int index; + const int cd = current_dimension(); + if( is_ascii(is) ) + is >> m; + else + read(is, m, io_Read_write()); + + std::vector<Full_cell_handle> full_cells; + full_cells.reserve(m); + // read the vertices of each full_cell + std::size_t i = 0; + while( i < m ) + { + Full_cell_handle s = new_full_cell(); + full_cells.push_back(s); + for( int j = 0; j <= cd; ++j ) + { + if( is_ascii(is) ) + is >> index; + else + read(is, index); + s->set_vertex(j, vertices[index]); + } + // read other non-combinatorial information for the full_cells + is >> (*s); + ++i; + } + + // read the neighbors of each full_cell + i = 0; + if( is_ascii(is) ) + while( i < m ) + { + for( int j = 0; j <= cd; ++j ) + { + is >> index; + full_cells[i]->set_neighbor(j, full_cells[index]); + } + ++i; + } + else + while( i < m ) + { + for( int j = 0; j <= cd; ++j ) + { + read(is, index); + full_cells[i]->set_neighbor(j, full_cells[index]); + } + ++i; + } + + // compute the mirror indices + for( i = 0; i < m; ++i ) + { + Full_cell_handle s = full_cells[i]; + for( int j = 0; j <= cd; ++j ) + { + if( -1 != s->mirror_index(j) ) + continue; + Full_cell_handle n = s->neighbor(j); + int k = 0; + Full_cell_handle nn = n->neighbor(k); + while( s != nn ) + nn = n->neighbor(++k); + s->set_mirror_index(j,k); + n->set_mirror_index(k,j); + } + } + return is; +} + +// NOT DOCUMENTED... +template<class Dimen, class Vb, class Fcb> +std::ostream & +Triangulation_data_structure<Dimen, Vb, Fcb> +::write_full_cells(std::ostream & os, std::map<Vertex_const_handle, int> & index_of_vertex) const +{ + std::map<Full_cell_const_handle, int> index_of_full_cell; + + std::size_t m = number_of_full_cells(); + + if( is_ascii(os) ) + os << std::endl << m; + else + write(os, m, io_Read_write()); + + const int cur_dim = current_dimension(); + // write the vertex indices of each full_cell + int i = 0; + for( Full_cell_const_iterator it = full_cells_begin(); it != full_cells_end(); ++it ) + { + index_of_full_cell[it] = i++; + if( is_ascii(os) ) + os << std::endl; + for( int j = 0; j <= cur_dim; ++j ) + { + if( is_ascii(os) ) + os << ' ' << index_of_vertex[it->vertex(j)]; + else + write(os, index_of_vertex[it->vertex(j)]); + } + // write other non-combinatorial information for the full_cells + os << (*it); + } + + CGAL_assertion( (std::size_t) i == m ); + + // write the neighbors of each full_cell + if( is_ascii(os) ) + for( Full_cell_const_iterator it = full_cells_begin(); it != full_cells_end(); ++it ) + { + os << std::endl; + for( int j = 0; j <= cur_dim; ++j ) + os << ' ' << index_of_full_cell[it->neighbor(j)]; + } + else + for( Full_cell_const_iterator it = full_cells_begin(); it != full_cells_end(); ++it ) + { + for( int j = 0; j <= cur_dim; ++j ) + write(os, index_of_full_cell[it->neighbor(j)]); + } + + return os; +} + +// = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = + +// FUNCTIONS THAT ARE NOT MEMBER FUNCTIONS: + +template<class Dimen, class Vb, class Fcb> +std::istream & +operator>>(std::istream & is, Triangulation_data_structure<Dimen, Vb, Fcb> & tr) + // reads : + // - the dimensions (maximal and current) + // - the number of finite vertices + // - the non combinatorial information on vertices (point, etc) + // - the number of full_cells + // - the full_cells by the indices of their vertices in the preceding list + // of vertices, plus the non combinatorial information on each full_cell + // - the neighbors of each full_cell by their index in the preceding list +{ + typedef Triangulation_data_structure<Dimen, Vb, Fcb> TDS; + typedef typename TDS::Vertex_handle Vertex_handle; + + // read current dimension and number of vertices + std::size_t n; + int cd; + if( is_ascii(is) ) + is >> cd >> n; + else + { + read(is, cd); + read(is, n, io_Read_write()); + } + + CGAL_assertion_msg( cd <= tr.maximal_dimension(), "input Triangulation_data_structure has too high dimension"); + + tr.clear(); + tr.set_current_dimension(cd); + + if( n == 0 ) + return is; + + std::vector<Vertex_handle> vertices; + vertices.resize(n); + + // read the vertices: + std::size_t i(0); + while( i < n ) + { + vertices[i] = tr.new_vertex(); + is >> (*vertices[i]); // read a vertex + ++i; + } + + // now, read the combinatorial information + return tr.read_full_cells(is, vertices); +} + +template<class Dimen, class Vb, class Fcb> +std::ostream & +operator<<(std::ostream & os, const Triangulation_data_structure<Dimen, Vb, Fcb> & tr) + // writes : + // - the dimensions (maximal and current) + // - the number of finite vertices + // - the non combinatorial information on vertices (point, etc) + // - the number of full cells + // - the full cells by the indices of their vertices in the preceding list + // of vertices, plus the non combinatorial information on each full_cell + // - the neighbors of each full_cell by their index in the preceding list +{ + typedef Triangulation_data_structure<Dimen, Vb, Fcb> TDS; + typedef typename TDS::Vertex_const_handle Vertex_handle; + typedef typename TDS::Vertex_const_iterator Vertex_iterator; + + // outputs dimension and number of vertices + std::size_t n = tr.number_of_vertices(); + if( is_ascii(os) ) + os << tr.current_dimension() << std::endl << n; + else + { + write(os, tr.current_dimension()); + write(os, n, io_Read_write()); + } + + if( n == 0 ) + return os; + + // write the vertices + std::map<Vertex_handle, int> index_of_vertex; + int i = 0; + for( Vertex_iterator it = tr.vertices_begin(); it != tr.vertices_end(); ++it, ++i ) + { + os << *it; // write the vertex + if (is_ascii(os)) + os << std::endl; + index_of_vertex[it] = i; + } + CGAL_assertion( (std::size_t) i == n ); + + // output the combinatorial information + return tr.write_full_cells(os, index_of_vertex); +} + +} //namespace CGAL + +#endif // CGAL_TRIANGULATION_DATA_STRUCTURE_H |