CGAL users discussion list

[Menelaos Karavelas <>]

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.

Attachment: main.cpp
Description: Binary data

On 23 Apr 2010, at 11:46, Bai wrote:

> I just run your code,
> I think the reason lies in the use of
> Segment_Delaunay_graph_degeneracy_removal_policy_2, there may be some
> degeneracies in Voronoi diagram and such denegeracies are rejected  
> by such a
> policy.
> --
> View this message in context: 
> http://cgal-discuss.949826.n4.nabble.com/Problems-on-segment-Voronoi-diagram-tp2023020p2036497.html
> Sent from the cgal-discuss mailing list archive at Nabble.com.
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss