CGAL users discussion list

[Andreas Fabri <>]

Hello,

As your points are on an integer grid there will be many
degenerate situations.  The situation is even worse
in the scenario with the points being on two parallel
planes.

The benchmarks Oliver refers to are done with random
floating point numbers.

Which release of CGAL do you use?  I ask because there
was a recent effort to use a less expensive exact number
types, when tests like orientation predicates fail with
floating point numbers.  So in case you use CGAL 4.2,
please retry it with CGAL 4.3beta.

Best regards,

Andreas

On 16/10/2013 15:12, mytien wrote:
> This is my benchmark program. I use Qt, but of course you can replace the Qt
> functions.
>
> #define _SECURE_SCL 0
> #define DCGAL_NDEBUG
>
> #include <QTime>
> #include <QElapsedTimer>
>
> #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
> #include <CGAL/Delaunay_triangulation_3.h>
>
> typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
> typedef CGAL::Delaunay_triangulation_3<K>  Triangulation;
> typedef K::Point_3                         CGAL_Point;
>
> int main(int argc, char *argv[])
> {
>      Triangulation tri;
>      CGAL_Point p;
>      float x, y, z;
>      int numPoints = 0;
>      QElapsedTimer timer;
>      int cloudSize = 50000; // adjust point cloud size
>
>      qsrand(QTime::currentTime().msec()); //seed for rand()
>
>      // create two layers of points
>      std::vector<CGAL_Point> points(cloudSize);
>      qDebug("start generating random points");
>      for(int i = 0; i < cloudSize/2; i++) {
>          x = rand() % 2000;
>          y = rand() % 2000;
>          z = 50;
>          p = CGAL_Point(x, y, z);
>          points.push_back(p);
>          numPoints++;
>
>          x = rand() % 2000;
>          y = rand() % 2000;
>          z = 150;
>          p = CGAL_Point(x, y, z);
>          points.push_back(p);
>          numPoints++;
>
>      }
>
>      qDebug("start triangulation...\n");
>      timer.start();
>      tri.insert(points.begin(), points.end());
>      qDebug("points: %d, ms: %d\n", numPoints, timer.elapsed());
>
>      return 0;
> }
>
> As you notice, I create two layers with random points on them and I found
> out that if instead of on the two layers I distribute the points evenly in
> space, like this:
>
>      for(int i = 0; i < cloudSize; i++) {
>          x = rand() % 2000;
>          y = rand() % 2000;
>          z = 50;
>          p = CGAL_Point(x, y, z);
>          points.push_back(p);
>          numPoints++;
>
>          x = rand() % 2000;
>          y =
>
> The performance improves.
> 1000 points: 70 - 130ms
> 10000 points: 200 - 800ms
> 20000 poinst: 300 - 1700ms
> 50000 points: 2500 - 4000ms
>
> Still I am not close to the performance in the manual. Do you think the
> randomness of my data is the problem here?
>
>
>
>
> --
> View this message in context: 
> http://cgal-discuss.949826.n4.nabble.com/Performance-of-Triangulation-3-tp4658201p4658211.html
> Sent from the cgal-discuss mailing list archive at Nabble.com.


--
Andreas Fabri, PhD
Chief Officer, GeometryFactory
Editor, The CGAL Project

phone: +33.492.954.912    skype: andreas.fabri