CGAL users discussion list

["Louis Feng" <>]

I compiled your code. I was able to reproduce the problem. I think the
problem is numerical accuracy related. As it has nothing to do with the
number of points you are inserting into the triangulation. In fact if you
try to add the following points, the same problem occurs:

6.68896e-005 1
6.68852e-005 2
6.68807e-005 0
6.68762e-005 1
6.68717e-005 2
6.68673e-005 0

Maybe you need to use exact number types.

Louis

> -----Original Message-----
> From: 
> 
>  
> [mailto:]
> Sent: Saturday, March 29, 2008 2:28 PM
> To: 
> 
> Subject: [cgal-discuss] Delaunay_triangulation_2
> 
> Hi all,
> 
> I am in the process of migrating some Delaunay triangulation/voronoi
> diagram code to use the CGAL implementation. The code uses properties
> of the delaunay triangulation and voronoi diagram in order to produce a
> variety of metrics from output from a forest fire simulation. Many of
> these simulations result extremely large numbers of vertices's, which
> is where we are running into problems.
> 
> When built in debug mode, our CGAL backed implementation works
> correctly, however when the project is built in release mode, its a
> whole other story.
> 
> There are two commonly encountered errors, so far we have have not been
> able to determine the reason, or even the circumstances under which,
> these errors occur. In all cases the error occurs as a result of
> calling the insert(Point) method on the triangulation.
> 
> Everything is being compiled in Visual Studio 2008.
> 
> Rather than posting code from our implementation, I will present two
> very simple loops that seem to trigger the errors. If anybody can help
> explain what is going wrong, or make suggestions as to how to fix it, I
> would be very grateful!
> I have been scratching my head with this one for a while now and am
> running low on ideas.
> 
> The following includes and typedef's are in the header:
> 
> >     #include <CGAL/basic.h>
> >     #include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
> >     #include <CGAL/Delaunay_triangulation_2.h>
> >
> >     struct K : CGAL::Exact_predicates_inexact_constructions_kernel {};
> >     typedef CGAL::Delaunay_triangulation_2<K>
> Triangulation;
> >     typedef Triangulation::Point
> Point;
> 
> The follow loop causes an error to be thrown in dblhook.c.
> 
> >         Triangulation T;
> >         for (long i=1; i<15000; i++) {
> >             T.insert(Point(1.0f/i, i%3));
> >         }
> 
> And, oddly enough, the minor change below changes the error
> dramatically, in particular it now throws a std::length_error exception
> in "iosfwd", specifically in "std::_Traits_helper::length_error()"
> 
> >         Triangulation T;
> >         for (long i=1; i<15000; i++) {
> >             T.insert(Point(1.0f/i, rand()%100));
> >         }
> 
> And, even weirder, the following modification gets rid of the error
> altogether.
> 
> >         Triangulation T;
> >         for (long i=1; i<15000; i++) {
> >             T.insert(Point(1.0f/i, i%100));
> >         }
> 
> Note that the results change if we change the number of points added.
> For a sufficiently small set of vertices's, it seems to work every time.
> As the number increases, the likelihood of one of these errors
> occurring increases correspondingly.
> Any insight into the source of these problems would be immensely
> helpful.
> 
> -Ryan
> --
> You are currently subscribed to cgal-discuss.
> To unsubscribe or access the archives, go to
> https://lists-sop.inria.fr/wws/info/cgal-discuss