CGAL users discussion list

[Menelaos Karavelas <>]

I will take a look at the adaptor and get back to you.

Thanks for the "problematic" example.

- m.

On 23 Apr 2010, at 13:01, Vu, Khuong wrote:

> 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
>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss