// Copyright (c) 2005,2007,2009,2010,2011 Tel-Aviv University (Israel). // 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) : Ron Wein // Ophir Setter #ifndef CGAL_GRAPH_TRAITS_DUAL_ARRANGEMENT_2_H #define CGAL_GRAPH_TRAITS_DUAL_ARRANGEMENT_2_H /*! \file * Definition of the specialized Dual class, * and the specialized boost::graph_traits >class. */ // include this to avoid a VC15 warning #include #include #include namespace CGAL { // Forward declaration. template class Dual; /*! \class * Specilaization of the Dual<> template for Arrangement_on_surface_2. */ template class Dual > { public: typedef GeomTraits_ Geometry_traits_2; typedef TopTraits_ Topology_traits; typedef CGAL::Arrangement_on_surface_2 Arrangement_on_surface_2; typedef typename Arrangement_on_surface_2::Size Size; typedef typename Arrangement_on_surface_2::Face_handle Vertex_handle; typedef typename Arrangement_on_surface_2::Halfedge_handle Edge_handle; typedef typename Arrangement_on_surface_2::Face_iterator Vertex_iterator; typedef typename Arrangement_on_surface_2::Halfedge_iterator Edge_iterator; protected: typedef typename Arrangement_on_surface_2::Face_handle Face_handle; typedef typename Arrangement_on_surface_2::Ccb_halfedge_circulator Ccb_halfedge_circulator; typedef typename Arrangement_on_surface_2::Outer_ccb_iterator Outer_ccb_iterator; typedef typename Arrangement_on_surface_2::Inner_ccb_iterator Inner_ccb_iterator; /*! \class * Iterator over the neighbors of a dual vertex (a face in the primal * arrangement). * These neighbors are the adjacent faces along the outer boundaries of the * face and its inner boundaries. */ class Face_neighbor_iterator { typedef Face_neighbor_iterator Self; public: typedef std::forward_iterator_tag iterator_category; typedef Edge_handle value_type; typedef value_type reference; typedef value_type* pointer; typedef int difference_type; private: Outer_ccb_iterator _outer_ccb_iter; Inner_ccb_iterator _inner_ccb_iter; Ccb_halfedge_circulator _ccb_curr; Ccb_halfedge_circulator _ccb_first; Face_handle _face; bool _out; Edge_handle _hh; bool _end; public: /*! Default constructor. */ Face_neighbor_iterator () : _end (true) {} /*! * Constructor. * \param face The face (dual vertex). * \param out_edges Do we need the outgoing or the ingoing halfedges. * \param start Should we start traversing the edges. * If false, we construct a past-the-end iterator. */ Face_neighbor_iterator (Face_handle face, bool out_edges, bool start) : _face (face), _out (out_edges), _end (! start) { CGAL_precondition (! face->is_fictitious()); if (start) { _outer_ccb_iter = _face->outer_ccbs_begin(); _inner_ccb_iter = _face->inner_ccbs_begin(); if (_outer_ccb_iter != _face->outer_ccbs_end()) { // Start from the first outer CCB, if one exists. _ccb_curr = _ccb_first = *_outer_ccb_iter; } else if (_inner_ccb_iter != face->inner_ccbs_end()) { // Otherwise, start from the first inner CCB. _ccb_curr = _ccb_first = *_inner_ccb_iter; } else { // In this case there are no CCBs to traverse: _end = true; return; } _hh = this->_dereference(); // In case the incident face of the twin halfedge is fictitious, // skip it and proceed to the next edge. if (_hh->is_fictitious()) ++(*this); } else // end iterator. { _outer_ccb_iter = _face->outer_ccbs_end(); _inner_ccb_iter = _face->inner_ccbs_end(); } } /*! Equality operators. */ bool operator== (const Self& it) const { return (this->_equal(it)); } bool operator!= (const Self& it) const { return (! this->_equal(it)); } /*! Dereference operators. */ reference operator* () const { return (_hh); } pointer operator-> () const { return (&_hh); } /* Increment operators. */ Self& operator++ () { do { this->_increment(); if (_end) return (*this); _hh = this->_dereference(); } while (_hh->is_fictitious()); return (*this); } Self operator++ (int ) { Self tmp = *this; do { this->_increment(); if (_end) return (tmp); _hh = this->_dereference(); } while (_hh->is_fictitious()); return (tmp); } private: /*! Check two iterators for equality. */ bool _equal (const Self& it) const { return (_out == it._out && _face == it._face && ((_end && it._end) || (_outer_ccb_iter == it._outer_ccb_iter && _inner_ccb_iter == it._inner_ccb_iter && _ccb_curr == it._ccb_curr))); } /*! Derefernce the current circulator. */ Edge_handle _dereference () const { if (_out) return (_ccb_curr); else return (_ccb_curr->twin()); } // Increments of the iterator. void _increment () { CGAL_assertion (! _end); // If we have not traversed the entire CCB in full, move to the next // halfedge along the current CCB. ++_ccb_curr; if (_ccb_curr != _ccb_first) return; // In this case we have completed the current CCB and we have to move // to the next one. if (_outer_ccb_iter != _face->outer_ccbs_end()) { // Try to move to the next outer CCB. ++_outer_ccb_iter; if (_outer_ccb_iter != _face->outer_ccbs_end()) { _ccb_curr = _ccb_first = *_outer_ccb_iter; return; } // In this case we start traversing the inner CCBs. if (_inner_ccb_iter != _face->inner_ccbs_end()) { CGAL_assertion (_inner_ccb_iter == _face->inner_ccbs_begin()); // Otherwise, start from the first inner CCB. _ccb_curr = _ccb_first = *_inner_ccb_iter; return; } } else if (_inner_ccb_iter != _face->inner_ccbs_end()) { // In this case we have already traversed all outer CCBs (and at least // one inner CCB), so we try to move to the next inner CCB. ++_inner_ccb_iter; if (_inner_ccb_iter != _face->inner_ccbs_end()) { // Otherwise, start from the first inner CCB. _ccb_curr = _ccb_first = *_inner_ccb_iter; return; } } // In this case we finished traversing all outer and inner CCBs: _end = true; return; } }; // Data members: mutable Arrangement_on_surface_2 *p_arr; // The primal arrangement. public: typedef Face_neighbor_iterator Incident_edge_iterator; /*! Default constructor. */ Dual () : p_arr (NULL) {} /*! Constructor from an arrangement. */ Dual (const Arrangement_on_surface_2& arr) : p_arr (const_cast (&arr)) {} /*! Get the primal arrangement (const version). */ const Arrangement_on_surface_2* arrangement () const { return (p_arr); } /*! Get the primal arrangement (non-const version). */ Arrangement_on_surface_2* arrangement () { return (p_arr); } /*! Get the number of vertices (face of the primal arrangement). */ Size number_of_vertices () const { return (p_arr->number_of_faces()); } /*! Traverse the vertices (faces of the primal arrangement). */ Vertex_iterator vertices_begin () const { return (p_arr->faces_begin()); } Vertex_iterator vertices_end () const { return (p_arr->faces_end()); } /*! Get the number of edges. */ Size number_of_edges () const { return (p_arr->number_of_halfedges()); } /*! Traverse the edges. */ Edge_iterator edges_begin () const { return (p_arr->halfedges_begin()); } Edge_iterator edges_end () const { return (p_arr->halfedges_end()); } /*! * Get the dual vertex-degree (number of edges forming the face boundary). */ Size degree (Vertex_handle v) const { Incident_edge_iterator begin = Incident_edge_iterator (v, true, true); Incident_edge_iterator end = Incident_edge_iterator (v, false, true); Size deg = 0; while (begin != end) { deg++; ++begin; } return (deg); } /*! Traverse the outgoing edges of a given vertex. */ Incident_edge_iterator out_edges_begin (Vertex_handle v) const { return (Incident_edge_iterator (v, true, true)); } Incident_edge_iterator out_edges_end (Vertex_handle v) const { return (Incident_edge_iterator (v, true, false)); } /*! Traverse the ingoing edges of a given vertex. */ Incident_edge_iterator in_edges_begin (Vertex_handle v) const { return (Incident_edge_iterator (v, false, true)); } Incident_edge_iterator in_edges_end (Vertex_handle v) const { return (Incident_edge_iterator (v, false, false)); } }; /*! \class * Specilaization of the Dual<> template for Arrangement_2. */ template class Dual > : public Dual::Geometry_traits_2, typename CGAL::Arrangement_2::Topology_traits> > { typedef Traits_ Traits_2; typedef Dcel_ Dcel; typedef Dual::Geometry_traits_2, typename CGAL::Arrangement_2::Topology_traits> > Base; public: /*! Default constructor. */ Dual () : Base() {} /*! Constructor from an arrangement. */ Dual (const CGAL::Arrangement_2& arr) : Base (arr) {} }; } //namespace CGAL #include #include namespace boost { /*! \class * Specialization of the BGL graph-traits template, which serve as a dual * adapter for Arrangment_on_surface_2, where the valid arrangement faces * correspond to graph verices, and two graph vertices are connected if the * two corrsponding faces are adjacent. * We consider the graph as directed. We also allow parallel edges, as two * faces may have more than one common edges. */ template class graph_traits > > { public: typedef GeomTraits_ Geometry_traits_2; typedef TopTraits_ Topology_traits; typedef CGAL::Arrangement_on_surface_2 Arrangement_on_surface_2; typedef CGAL::Dual Dual_arr_2; private: typedef typename Dual_arr_2::Vertex_iterator Vertex_iterator; typedef typename Dual_arr_2::Edge_iterator Edge_iterator; typedef typename Dual_arr_2::Incident_edge_iterator Incident_edge_iterator; /*! \struct * Define the arrangement traversal category, which indicates the arrangement * models the BidirectionalGraph concept and the VertexListGraph and * EdgeListGraph concepts. */ struct Dual_arr_traversal_category : public virtual boost::bidirectional_graph_tag, // This tag refines the // incidence_graph_tag. public virtual boost::vertex_list_graph_tag, // Can iterate over vertices. public virtual boost::edge_list_graph_tag // Can iterate over edges. {}; public: // Types required of the Graph concept: typedef typename Dual_arr_2::Vertex_handle vertex_descriptor; typedef boost::directed_tag directed_category; typedef boost::allow_parallel_edge_tag edge_parallel_category; typedef Dual_arr_traversal_category traversal_category; // Types required by the IncidenceGraph concept: typedef typename Dual_arr_2::Edge_handle edge_descriptor; typedef Incident_edge_iterator out_edge_iterator; typedef typename Dual_arr_2::Size degree_size_type; // Types required by the BidirectionalGraph concept: typedef Incident_edge_iterator in_edge_iterator; // Types required by the VertexListGraph concept: typedef boost::counting_iterator vertex_iterator; typedef typename Dual_arr_2::Size vertices_size_type; // Types required by the EdgeListGraph concept: typedef boost::counting_iterator edge_iterator; typedef typename Dual_arr_2::Size edges_size_type; // Types not required by any of these concepts: typedef void adjacency_iterator; }; /*! \class * Specialization of the BGL graph-traits template, which serve as a dual * adapter for Arrangment_2. */ template class graph_traits > > : public graph_traits::Geometry_traits_2, typename CGAL::Arrangement_2::Topology_traits> > > {}; } // namespace boost namespace CGAL { // Functions required by the IncidenceGraph concept: // ------------------------------------------------- /*! * Get the out-degree of a vertex in a given dual arrangement. * \param v The vertex. * \param darr The dual arrangement. * \param Number of halfedges around the boundary of the primal face. */ template typename boost::graph_traits > >::degree_size_type out_degree(typename boost::graph_traits > >:: vertex_descriptor v, const CGAL::Dual >& darr) { return darr.degree (v); } /*! * Return a range of the out-edges of a vertex given by its descriptor and the * dual arrangement it belongs to. * \param v The vertex. * \param darr The dual arrangement. * \return A pair of out-edges iterators. */ template std::pair > >:: out_edge_iterator, typename boost::graph_traits > >:: out_edge_iterator> out_edges(typename boost::graph_traits > >:: vertex_descriptor v, const CGAL::Dual >& darr) { return std::make_pair (darr.out_edges_begin (v), darr.out_edges_end (v)); } /*! * Get the source vertex of a dual arrangement edge. * \param e The edge. * \param darr The dual arrangement. * \return The incident face of e in the primal arrangement. */ template typename boost::graph_traits > >::vertex_descriptor source(typename boost::graph_traits > >:: edge_descriptor e, const CGAL::Dual >& /* darr */) { return e->face(); } /*! * Get the target vertex of a dual arrangement edge. * \param e The edge. * \param darr The dual arrangement. * \return The incident face of e's twin in the primal arrangement. */ template typename boost::graph_traits > >::vertex_descriptor target(typename boost::graph_traits > >:: edge_descriptor e, const CGAL::Dual >& /* darr */) { return e->twin()->face(); } // Functions required by the BidirectionalGraph concept: // ----------------------------------------------------- /*! * Get the in-degree of a vertex in a given dual arrangement. * \param v The vertex. * \param darr The dual arrangement. * \param Number of halfedges around the boundary of the primal face. */ template typename boost::graph_traits > >::degree_size_type in_degree(typename boost::graph_traits > >:: vertex_descriptor v, const CGAL::Dual >& darr) { return darr.degree (v); } /*! * Return a range of the in-edges of a vertex given by its descriptor and the * dual arrangement it belongs to. * \param v The vertex. * \param darr The dual arrangement. * \return A pair of in-edges iterators. */ template std::pair > >:: in_edge_iterator, typename boost::graph_traits > >:: in_edge_iterator> in_edges(typename boost::graph_traits > >:: vertex_descriptor v, const CGAL::Dual >& darr) { return std::make_pair (darr.in_edges_begin (v), darr.in_edges_end (v)); } /*! * Get the degree of a vertex in a given dual arrangement. * \param v The vertex. * \param darr The dual arrangement. * \param Number of ingoing and outgoing halfedges incident to v. */ template typename boost::graph_traits > >::degree_size_type degree(typename boost::graph_traits > >:: vertex_descriptor v, const CGAL::Dual >& darr) { return (2 * darr.degree (v)); } // Functions required by the VertexListGraph concept: // -------------------------------------------------- /*! * Get the number of vertices in the given dual arrangement. * \param darr The dual arrangement. * \return Number of faces in the primal arrangement. */ template typename boost::graph_traits > >::vertices_size_type num_vertices(const CGAL::Dual >& darr) { return darr.number_of_vertices(); } /*! * Get the range of vertices of the given dual arrangement. * \param darr The dual arrangement. * \return A pair of vertex iterators. */ template std::pair > >:: vertex_iterator, typename boost::graph_traits > >:: vertex_iterator> vertices (const CGAL::Dual >& darr) { return std::make_pair (darr.vertices_begin(), darr.vertices_end()); } // Functions required by the EdgeListGraph concept: // ------------------------------------------------ /*! * Get the number of edges in the given dual arrangement. * \param darr The dual arrangement. * \return Number of halfedges in the primal arrangement. */ template typename boost::graph_traits > >::edges_size_type num_edges(const CGAL::Dual >& darr) { return darr.number_of_edges(); } /*! * Get the range of edges of the given dual arrangement. * \param darr The dual arrangement. * \return A pair of edge iterators. */ template std::pair > >:: edge_iterator, typename boost::graph_traits > >:: edge_iterator> edges (const CGAL::Dual >& darr) { return std::make_pair (darr.edges_begin(), darr.edges_end()); } } //namespace CGAL #endif