CGAL users discussion list

[Olivier Devillers <>]

> Hi again
> These are some preliminary results.
> by passing a whole vector of 100K random vertices inside a square region..
>
> <begin_code>
> constrained_del_tri.insert(vertices.begin(), vertices.end())
> <end_code>
>
> cgal was able to build the constrained delaunay triangulation in just 
> 0.233020 secs
> this with a 2.0 Ghz AMD laptop (not the best hardware).
>
> Is there any reference from the literature (or manual) about this fact 
> you mentioned (rebuilding vs improving a delaunay mesh)?


Improving you triangulation by flipping (while there is an edge which is 
not locally Delaunay: flip it)
may need a quadratic number of flips in the worst case (there is example 
that need this number of flip [Hurtado...])
while the construction from scratch use spatial sorting (O(n log n) and 
the compute the triangulation
in linear time in practice.

Thus the interest of flipping algo arise only if your starting 
triangulation is quite good.

My timing (code below):
 Static Delaunay triangulation of 1000000 points in dim 2 done in 
1.34564 micro-seconds per point.
 checked in 0.666302 micro-seconds per point.

thus just checking the triangulation is half of constructing it.
Hard for flipping to be better than construction from scratch.


Olivier







---- code

#include <iostream>
#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/point_generators_2.h>
#include <CGAL/iterator.h>
#include <CGAL/Timer.h>
typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Delaunay_triangulation_2<K>                   DT;
typedef CGAL::Random_points_in_square_2<DT::Point>          Rnd_points_it;
typedef CGAL::Counting_iterator<Rnd_points_it, DT::Point>   Points_iterator;

int main (int argc, char **argv)
{   int N = 1000000; if( argc > 1 )N = atoi(argv[1]); // number of points
    Rnd_points_it   rand_it( 1.0);
    Points_iterator begin(rand_it), end(rand_it,N);
    DT dt;
    CGAL::Timer cost; cost.reset();cost.start();
    std::cout << " Static Delaunay triangulation of "<<N<<" points in 
dim 2"<< std::flush;
    dt.insert(begin,end);cost.stop();
    std::cout << " done in "<<cost.time()/N*1000000<<" micro-seconds 
per point." << std::endl;
    cost.reset();cost.start();
    dt.is_valid();
    std::cout << " checked in "<<cost.time()/N*1000000<<" micro-seconds 
per point." << std::endl;
    return 0;
}