CGAL users discussion list

[Olivier Devillers <>]

Le 10/17/13 1:09 PM, mytien a écrit :

Thanks for you responsiveness, you guys are great! 
Yesterday I somehow did not see your post with your benchmark program,
Olivier. I tried it and indeed receive the results from the manual! 
But I see that you used the Random_points_in_cube_3 template, with which you
create the optimal case for triangulation, is that right?

It is certainly a good case, but we have similar timings on many other data sets (as reported in the manual)

Does that mean, your benchmarks do not show the usually achieved
performance, but the best possible?

this is the usually achieved performance for many inputs,
e.g for 3d models coming from laser scans.

What I actually want to do is, let the user of my application draw circles
on planes, collect the points 

Your data set have two problems:

1- bad size of the Delaunay triangulation
A regular sampling of curves in 3D is a bad case for the Delaunay complexity.
(if you take points on two lines, then Delaunay has quadratic size,
by sampling curves, you may reproduce this locally).
(count the number of tetrahdra per vertex in the triangulation to see if it increase too quickly)

2- near degeneracies.
The management of robustness issues is fast for non degenerate position and slower for
configuration in degenerate position or close to degenerate positions.
A degenerate position is 5 co-spherical points. If your points are sampled from circles
then you construct highly degenerate positions.
It could be enough to perturb a bit the points if it is suitable for your application.

--
Olivier Devillers, chercheur à