Saturday, January 20, 2007

Intersection test assertion failure in CGAL

I have just started using the CGAL library. It is a library for doing computational geometry. It contains classes and functions for different geometric data structures like triangles, line segments, polygons and functions for testing for intersection, calculating convex hull and a lot more. This week I fell into the first trap of computational geometry. I stored polygons in Polygon_2 classes and then performed an intersection test with the do_intersect function. Unfortunately that too often lead to the program crashing with the assertion failure: CGAL error: precondition violation! Expr: Segment_assertions::_assert_is_point_on (p, cv, Has_exact_division()) && compare_xy(cv.left(), p) == SMALLER && compare_xy(cv.right(), p) == LARGER File: /Users/Shared/CGAL-3.2.1/include/CGAL/Arr_segment_traits_2.h Line: 730 or CGAL error: assertion violation! Expr: *slIter == curve File: /Users/Shared/CGAL-3.2.1/include/CGAL/Basic_sweep_line_2.h Line: 591 Eventually I narrowed it down to discover that it happened in specific degenerate cases. For instance when a corner of a polygon intersected an edge of another polygon. Which means two line segments are intersecting another line segment in the exact same spot. Now I know this would normally be a problem for line sweep algorithms but I also know that any computational geometry library with respect for itself should handle such degeneracies. So I could not understand why CGAL should fail. Well it turns out that I didn't read this part of the CGAL manual:
If it is crucial for you that the computation is reliable, the right choice is probably a number type that guarantees exact computation. The Filtered kernel provides a way to apply filtering techniques [BBP01] to achieve a kernel with exact and efficient predicates. Still other people will prefer the built-in type double, because they need speed and can live with approximate results, or even algorithms that, from time to time, crash or compute incorrect results due to accumulated rounding errors.
I had expected this kind of problem. So I thought it was because I used float. I changed to double and got the same problem. It turns out I should have used CGAL::Exact_predicates_exact_constructions_kernel.