CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

Ben Haller wrote:
>   Yeah, I think you're right.  I'm puzzled as to why using exact numbers would 
> solve the problem; the points in question violate the assumption (that 3+ points 
> will not be colinear) even with exact numbers, I would think.  But anyhow, I 
> have come to the conclusion that jittering the points slightly is a reasonable 
> workaround; I often have colinear points, and I don't really care which way the 
> Delaunay triangulation decides to handle them, as long as it picks a way and 
> doesn't raise.  :->
>   Thanks!
The problem here is not which triangulation you will get but
will you get a triangulation. Due to floating point computation,
you end up in a situation (because another predicate was badly
evaluated) where you call a predicate with points that
should form an independent set of points. Unfortunately this is not the
case and the predicate crashes.


S.

> Ben Haller
> McGill University
>
>
> On Jul 20, 2010, at 10:06 AM, Sebastien Loriot (GeometryFactory) wrote:
>
> > Ben Haller wrote:
> > > On Jul 19, 2010, at 4:06 PM, Ben Haller wrote:
> > > > 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...
> > >  I have just discovered that adding a small amount of random noise to the 
> > > points I am inserting prevents the assertion.  This was based on the 
> > > intuition that the problem might be related to some sort of symmetry in the 
> > > points inserted.  The random noise seems to break the symmetry, and the 
> > > assertion is no longer triggered.  I'm not happy with this solution, though, 
> > > as it seems both to be 1) a hack, and 2) probably unreliable.  Does anybody 
> > > have a better suggestion?  Is there a really good reason why CGAL needs to 
> > > assert on this condition in the first place?
> > >  Thanks!
> > > Ben Haller
> > > McGill University
> > Hello,
> >
> >
> > I guess this is because your points are in a degenerate configuration
> > and you are using a non-exact number type. I have the same error you report 
> > when using double, but when using Gmpq this is fine.
> >
> > Have a look here for more details:
> > http://www.cgal.org/FAQ.html#inexact_NT
> > and here:
> > http://www.cgal.org/philosophy.html
> >
> >
> > S.
> >
> > --
> > You are currently subscribed to cgal-discuss.
> > To unsubscribe or access the archives, go to
> > https://lists-sop.inria.fr/wws/info/cgal-discuss
> >
> > #include <CGAL/Cartesian_d.h>
> > #include <CGAL/Delaunay_d.h>
> > #include <CGAL/Gmpq.h>
> >
> >
> > //typedef CGAL::Cartesian_d<double> Kernel;
> > typedef CGAL::Cartesian_d<CGAL::Gmpq> Kernel;
> > typedef CGAL::Delaunay_d<Kernel> Delaunay_d;
> > typedef Delaunay_d::Point_d Point;
> >
> > const double points[] = {
> >  0.0,    0.0 ,   0.0 ,   0.00,
> >  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
> > };
> >
> > int main()
> > {
> >  int d=4;
> >  Delaunay_d T(d);
> >
> >  for (int i=0;i<14;++i)
> >    T.insert(Point(d, points+4*i, points+4*i+d));
> >
> >  return 0;
> > }