CGAL users discussion list

[Martin Uhrin <>]

Dear CGAL community,

I'm using a Delaunay triangulation using vertices with info to 'tag' each vertex.  For neighbouring vertices with the same tag I would like to join the corresponding Voronoi faces.  Eventually I plan to bound the Voronoi diagram along the lines of this example: 

http://www.cgal.org/Manual/latest/doc_html/cgal_manual/Triangulation_2/Chapter_main.html#Subsection_37.5.4

and extract the now bounded polygons corresponding to regions with the same tag.

Currently my approach is roughly as follows:

1) Create triangulation, tagging each vertex

2) Create an Arrangement for each tag

3) Iterate over all (finite) Delaunay edges

4) if the two vertices of the edge do not share the same tag, insert the corresponding Voronoi halfedge into the arrangement for each of the two tags

5) Iterate over all arrangements extracting the edges to get the joined regions of the Voronoi for each tag

My questions are:

a) Is there any more intuitive a way to achieve my goals rather than using arrangements?

b) Is there any way to get better performance?  I've had to use an Exact_predicates_exact_constructions_kernel because I was getting precondition failures with inexact when adding edges to arrangements but now this operation is very slow.

c) When I finally add the boundary to the Voronoi resulting in (hopefully) there being only bounded polygons in the arrangements will I be able to extract these as polygon objects or do I have to somehow build the polygons myself?

Many thanks for your help,

-Maritn

--
Martin Uhrin                                                  Tel: +44 207 679 3466
Department of Physics & Astronomy               Fax:+44 207 679 0595
University College London                         
Gower St, London, WC1E 6BT, U.K.         http://www.cmmp.ucl.ac.uk