CGAL users discussion list

["Sebastien Loriot (GeometryFactory)" <>]

On 07/04/2012 07:46 PM, Cornelia Auer wrote:
> 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> >.
Indeed, you should try with a kernel with exact constructions
(CGAL::Simple_cartesian<CGAL::Gmpq> or 
CGAL::Exact_predicates_exact_constructions_kernel).

Sebastien.

> Thanks in advance for your help
> Best,
> Cornelia Auer