CGAL users discussion list

[Cornelia Auer <>]

Dear CGAL users & developers,

with the help of the segment_delaunay_graph_2 I try to compute the 
medial axis for a given *non*-convex polygon.
To build the segment delaunay graph (SDG) I am adding edge by edge of 
the initial polygon. This should give me only weakly intersecting segments.

Now, this works perfectly for most of my polygons, however sometimes the 
construction of the SDG crashes:

I try to insert a new segment by
v_h=sdg.insert(p1,p2, v_h);
however within the insert routine the check SDG.is_valid() fails and the 
procedure crashes. But for no obvious reason (looking at the polygon). 
Due to the high grade of templatization the code is really hard to 
debug/step through for me. I also tried to find the answer by reading 
the paper of Karavelas, but without success.

I would be extremly thankful for any information how degenerate cases 
(!SDG.is_valid()) arise for weakly intersecting input segments.

Or if this could be a numerical issue, as I use the 
Filtered_kernel<Simple_cartesian<double> >.


Thanks in advance for your help
Best,
Cornelia Auer