// Copyright (c) 2011 CNRS and LIRIS' Establishments (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 Lesser 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) : Guillaume Damiand // #ifndef CGAL_LINEAR_CELL_COMPLEX_CONSTRUCTORS_H #define CGAL_LINEAR_CELL_COMPLEX_CONSTRUCTORS_H 1 #include #include #include #include #include #include #include #include #include #include #include #include namespace CGAL { /** @file Linear_cell_complex_constructors.h * Some construction operations for a linear cell complex from other * CGAL data structures. */ /** Import an embedded plane graph read into a flux into a * linear cell complex. * @param alcc the linear cell complex where the graph will be imported. * @param ais the istream where read the graph. * @return A dart created during the convertion. */ template< class LCC > typename LCC::Dart_handle import_from_plane_graph(LCC& alcc, std::istream& ais) { CGAL_static_assertion( LCC::dimension>=2 && LCC::ambient_dimension==2 ); typedef typename LCC::Dart_handle Dart_handle; typedef typename LCC::Traits::Direction_2 Direction; typedef typename std::list::iterator List_iterator; typedef typename std::map::iterator LCC_iterator; // Arrays of vertices std::vector< typename LCC::Vertex_attribute_handle > initVertices; std::vector< std::list > testVertices; std::string txt; typename LCC::FT x, y; Dart_handle d1 = alcc.null_handle, d2 = alcc.null_handle; unsigned int v1, v2; unsigned int nbSommets = 0; unsigned int nbAretes = 0; ais >> nbSommets >> nbAretes; while (nbSommets > 0) { if (!ais.good()) { std::cout << "Problem: file does not contain enough vertices." << std::endl; return alcc.null_handle; } ais >> iformat(x) >> iformat(y); initVertices.push_back(alcc.create_vertex_attribute (typename LCC::Point(x, y))); testVertices.push_back(std::list()); --nbSommets; } while (nbAretes > 0) { if (!ais.good()) { std::cout << "Problem: file does not contain enough edges." << std::endl; return alcc.null_handle; } // We read an egde (given by the number of its two vertices). ais >> v1 >> v2; --nbAretes; CGAL_assertion(v1 < initVertices.size()); CGAL_assertion(v2 < initVertices.size()); d1 = alcc.create_dart(initVertices[v1]); d2 = alcc.create_dart(initVertices[v2]); alcc.template link_beta<2>(d1, d2); testVertices[v1].push_back(d1); testVertices[v2].push_back(d2); } // LCC associating directions and darts. std::map tabDart; List_iterator it; LCC_iterator it2; Dart_handle first = alcc.null_handle; Dart_handle prec = alcc.null_handle; typename LCC::Point sommet1, sommet2; for (unsigned int i = 0; i < initVertices.size(); ++i) { it = testVertices[i].begin(); if (it != testVertices[i].end()) // Si la liste n'est pas vide. { // 1. We insert all the darts and sort them depending on the direction tabDart.clear(); sommet1 = alcc.point(*it); sommet2 = alcc.point(alcc.beta(*it,2)); tabDart.insert(std::pair (typename LCC::Traits::Construct_direction_2() (typename LCC::Traits::Construct_vector() (sommet1,sommet2)), *it)); ++it; while (it != testVertices[i].end()) { sommet2 = alcc.point(alcc.beta(*it,2)); tabDart.insert(std::pair (typename LCC::Traits::Construct_direction_2() (typename LCC::Traits::Construct_vector() (sommet1,sommet2)), *it)); ++it; } // 2. We run through the array of darts and 1 links darts. it2 = tabDart.begin(); first = it2->second; prec = first; ++it2; while (it2 != tabDart.end()) { alcc.template link_beta<0>(prec, alcc.beta(it2->second,2)); prec = it2->second; ++it2; } alcc.template link_beta<0>(prec, alcc.beta(first,2)); } } // We return a dart from the imported object. return first; } /** Convert a given Triangulation_2 into a 2D linear cell complex. * @param alcc the used linear cell complex. * @param atr the Triangulation_2. * @param aface_to_dart a pointer to a std::map associating to each * triangle of atr a corresponding dart in alcc. Not used if NULL. * @return A dart incident to the infinite vertex. */ template < class LCC, class Triangulation > typename LCC::Dart_handle import_from_triangulation_2 (LCC& alcc, const Triangulation &atr, std::map* aface_to_dart=NULL) { CGAL_static_assertion( LCC::dimension>=2 && LCC::ambient_dimension==2 ); // Case of empty triangulations. if (atr.number_of_vertices() == 0) return LCC::null_handle; // Check the dimension. if (atr.dimension() != 2) return LCC::null_handle; CGAL_assertion(atr.is_valid()); typedef typename Triangulation::Vertex_handle TVertex_handle; typedef typename Triangulation::All_vertices_iterator TVertex_iterator; typedef typename Triangulation::All_faces_iterator TFace_iterator; typedef typename std::map < TFace_iterator, typename LCC::Dart_handle >::iterator itmap_tcell; // Create vertices in the map and associate in a map // TVertex_handle and vertices in the map. std::map< TVertex_handle, typename LCC::Vertex_attribute_handle > TV; for (TVertex_iterator itv = atr.all_vertices_begin(); itv != atr.all_vertices_end(); ++itv) { TV[itv] = alcc.create_vertex_attribute(itv->point()); } // Create the triangles and create a map to link Cell_iterator // and triangles. TFace_iterator it; std::map TC; std::map* mytc = (aface_to_dart==NULL?&TC:aface_to_dart); itmap_tcell maptcell_it; typename LCC::Dart_handle res=LCC::null_handle, dart=LCC::null_handle; typename LCC::Dart_handle cur=LCC::null_handle, neighbor=LCC::null_handle; for (it = atr.all_faces_begin(); it != atr.all_faces_end(); ++it) { /* if (it->vertex(0) != atr.infinite_vertex() && it->vertex(1) != atr.infinite_vertex() && it->vertex(2) != atr.infinite_vertex() && it->vertex(3) != atr.infinite_vertex()) */ { res = alcc.make_triangle(TV[it->vertex(0)], TV[it->vertex(1)], TV[it->vertex(2)]); if ( dart==LCC::null_handle ) { if ( it->vertex(0) == atr.infinite_vertex() ) dart = res; else if ( it->vertex(1) == atr.infinite_vertex() ) dart = alcc.beta(res,1); else if ( it->vertex(2) == atr.infinite_vertex() ) dart = alcc.beta(res,0); } for (unsigned int i=0; i<3; ++i) { switch (i) { case 0: cur = alcc.beta(res,1); break; case 1: cur = alcc.beta(res,0); break; case 2: cur = res; break; } maptcell_it = mytc->find(it->neighbor(i)); if (maptcell_it != mytc->end()) { switch (atr.mirror_index(it,i) ) { case 0: neighbor = alcc.beta(maptcell_it->second,1); break; case 1: neighbor = alcc.beta(maptcell_it->second,0); break; case 2: neighbor = maptcell_it->second; break; } alcc.template topo_sew<2>(cur, neighbor); } } (*mytc)[it] = res; } } CGAL_assertion(dart!=LCC::null_handle); return dart; } /** Convert a given Triangulation_3 into a 3D linear cell complex. * @param alcc the used linear cell complex. * @param atr the Triangulation_3. * @param avol_to_dart a pointer to a std::map associating to each * tetrahedron of atr a corresponding dart in alcc. Not used if NULL. * @return A dart incident to the infinite vertex. */ template < class LCC, class Triangulation > typename LCC::Dart_handle import_from_triangulation_3 (LCC& alcc, const Triangulation &atr, std::map* avol_to_dart=NULL) { CGAL_static_assertion( LCC::dimension>=3 && LCC::ambient_dimension==3 ); // Case of empty triangulations. if (atr.number_of_vertices() == 0) return LCC::null_handle; // Check the dimension. if (atr.dimension() != 3) return LCC::null_handle; CGAL_assertion(atr.is_valid()); typedef typename Triangulation::Vertex_handle TVertex_handle; typedef typename Triangulation::Vertex_iterator TVertex_iterator; typedef typename Triangulation::Cell_iterator TCell_iterator; typedef typename std::map < TCell_iterator, typename LCC::Dart_handle >::iterator itmap_tcell; // Create vertices in the map and associate in a map // TVertex_handle and vertices in the map. std::map< TVertex_handle, typename LCC::Vertex_attribute_handle > TV; for (TVertex_iterator itv = atr.vertices_begin(); itv != atr.vertices_end(); ++itv) { TV[itv] = alcc.create_vertex_attribute(itv->point()); } // Create the tetrahedron and create a map to link Cell_iterator // and tetrahedron. TCell_iterator it; std::map TC; std::map* mytc = (avol_to_dart==NULL?&TC:avol_to_dart); itmap_tcell maptcell_it; typename LCC::Dart_handle res=LCC::null_handle, dart=LCC::null_handle; typename LCC::Dart_handle cur=LCC::null_handle, neighbor=LCC::null_handle; for (it = atr.cells_begin(); it != atr.cells_end(); ++it) { /* if (it->vertex(0) != atr.infinite_vertex() && it->vertex(1) != atr.infinite_vertex() && it->vertex(2) != atr.infinite_vertex() && it->vertex(3) != atr.infinite_vertex()) */ { res = alcc.make_tetrahedron(TV[it->vertex(0)], TV[it->vertex(1)], TV[it->vertex(2)], TV[it->vertex(3)]); if ( dart==LCC::null_handle ) { if ( it->vertex(0) == atr.infinite_vertex() ) dart = res; else if ( it->vertex(1) == atr.infinite_vertex() ) dart = alcc.beta(res, 1); else if ( it->vertex(2) == atr.infinite_vertex() ) dart = alcc.beta(res, 1, 1); else if ( it->vertex(3) == atr.infinite_vertex() ) dart = alcc.beta(res, 2, 0); } for (unsigned int i = 0; i < 4; ++i) { switch (i) { case 0: cur = alcc.beta(res, 1, 2); break; case 1: cur = alcc.beta(res, 0, 2); break; case 2: cur = alcc.beta(res, 2); break; case 3: cur = res; break; } maptcell_it = mytc->find(it->neighbor(i)); if (maptcell_it != mytc->end()) { switch (atr.mirror_index(it,i) ) { case 0: neighbor = alcc.beta(maptcell_it->second, 1, 2); break; case 1: neighbor = alcc.beta(maptcell_it->second, 0, 2); break; case 2: neighbor = alcc.beta(maptcell_it->second, 2); break; case 3: neighbor = maptcell_it->second; break; } while (alcc.temp_vertex_attribute(neighbor) != alcc.temp_vertex_attribute(alcc.other_extremity(cur)) ) neighbor = alcc.beta(neighbor,1); alcc.template topo_sew<3>(cur, neighbor); } } (*mytc)[it] = res; } } CGAL_assertion(dart!=LCC::null_handle); return dart; } /** Import a given Polyhedron_3 into a Linear_cell_complex. * @param alcc the linear cell complex where Polyhedron_3 will be converted. * @param apoly the Polyhedron. * @return A dart created during the convertion. */ template< class LCC, class Polyhedron > typename LCC::Dart_handle import_from_polyhedron_3(LCC& alcc, const Polyhedron &apoly) { CGAL_static_assertion( LCC::dimension>=2 && LCC::ambient_dimension==3 ); typedef typename Polyhedron::Halfedge_const_handle Halfedge_handle; typedef typename Polyhedron::Facet_const_iterator Facet_iterator; typedef typename Polyhedron::Halfedge_around_facet_const_circulator HF_circulator; typedef std::map < Halfedge_handle, typename LCC::Dart_handle> Halfedge_handle_map; typedef typename Halfedge_handle_map::iterator itmap_hds; Halfedge_handle_map TC; itmap_hds it; typename LCC::Dart_handle d = LCC::null_handle, prev = LCC::null_handle; typename LCC::Dart_handle firstFacet = LCC::null_handle, firstAll = LCC::null_handle; // First traversal to build the darts and link them. for (Facet_iterator i = apoly.facets_begin(); i != apoly.facets_end(); ++i) { HF_circulator j = i->facet_begin(); prev = LCC::null_handle; do { d = alcc.create_dart(); TC[j] = d; if (prev != LCC::null_handle) alcc.template link_beta<1>(prev, d); else firstFacet = d; it = TC.find(j->opposite()); if (it != TC.end()) alcc.template link_beta<2>(d, it->second); prev = d; } while (++j != i->facet_begin()); alcc.template link_beta<1>(prev, firstFacet); if (firstAll == LCC::null_handle) firstAll = firstFacet; } // Second traversal to update the geometry. // We run one again through the facets of the HDS. for (Facet_iterator i = apoly.facets_begin(); i != apoly.facets_end(); ++i) { HF_circulator j = i->facet_begin(); do { d = TC[j]; // Get the dart associated to the Halfedge if (alcc.temp_vertex_attribute(d) == LCC::null_handle) { alcc.set_vertex_attribute (d, alcc.create_vertex_attribute(j->opposite()->vertex()->point())); } } while (++j != i->facet_begin()); } return firstAll; } template < class LCC > void load_off(LCC& alcc, std::istream& in) { File_header_OFF m_file_header; File_scanner_OFF scanner( in, m_file_header.verbose()); if ( ! in) return; m_file_header = scanner; // Remember file header after return. Linear_cell_complex_incremental_builder_3 B( alcc); B.begin_surface( scanner.size_of_vertices(), scanner.size_of_facets(), scanner.size_of_halfedges()); typedef typename LCC::Point Point; // read in all vertices std::size_t i; for ( i = 0; i < scanner.size_of_vertices(); i++) { Point p; file_scan_vertex( scanner, p); B.add_vertex( p); scanner.skip_to_next_vertex( i); } /* TODO rollback if ( ! in || B.error()) { B.rollback(); in.clear( std::ios::badbit); return; } */ // read in all facets for ( i = 0; i < scanner.size_of_facets(); i++) { B.begin_facet(); std::size_t no; scanner.scan_facet( no, i); /* TODO manage errors if( ! in || B.error() || no < 3) { if ( scanner.verbose()) { std::cerr << " " << std::endl; std::cerr << "Polyhedron_scan_OFF::" << std::endl; std::cerr << "operator()(): input error: facet " << i << " has less than 3 vertices." << std::endl; } B.rollback(); in.clear( std::ios::badbit); return; } */ for ( std::size_t j = 0; j < no; j++) { std::size_t index; scanner.scan_facet_vertex_index( index, i); B.add_vertex_to_facet( index); } B.end_facet(); scanner.skip_to_next_facet( i); } /* TODO manage errors if ( ! in || B.error()) { B.rollback(); in.clear( std::ios::badbit); return; } if ( B.check_unconnected_vertices()) { if ( ! B.remove_unconnected_vertices()) { if ( scanner.verbose()) { std::cerr << " " << std::endl; std::cerr << "Polyhedron_scan_OFF::" << std::endl; std::cerr << "operator()(): input error: cannot " "succesfully remove isolated vertices." << std::endl; } B.rollback(); in.clear( std::ios::badbit); return; } }*/ B.end_surface(); } /** Convert a Polyhedron_3 read into a flux into 3D linear cell complex. * @param alcc the linear cell complex where Polyhedron_3 will be converted. * @param ais the istream where read the Polyhedron_3. * @return A dart created during the convertion. */ template < class LCC > typename LCC::Dart_handle import_from_polyhedron_3_flux(LCC& alcc, std::istream& ais) { if (!ais.good()) { std::cout << "Error reading flux." << std::endl; return LCC::null_handle; } CGAL::Polyhedron_3 P; ais >> P; return import_from_polyhedron_3 > (alcc, P); } /** Export the alcc in off file format. If dimension>2, export all faces but only once. */ template < class LCC > void write_off(LCC& alcc, std::ostream& out) { File_header_OFF header(false); header.set_binary(is_binary( out)); header.set_no_comments(!is_pretty( out)); File_writer_OFF writer( header); writer.header().set_polyhedral_surface(true); writer.header().set_halfedges( alcc.number_of_darts()); // Print header. writer.write_header( out, alcc.number_of_vertex_attributes(), alcc.number_of_darts(), alcc.template one_dart_per_cell<2>().size() ); typedef typename LCC::Vertex_attribute_range::iterator VCI; VCI vit, vend = alcc.vertex_attributes().end(); for ( vit = alcc.vertex_attributes().begin(); vit!=vend; ++vit ) { writer.write_vertex( ::CGAL::to_double( vit->point().x()), ::CGAL::to_double( vit->point().y()), ::CGAL::to_double( vit->point().z())); } typedef Inverse_index< VCI > Index; Index index( alcc.vertex_attributes().begin(), alcc.vertex_attributes().end()); writer.write_facet_header(); typename LCC::size_type m = alcc.get_new_mark(); for ( typename LCC::Dart_range::iterator itall = alcc.darts().begin(), itallend = alcc.darts().end(); itall!=itallend; ++itall ) { if ( !alcc.is_marked(itall, m) ) { std::size_t n = 0; // First we count the number of vertices of the face. for ( typename LCC::template Dart_of_orbit_range<1>::iterator itf=alcc.template darts_of_orbit<1>(itall).begin(), itfend=alcc.template darts_of_orbit<1>(itall).end(); itf!=itfend; ++itf, ++n ); CGAL_assertion( n>=3 ); writer.write_facet_begin(n); // Second we write the indices of vertices. for ( typename LCC::template Dart_of_orbit_range<1>::iterator itf=alcc.template darts_of_orbit<1>(itall).begin(), itfend=alcc.template darts_of_orbit<1>(itall).end(); itf!=itfend; ++itf ) { // TODO case with index writer.write_facet_vertex_index(index[VCI(alcc.vertex_attribute(itf))]); for ( typename LCC::template Dart_of_involution_basic_range<1>::iterator itinv=alcc.template darts_of_involution_basic<1>(itf, m).begin(), itinvend=alcc.template darts_of_involution_basic<1>(itf, m).end(); itinv!=itinvend; ++itinv ) alcc.mark(itinv, m); } writer.write_facet_end(); } } writer.write_footer(); alcc.free_mark(m); } } // namespace CGAL #endif // CGAL_LINEAR_CELL_COMPLEX_CONSTRUCTORS_H // // EOF //