CGAL users discussion list

[Camille Wormser <>]

I don't know why exactly this is used however. Can some on explain this to me?

This is the empty ball condition used for defining the Delaunay triangulation. When inserting a new point p, all simplices S such that p is inside the circumsphere of S are searched. This is the test side_of_oriented_sphere. At the beginning, the method checks if the four vertices of simplex S are oriented positively. This should not fail with a Filtered kernel.

I guess I'm getting this error because my input is degenerate? Is there any way to fix this?

No, this reason would be valid if you were using an unfiltered kernel.

I'm using the following data structures:

I copy pasted your definitions (see code below), and I am unable to reproduce your problem. The program prints:

triangulation of 10000 points computed in 1.56 s

Are you sure you are really using these definitions?

-- 

Camille

---------------------------------------------------------------------------------

#include <CGAL/point_generators_3.h>

#include <CGAL/copy_n.h>

#include <list>

// YOUR DEFINITIONS START HERE

#include <CGAL/Simple_cartesian.h>

#include <CGAL/Filtered_kernel.h>

typedef CGAL::Filtered_kernel<CGAL::Simple_cartesian<float> > KernelFloat;

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>

typedef CGAL::Exact_predicates_inexact_constructions_kernel KernelDouble;

typedef KernelFloat KernelActive;

#include <CGAL/Delaunay_triangulation_3.h>

#include <CGAL/Triangulation_hierarchy_3.h>

typedef CGAL::Triangulation_vertex_base_3<KernelActive> TVB;

typedef CGAL::Triangulation_hierarchy_vertex_base_3<TVB> THVB;

typedef CGAL::Triangulation_data_structure_3<THVB> TDS;

typedef CGAL::Delaunay_triangulation_3<KernelActive, TDS> DT;

typedef CGAL::Triangulation_hierarchy_3<DT> CGAL_Triangulation;

typedef CGAL_Triangulation::Point CGAL_Point;

typedef CGAL_Triangulation::Vertex_handle CGAL_VertexHandle;

typedef CGAL_Triangulation::Finite_vertices_iterator CGAL_FiniteVerticesIter;

typedef CGAL_Triangulation::Cell_handle CGAL_CellHandle;

// YOUR DEFINITIONS END HERE

#include <boost/progress.hpp>

#include <iostream>

#define N 10000

int main() {

CGAL_Triangulation triangulation;

typedef CGAL::Random_points_on_sphere_3<CGAL_Point> Generator;

std::list<CGAL_Point> collection;

CGAL::copy_n(Generator(1.), N, std::back_inserter(collection));

std::cout << "triangulation of " << N << " points computed in ";

{

boost::progress_timer timer(std::cout);

triangulation.insert(collection.begin(), collection.end());

}

return 0;

}