CGAL users discussion list

["Vu, Khuong" <>]

Segment_Delaunay_graph_hierarchy_2 really reduces the running time. I think 
we have nothing to do with the Delaunay diagram. It's totally correct. But 
converting to the Voronoi diagram takes forever. Could you please let us know 
how the Voronoi adapter works? I, personally, think it has a serious bug. 
Thanks for your help.

Khuong

________________________________________
From: Menelaos Karavelas 
[]
Sent: Friday, April 23, 2010 4:32 AM
To: 

Subject: Re: [cgal-discuss] RE: Problems on segment Voronoi diagram

I am not really sure about that. I am attaching my version of your
code, where I made some modifications. You will notice that I have
commented the usage of Quotient<MP_Float> and replaced it by Gmpq.
Also I have commented the usage of Segment_Delaunay_graph_2 and
replaced it by Segment_Delaunay_graph_hierarchy_2. Also I am
considering two possible ways of inserting the segments: your way (the
simple/obvious way) and inserting the first endpoint of a segment,
then the second using the vertex_handle returned for the first, and
then use the two vertex handles to insert the interior of the segment
(I call this below the polyline insertion method, whereas the first
one is called the segments' method).

Here are my running times (on a PowerPC G4) in seconds with
optimization flags turned on (Release building mode):

SDG + MP_Float + polyline: 35.5918
SDG Hierarchy + MP_Float + segments: 35.6429

SDG + Gmpq + segments: 1.19534
SDG + Gmpq + polyline: 1.17302

SDG Hierarchy + Gmpq + segments: 1.14345
SDG Hierarchy + Gmpq + polyline: 1.17157

It seems to me that the showstopper is the number type. I would
immediately switch to Gmpq, and also use the hierarchy (it will be
much for efficient for more input segments). I you do not want to use
the hierarchy, then use the alternative way of inserting your input
(this is the insertPolyline function in the code).

- m.


--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to
https://lists-sop.inria.fr/wws/info/cgal-discuss