Robust distance comparing predicate

Question

I need a robust predicate defined by the following code:

CompareResult compareDistance(Point a, Point b, Point c, Point d) {
    if (distance(a, b) > distance(c, d))
        return Larger;
    else if (distance(a, b) == distance(c, d))
        return Equal;
    else
        return Smaller;
}

Due to the floating point arithmetic limitations we can't compute distance exactly (even its square), so if we just directly implement this code, the predicate will not be robust. I tried to find it in CGAL library, but couldn't.

Somewhat close to the predicate I need is compare_distance_to_point(Point p, Point q, Point r) predicate. It returns Smaller if distance(p, q) < distance(p, r), Equal if distance(p, q) == distance(p, r) and Larger otherwise. The first thought is to shift c and d by (c - a) vector, so we could call compare_distance_to_point(a, b, d + (c - a)), but this will violate robustness again. So, does anyone have an idea for adapting it?

Answer 1

If you take a kernel with exact predicates such as Exact_predicates_inexact_constructions_kernel, you can use the functor Compare_distance_3 which is a model of the concept CompareDistance_3.

Kernel::Compare_distance_3 cmp;

return cmp(a,b,c,d);