CODEWITHSUNDEEP
c++algorithmcgal
Pranav
Pranav

Reputation: 475

How to efficiently access vertex_handle from CGAL::Triangulation_3 for a vertex in a std::list?

I am working on an algorithm for mesh generation in which I need to maintain a collection of vertices,segments and triangles in a structure called Piecwise Linear Complex(PLC) and a Delaunay tetrahedralization(DT)(extension of Delaunay triangulation to 3D space) of vertices in PLC.

As per the algorithm, I frequently need to get a handle to a vertex in DT while I have pointer to the same vertex(both have same x,y,z coordinates) in PLC. Below is the initialization of DT and structure of PLC:

PLC structure:

class vertex
{
    float x;
    float y;
    float z;
    std::list<vertex*> neighbor_vertices;
};

class segment
{
    vertex* endpoints[2];
};

class facet
{
    vertex*vertices[3]; 
};

class PLC
{
    std::list<vertex> vertex_list;
    std::list<segment> segment_list;
    std::list<facet> facet_list;
};

Initialization of DT:

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Triangulation_data_structure_3<> tds;
typedef CGAL::Delaunay_triangulation_3<K,tds> Delaunay;

Delaunay DT; 
PLC input_constraints; 

// Initializing Delaunay tetrahedralization structure
DT.insert(input_constraints.vertex_list.begin(),input_constraints.vertex_list.end());

My question is:

For the problem of getting vertex_handle in DT corresponding to a vertex in input_constraints, is there any more efficient(requiring lesser number of operations) approach than:

  1. Simply traversing all vertices of DT and comparing their x,y,z components with that of a vertex in input_constraints.

  2. Maintaining a mapping between vertex_handle of DT and vertex in input_constraints.

This problem can turnout to be a bottleneck because I need to perform this operation frequently and DT and input_constraints both keep updating at different stages of the algorithm.

Upvotes: 0

Views: 635

Answers (1)

Sylvain Pion
Sylvain Pion

Reputation: 585

Ideally, you should try to avoid loosing the information, that is, maintain a list<Vertex_handle> instead of a list<Vertex *>.

There is a way to do what you need, though. Something like the following might work :

Vertex * vp; // your vertex pointer
Vertex_handle v = Delaunay::Triangulation_data_structure::Vertex_range::s_iterator_to(*vp);

Upvotes: 4

Related Questions