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.
