CGAL users discussion list

[Bernhard Kornberger <>]

I've written a small benchmark which tests the performance of
d-dimensional delaunay triangulations:

./delaunay_d -n 100 -d 8
Starting Triangulation...
Triangulation for 100 points in dimension 8
Time for Triangulation: [168.51 s]

However, in higher dimension the code crashes:

./delaunay_d -n 100 -d 9
Starting Triangulation...
Triangulation for 100 points in dimension 9
Segmentation fault (core dumped)

I have used CGAL3.3.1 and gcc 4.1.3. The error happens
regardless if double or gmpq is used as RT. This is the source
code which is also available as download with Makefile from
http://www.ist.tugraz.at/staff/kornberger/delaunay_d.tar.bz2)

#include <map>
#include <unistd.h>
#include <time.h>
#include <CGAL/Cartesian_d.h>
#include <CGAL/Homogeneous_d.h>
#include <CGAL/Delaunay_d.h>
#include <CGAL/point_generators_d.h>
#include <CGAL/Gmpq.h>
#include <CGAL/Filtered_kernel.h>
//typedef CGAL::Gmpq RT;
typedef double RT;
typedef CGAL::Homogeneous_d<RT> Kernel;

typedef CGAL::Delaunay_d<Kernel> Delaunay_d;
typedef Delaunay_d::Point_d Point_d;
typedef Delaunay_d::Simplex_handle Simplex_handle;
typedef Delaunay_d::Vertex_handle Vertex_handle;

typedef CGAL::Random_points_in_iso_box_d<Point_d> 
Random_points_iterator;
typedef CGAL::Counting_iterator<Random_points_iterator> 
N_Random_points_iterator;

using namespace std;

// A tool used for performance measurement
void stopWatch(const string& str)
{
        static map<string,long long unsigned> timers;
        map<string,long long unsigned >::iterator it=timers.find(str);
        if(it==timers.end())
        {
                timers.insert(make_pair(str,clock()));
                cout << "Starting "<<str<<"..."<<endl;
        }
        else
        {
		cout << "Time for "<< str <<": 
["<<double(clock()-it->second)/(double)CLOCKS_PER_SEC<<" s]"<<endl<<endl;
                timers.erase(it);
        }
}

void usage()
{
	cout << endl<<"Usage: ./delaunay_d -d <dimension> -n 
<numPoints>"<<endl<<endl;
        exit(1);
}

void triangulate(unsigned dim,unsigned numPoints)
{
	cout << "Triangulation for "<<numPoints<<" points in dimension 
"<<dim<<endl;
        Delaunay_d T(dim);
        Random_points_iterator rand_it(dim,1.0);
        while(numPoints-->0)
        {
        //      cout << *rand_it<<endl;
                T.insert(*rand_it);
                ++rand_it;
        }
	//	cout << 
"Triangulation.number_of_vertices()="<<T.number_of_vertices()<<endl;
}

int main(int argc, char *argv[])
{
        
        int c;
        unsigned dim(0),numPoints(0);
        while ((c=getopt(argc,argv,"d:n:"))!=-1)
        {
                switch (c)
                {
                        case 'd': dim=atoi(optarg);
                        break;
                        case 'n': numPoints=atoi(optarg);
                        break;
                        default:
                        cout << "Wrong argument list"<<endl;
                        usage();
                }
        }
        if(dim==0 || numPoints==0) usage();
        
        stopWatch("Triangulation");
        triangulate(dim,numPoints);     
        stopWatch("Triangulation");
        return 0;
}



Any hints?

Thx/best
Bernhard