CGAL users discussion list

["Wesley Smith" <>]

I use this functor for a similar purpose.  It gets all incident edges
which is essentially the same thing.  It uses the inconflict flag to
mark visited vertices.  This one is parameterized on my voronoi 3d
class, so you'll need to adjust the typedefs.

wes


template < class VDA = void >
struct Finder_utils_base
{
        public:
        
        enum flags {
                EDGE_01 = 1,
                EDGE_02 = 2,
                EDGE_03 = 4,
                EDGE_12 = 8,
                EDGE_13 = 16,
                EDGE_23 = 32,
                UNDEFINED = 64,
                VISITED = 128
        };

        static const unsigned char edge_flags[4][4];
};

template < class VDA >
const unsigned char Finder_utils_base<VDA>::edge_flags[4][4] =
{
        {UNDEFINED,             EDGE_01,        EDGE_02,        EDGE_03},
        {EDGE_01,               UNDEFINED,      EDGE_12,        EDGE_13},
        {EDGE_02,               EDGE_12,        UNDEFINED,      EDGE_23},
        {EDGE_03,               EDGE_13,        EDGE_23,        UNDEFINED}
};

template<class VDA>
class Find_incident_edges
: public Finder_utils_base<>
{
        private:
                typedef typename VDA::Delaunay_graph                    T;

        public:
                typedef typename VDA::Delaunay_graph::Cell_handle             
                          Delaunay_cell_handle;
                typedef typename
VDA::Delaunay_graph::Vertex_handle                                      
Delaunay_vertex_handle;
                typedef typename
VDA::Delaunay_graph::Cell_circulator                            
Delaunay_cell_circulator;
                typedef typename VDA::Delaunay_graph::Edge                    
                                  Delaunay_edge;
                
                template <class OutputIterator>
                OutputIterator
                operator()(const VDA* vda, const Delaunay_vertex_handle& v,
OutputIterator edges)
                {
                //      CGAL_triangulation_precondition( v != Vertex_handle() 
);
                //      CGAL_triangulation_expensive_precondition( 
is_vertex(v) );

                        std::vector<Delaunay_cell_handle> tmp_cells;
                        tmp_cells.reserve(64);
                        
std::pair<std::back_insert_iterator<std::vector<Delaunay_cell_handle> >,
                                        OutputIterator> it 
(std::back_inserter(tmp_cells), edges);
                        it = incident_edges_3(&(vda->dual()), v, v->cell(), 
it);

                        for(typename 
std::vector<Delaunay_cell_handle>::iterator cit =
tmp_cells.begin();
                          cit != tmp_cells.end();
                          ++cit)
                        {
                                (*cit)->set_in_conflict_flag(0);
                        }
                        return it.second;
                }

        private:
                
                template <class IncidentCellIterator, class 
IncidentEdgeIterator>
                std::pair<IncidentCellIterator, IncidentEdgeIterator>
                incident_edges_3(const T* t, const Delaunay_vertex_handle& v, 
const
Delaunay_cell_handle& c,
                                   std::pair<IncidentCellIterator,
                                                                 
IncidentEdgeIterator> it)
                {
                        //CGAL_triangulation_precondition(dimension() == 3);

                        // Flag values :
                        // 128 : incident cell already visited
                        // 64 : unknown
                        // etc. for edges
                        c->set_in_conflict_flag( c->get_in_conflict_flag() | 
VISITED);
                        *it.first++ = c;

                        int vertex_index = c->index(v);
                        for (int i=0; i<4; ++i) {
                                if (i == vertex_index)
                                        continue;
                                Delaunay_cell_handle next = c->neighbor(i);
                                
                                for(int e = 0; e < 3; e++) {
                                        int target_index = 
T::vertex_triple_index(vertex_index, e);
                                        if(! (c->get_in_conflict_flag() & 
edge_flags[vertex_index][
target_index ]) ) {
                                
                                                *it.second++ = 
Delaunay_edge(c, vertex_index, target_index);
                                                Delaunay_vertex_handle target 
= c->vertex( target_index);
                                                
                                                Delaunay_cell_circulator ccs 
= t->incident_cells(c,
vertex_index, target_index);
                                                Delaunay_cell_circulator cce 
= ccs;
                                                do {
                                                        int vindex = 
(*ccs).index(v);
                                                        int tindex = 
(*ccs).index(target);
                                                        
(*ccs).set_in_conflict_flag((*ccs).get_in_conflict_flag() |
edge_flags[vindex][tindex]);
                                                        ccs++;
                                                } while(ccs != cce);
                                        }
                                }

                                if (next->get_in_conflict_flag() & VISITED)
                                        continue;
                                it = incident_edges_3(t, v, next, it);
                        }
                        return it;
                }

};