CGAL users discussion list

[Menelaos Karavelas <>]

Try using CGAL::Simple_cartesian<CGAL::Gmpq> as your exact kernel.  
Also using the segment Delaunay graph hierarchy should make things  
faster.

There are also other alternatives for constructing the segment  
Delaunay graph even faster, but they apply only if you know all your  
input in advance (i.e., they are not incremental).

As far as the problem with more than 5000 segments is concerned,  
please send the data, along with the actual code you used to compute  
the segment Delaunay graph, so that I can take a look at them.

- m.


On 23 Apr 2010, at 05:36, Vu, Khuong wrote:

> Hi there,
>
> I think what you did was good. I got the same thing working with  
> Voronoi diagram. I guess it is the problem of Voronoi diagram adapter.
>
> You can check if it is by constructing the DELAUNAY diagram of the  
> same set of input instead of Vornoi diagram. If it runs reasonably  
> fast, then it is the Voronoi adapter to have trouble. You can look  
> at the header definition of the SegmentDelaunayGraph demo. The  
> declaration should be good for you since it deals with no strongly  
> intersection. However, it is Delaunay. Constructing the Voronoi  
> still runs pretty slow though.
>
> Please let me know if you need further help. I have written an  
> alternative Voronoi adapter, currently just for myself. But I'm now  
> away from my desk.
>
> Khuong
> ________________________________________
> From: Bai 
> []
> Sent: Thursday, April 22, 2010 8:01 PM
> To: 
>
> Subject: [cgal-discuss] Problems on segment Voronoi diagram
>
> I am constructing Vornoi diagrams using CGAL, the segments are all  
> from a
> polygonal line, they are consecutive, and there are
> weak intersections as CGAL describes.
>  Firstly,I chose MP_Float as the data type for EK, however, the  
> running
> time is rather slow,
> even slower than the results given in the corresponding papar<< A  
> robust and
> efficient implementation for the segment Voronoi diagram>>
> in 2004.
> Then, I chose Simple_cartesian<double> as EK, this time the running  
> time is
> rather short , however, the checking function is_valid()
> returns false. And for segments more than 5000, the program corrupted.
> Could someone give a trait and policy configurtion ,under which I  
> can build
> Voronoi diagram of a polygonal line efficiently? Thank you
>
> The following is my current configuration(under which the program runs
> quite slow, if replace EK with Simple_cartesian<double>,
> the build time is short but for more than 5000 segments the program
> corrupts):
>        typedef CGAL::Quotient<CGAL::MP_Float>  ENT;
>        typedef CGAL::Simple_cartesian<double>     CK;
>        typedef CGAL::Simple_cartesian<ENT>        EK;
>        typedef
> CGAL 
> ::Segment_Delaunay_graph_filtered_traits_2 
> <CK,CGAL::Field_with_sqrt_tag,
> EK,  CGAL::Field_tag>  Gt;
>        typedef CGAL::Segment_Delaunay_graph_2<Gt>             SDG2;
>        typedef CGAL::Segment_Delaunay_graph_adaptation_traits_2<SDG2>
> TRAIT;
>        typedef
> CGAL::Segment_Delaunay_graph_caching_degeneracy_removal_policy_2<SDG2>
> POLICY;
>        typedef CGAL::Voronoi_diagram_2<SDG2,TRAIT,POLICY> SEG_VD;
> --
> View this message in context: 
> http://cgal-discuss.949826.n4.nabble.com/Problems-on-segment-Voronoi-diagram-tp2023020p2023020.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
>
>
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss