CGAL users discussion list

[Menelaos Karavelas <>]

What you describe sounds really strange. Could you be more precise  
(Again code and examples will help) as to what exactl you did?

Integer coordinates should be okay. I do not see any reason why  
integer coordinates would cause a problem.

- m.

On 23 Apr 2010, at 11:00, Vu, Khuong wrote:

> By the way, have you guys tried non-integer coordinates? I used  
> exactly the same declaration as in the demo with only about 80  
> segments. It was extremely slow, taking hours! However, the Delaunay  
> construction was much faster. Could you please tell me what was  
> wrong with that?
>
> Also, were you aware of a possible bug in Voronoi diagram, in which  
> the Voronoi construction procedure misses some vertex although the  
> Delaunay gives the correct result?
>
> Thank you,
> Khuong
> ________________________________________
> From: Menelaos Karavelas 
> []
> Sent: Friday, April 23, 2010 1:43 AM
> To: 
>
> Subject: Re: [cgal-discuss] Problems on segment Voronoi diagram
>
> 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
>
>
> --
> 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