CGAL users discussion list

["karine hins-mallet" <>]

Hello everyone,

 

I am currently working with the Polygon Delaunay demo. I need to implement a Polygon Voronoï diagram for polygons with extremely precise coordinates.

 

The demo reads polygons form a text file and inserts them into a Delaunay/Voronoï diagram. When the polygons have integer-types coordinates, the resulting Voronoï diagram is correct (see included image “Voronoï”). But when I define my polygons with very precise coordinates, there is a bug in the resulting Voronoï diagram (see included image “Incorrect Voronoï”).

 

Here is the content of the text file defining the polygons:

 

l 10 0.0001 89.99989999999999 24.99989999999999 89.99990000000001 24.9999 74.99989999999999 50.0001 74.99989999999999 50.00009999999999 89.99990000000001 109.9999 89.99990000000001 109.9999 75.0001 69.99990000000001 75.00009999999998 69.99989999999999 65.0001 0.0001 65.0001

l 4 0.0001 60.0001 70.0001 60.0001 70.0001 40.0001 0.0001 40.0001

 

For each line, the letter “l” means that the rest of the line defines the polygon, and the following number is the number of vertices. The following numbers are the vertices coordinates (x1 y1 x2 y2 x3…).

 

The demo is based on a Simple Cartesian (double) kernel. I tried switching to Exact_predicates_inexact_constructions_kernel, but it doesn’t solve the problem. It doesn’t seem to be a graphical problem either. I am really confused, and I refuse to believe that the Voronoï from CGAL only deals with integer coordinates J. What am I doing wrong?

 

 

Thanks in advance,

 

Karine

 

Attachment: incorrect voronoi.gif
Description: GIF image

Attachment: voronoi.gif
Description: GIF image