CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

randooom wrote:
> Hi all,
>
> I have to do some computation on a Voronoi diagram and therefore I need to
> extract the diagram out of the triangulation into a more accessible data
> structure.
>
> A colleague has done this some time ago, but his version is incredible slow
> (it takes 4 hours! to extract a Voronoi diagram from a triangulation of only
> 5000 points).
this is hard to believe.

> The said data structure consists basically of vertices, faces and cells. The
> vertices represent the points and know their adjacent vertices, a face knows
> its vertices and a cell its faces.
Here is what I would do:

1) create dual faces of each triangulation edge and maintain the
   mapping (usually we use a sorted pair of the two DT vertices as
   sorting key)
2) for each triangulation vertex, create its dual cell and for all
   finite incident edges, associate the dual faces of the dual cell
3) create dual vertex of each triangulation cell and maintain the
   mapping
3) for each triangulation edge, consider all incident_cells to
   get the dual vertices of a dual face.
4) for each triangulation cell, consider its neighbor cells to
   set the adjacencies between dual vertices.


main doc pages:
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_3_ref/Class_Triangulation_3.html
http://www.cgal.org/Manual/latest/doc_html/cgal_manual/TriangulationDS_3_ref/Concept_TriangulationDataStructure_3--Cell.html

Triangulation::incident_cells( Edge )
Triangulation::finite_incident_edges ( Vertex_handle , OutputIterator )
Cell::neighbor(int)

S.

> If possible I'd like to keep this structure, because some other code depends
> on it.
> However, the main goal is to make the extraction of the Voronoi diagram
> faster.
>
> I would appreciate any ideas or pointers (not the C ones ;)).
>
> Thanks,
> Daniel