CGAL users discussion list

[Dahn <>]

I'd like to create a 3d Delaunay triangulation with a pre-specified
circumradius bound. At first I thought a dense enough regular grid is a good
solution, but due to either the perturbation of the grid points or floating
point arithmetic (which is it?) this creates very large tetrahedra.

Say I want to limit the circumradius to 0.1. With 6000 points, most
tetrahedra indeed have a circumradius below 0.1. However, a few will have
circumradii as large as 3. Increasing the number of points won't help, as it
will only increase the size and number of the tetrahedra with large
circumradii.

#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_3.h>
#include <CGAL/point_generators_3.h>                    
#include <vector>
#include <iostream>

typedef CGAL::Exact_predicates_inexact_constructions_kernel     K;
typedef K::Point_3                                              Point;
typedef CGAL::Creator_uniform_3<double, Point>                  Creator;
typedef std::vector<Point>                                      Vector;
typedef CGAL::Delaunay_triangulation_3<K>                       Dt;
typedef Dt::Tetrahedron                                         Tetrahedron;

double circumradius( const Tetrahedron& t) {
        return
CGAL::sqrt(CGAL::squared_distance(CGAL::circumcenter(t),t.vertex(0)));
}


int main(){
        int npts = 6000;
        //// Create a vector of random points
        Vector points;
        CGAL::points_on_cube_grid_3( 1, npts, std::back_inserter(points), 
Creator()
);

        //// Create a Delaunay triangulation from those points
        Dt T;
        T.insert(points.begin(),points.end());

    /// Write out tetrahedron whose circumradii are too large
        for (Dt::Finite_cells_iterator cell = T.finite_cells_begin(); cell !=
T.finite_cells_end(); ++cell) {
        double circum = circumradius(T.tetrahedron(cell));
        if (circum > 0.1) {std::cout << circum << std::endl;}

    }
}



Thank you for any help!



--
Sent from: http://cgal-discuss.949826.n4.nabble.com/