ExactPredicates.jl

This package provides two important predicates for geometry in the Euclidean plane: orient and incircle.

They are ports in Julia of the CGAL C++ predicates, implemented by Sylvain Pion. They use floating point arithmetic and fallback to slow exact arithmetic when required. The algorithm has been proved robust and correct in a formal proof system by Guillaume Melquiond and Sylvain Pion (“Formal certification of arithmetic filters for geometric predicates”, IMACS 2005) in all cases:

underflows and overflows in the floating point computation;
degenerate configurations (collinear points, colliding vertices, etc.).

Robustness

Robust means that the code:

raises an exception on NaN and Inf arguments;
gives a correct answer on all other inputs with Float64 coordinates, no matter what.

Type for points

The basic type for representing points in the plane is Complex{Float64} (a.k.a. ComplexF64). To define the predicates for a type T, simply define complex(T).

using ExactPredicates
import Base: complex

struct Point
    x :: Float64
    y :: Float64
end

complex(p :: Point) = complex(p.x, p.y)

incircle(Point(0.0, 0.0), Point(1.0, 0.0), Point(0.0, 1.0), Point(.5, .5))

License

The package is released under the LGPLv3 license, or any later version, as required by CGAL's license.

Exported functions

ExactPredicates.orient — Method.

orient(p, q, r) -> Int

Return 1 if r is on the left of the oriented line defined by p and q. Return -1 if r is on the right. Return 0 if r is on the line or if p == q.

The result is guaranteed to be correct if p, q and r are Complex{Float64} values, or faithfully convertible to Complex{Float64} values via complex.

ExactPredicates.incircle — Method.

incircle(a, b, c, p) -> Int

Assume that a, b and c define a counterclockwise triangle. Return 1 if p is strictly inside the circumcircle of this triangle. Return -1 if p is outside. Return 0 if p is on the circle.

If the triangle is oriented clockwise, the signs are reversed. If a, b and c are collinear, this degenerate to an orientation test.

If two of the four arguments are equal, return 0.

The result is guaranteed to be correct if a, b, c and p are Complex{Float64} values, or faithfully convertible to Complex{Float64} values via complex.