CGAL users discussion list

[Ben Haller <>]

  Hi!  I'm very new to CGAL, so please forgive any cluelessness.  I'm on Mac 
OS
X 10.6.3 using CGAL version 5.0.0 I think (my /opt/local/lib/libCGAL.dylib
points to libCGAL.5.0.0.dylib), installed using MacPorts.  I'm trying to use
the Delaunay_d class to do Delaunay triangulations.  I'm wrapping the calls in
R and am calling them through R's .C() calling interface.  I don't think 
that's
particularly relevant to my problem, though, so let's not get too lost in the
details.  Test runs that I did with this wrapping worked fine, but now that 
I'm
trying to use the code with my actual dataset, the problem is that I'm getting
an assertion from function_objectsCd.h:285 when I insert a particular point
into the data structure; the assert is "Contained_in_simplex_d: A not affinely
independent."  I have no idea what that means, or how to fix it.  Here's the
sequence of (four-dimensional) points I'm inserting:

     0,      0,      0,      0 
  0.25,   0.00,   0.00, 100.00 
   0.5,    0.0,    0.0,    0.0 
  0.75,   0.00,   0.00,   0.00 
     1,      0,      0,      0 
  0.00,   0.25,   0.00, 100.00 
  1.00,   0.25,   0.00,   0.00 
   0.0,    0.5,    0.0,  100.0 
   1.0,    0.5,    0.0,    0.0 
  0.00,   0.75,   0.00, 100.00 
  1.00,   0.75,   0.00, 100.00 
     0,      1,      0,      0 
  0.25,   1.00,   0.00, 100.00 
   0.5,    1.0,    0.0,    0.0

  The insertion of the last point in that list triggers the assertion.

  I've previously been working with only 2D points, and so the R library 
deldir
sufficed for my purposes.  I never hit this sort of issue with it; it would
accept pretty much any set of points I cared to give it.  Does CGAL's
Delaunay_d class have more stringent requirements for the points you are
allowed to supply it, and if so, why?  The points I want to feed into it are
generated algorithmically, so it's quite a bummer if the Delaunay_d algorithm
is going to fail unpredictably for some sequences of points that I try to give
it!  Is there anything I can do about this?

  Here's the wrapper functions I've defined to interface with R; currently 
they
work with a global Delaunay_d object:

static Delaunay_d *T;

extern "C"
{
        // Initialize the state of this package; discard all previous state
        //
        //      d_      <-      the number of dimensions this triangulation
will involve
        void init(const int *d_)
        {
                using ::T;
                if (T)
                        delete T;
                T = new Delaunay_d(*d_);
        }
        
        // Insert a new point in the triangulation
        //
        //      x       <-      a vector of coordinates for one n-dimensional
point
        void insert(double *x)
        {
                using ::T;
                int d = T->dimension();
                
                T->insert(Point(d, x, x+d));
        }
}

and here are the relevant R functions:

cgal_delaunay_init <- function(dimensions, debug=FALSE)
{
        # check that we are non initialized
        stopifnot(!exists("cgal_delaunay_dims"))
        
        # note this must load the debug build; the release build fails!
        dyn.load("/Users/bhaller/objects/Debug/libcgaldelaunay.dylib")
        
        # test that the functions we expect to be there are there
        stopifnot(is.loaded("init", PACKAGE="libcgaldelaunay.dylib"))
        stopifnot(is.loaded("insert", PACKAGE="libcgaldelaunay.dylib"))
        
        # test that the number of dimensions is reasonable
        stopifnot(NROW(dimensions) == 1)
        stopifnot(dimensions >= 2)
        stopifnot(dimensions <= 32)
        
        cgal_delaunay_debug <<- debug
        
        # initialize with the given number of dimensions
        if (cgal_delaunay_debug)
                print(paste("initializing cgal_delaunay with dimensions ==",
dimensions))
                
        result <- .C("init", n=as.integer(dimensions),
PACKAGE="libcgaldelaunay.dylib")
        stopifnot(result$n == as.integer(dimensions))
        
        # remember the number of dimensions, for our own bookkeeping
        cgal_delaunay_dims <<- dimensions
}

cgal_delaunay_insert <- function(x)
{
        # check that we are initialized
        stopifnot(exists("cgal_delaunay_dims"))
        
        stopifnot(is.vector(x))
        stopifnot(NROW(x) == cgal_delaunay_dims)
        
        if (cgal_delaunay_debug)
                print(paste("inserting point (", paste(x, collapse=", "), ")",
sep=""))
        
        result <- .C("insert", x=as.double(x), 
PACKAGE="libcgaldelaunay.dylib")
}

  As I said before, I don't think this wrapping is related to the problem; I
think that a test program that just inserted the points in question would hit
the assertion, but I haven't tested that.

  Thanks!

Ben Haller
McGill University