CGAL users discussion list

[neoideo <>]

thanks!

On Fri, May 25, 2012 at 5:50 AM, Olivier Devillers-2 [via cgal-discuss] <[hidden email]> wrote:

> 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;
}

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

---

If you reply to this email, your message will be added to the discussion below:

http://cgal-discuss.949826.n4.nabble.com/looking-for-method-to-convert-2D-triangulation-into-Delaunay-tp4648517p4654204.html

To unsubscribe from looking for method to convert 2D triangulation into Delaunay, click here.
NAML

---

View this message in context: Re: looking for method to convert 2D triangulation into Delaunay
Sent from the cgal-discuss mailing list archive at Nabble.com.