CGAL users discussion list

[mytien <>]

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.