CGAL users discussion list

[Scherrer Daniel <>]

Thanks for this explanation.
If I understand right, this performance issue has also something to do with 
the fact that our data points are lying on regular grid positions and often 
there are many possibilities to triangulate and CGAL is searching for the 
exact best using the exact number type, which in our case would not be 
necessary as just one of best the possibilities could be chosen.
Can switching to exact number type be disabled somehow?
Thanks,
Daniel


-----Original Message-----
From: 

 
[mailto:]
 On Behalf Of Marc Glisse
Sent: Mittwoch, 7. Oktober 2015 16:19
To: 

Subject: Re: [cgal-discuss] dD Delaunay Triangulation, data dependent 
performance

On Wed, 7 Oct 2015, Scherrer Daniel wrote:

> I experience huge differences in performance when triangulating in 6D. I 
> tested the following:
>
>       const int D = 6;
>       typedef CGAL::Epick_d<CGAL::Dimension_tag<D>> K;
>       typedef CGAL::Delaunay_triangulation<K> T;
>       for (int i = 0; i < 512; ++i){
>               points.push_back(T::Point((i & 0x3), (i & 0xc) >> 2, (i & 
> 0x30) >> 4,
>                       (i & 0x40) >> 6, (i & 0x80) >> 7, (i & 0x100) >> 8));
>       }
>       T t(D);
>       t.insert(points.begin(), points.end());
>
> This takes about 12s on my PC.
>
> Then I tried the same but scaled the positions by 10 like this:

Try scaling by a power of 2 instead ;-)

>       ...
>       for (int i = 0; i < 512; ++i){
>               points.push_back(T::Point((i & 0x3) * 10, ((i & 0xc) >> 2) * 
> 10, ((i & 0x30) >> 4) * 10,
>                       ((i & 0x40) >> 6) * 10, ((i & 0x80) >> 7) * 10, ((i & 
> 0x100) >> 8) * 10));
>       }
>
> And this takes more than 1 minute. The scaling itself does not seem to be 
> the problem. I tried different data sets which performed better or worse 
> for no obvious reason. I observed factors in computing time up to 30.
>
> Any idea what the triangulation performance could depend on?

Predicates are first evaluated using interval arithmetic (a pair of double). 
In usual non-degenerate cases, it is often sufficient to get the sign of the 
polynomial. In degenerate situations (when the result is 0), it usually fails 
because we don't know the sign of an interval containing zero, and the 
computation is done again using an exact but slow number type. Except in one 
case : when all the interval computations were lucky enough to be exact and 
the interval is thus just one point, 0. This can happen in particular when 
all the coordinates are very small integers.

--
Marc Glisse

--
You are currently subscribed to cgal-discuss.
To unsubscribe or access the archives, go to 
https://sympa.inria.fr/sympa/info/cgal-discuss