CGAL users discussion list

[Andreas Fabri <>]

Dear Jean-Marc,

In contrast to the 2D and 3D Delaunay triangulation you must use an exact 
number type.
Example code can be found in demo/Convex_hull_d//delaunay_dd-runtime.cpp

Note however that this makes it even slower. Currently no filtering approach  
(interval
arithmetic combined with exact rithmetic as last resort) is offered to get it 
faster.
We had one user who didn't use the dD points but wrote his own 4D points, 
which reduced
lots of overhead.

best regards,

andreas




 wrote:
> Dear Andreas,
>
> In the sincere hope that it may be helpful, here are a piece of code :
>
> std:size_t numpoints = 40, dim = 6;
> typedef Cartesian_d<double>       Ker;
> typedef Delaunay_d<Ker>   OS_Delaunay_d;
> OS_Delaunay_d Delaunay(6);
>
> for (int j=0; j<numpoints; j++) {
>           particle_type::iterator it_b = from[j].begin();
>           particle_type::iterator it_e = from[j].end();
>           Delaunay.insert(OS_Point_d(dim, it_b, it_e));
> // from is of kind std::vector<std::vector<double> >, almost randomly filled
> };
> // assert( Delaunay.is_valid() ); 
> // is usually not valid, even in dim = 2. Did I mistake sthing ?
>
> This code raise a stackoverflow on my machine at the 40 th insertion, I run 
> VCExpress2005.
> ...
>  	Convex_hull_d<...>::visibility_search(... 
>  	Convex_hull_d<...>::visibility_search(...
>         Convex_hull_d<...>::visibility_search(...
> ...
>
> The same occurs in dim 5. In dim 4, time to insertion seems anormally slow : 
> 10 seconds for 1000 insertions. Dim 3 seems ok, but slower than Qhull. Dim 2 
> is comparable to Qhull.
> Did I mistake something ?
>
> Best
> Jean-Marc Mercier