Geometrical Predicates

This section discusses how geometrical predicates are defined in this package. The predicates in this package are primarily derived from those implemented in ExactPredicates.jl. The choice of exact predicates is important for the robustness of the algorithms in this package. Without using exact predicates, you may quickly find issues such as infinite loops or errors in the algorithms, as discussed for example at the start of p.3 of these notes by Shewchuk.

Certificates

All predicates defined in this package return a Certificate which simply specifies the result of the predicate. This is easier than working with Bools only as (1) not all predicates have only two outcomes and (2) it is easier to see the certificate than to remember exactly what outcome is represented by a Bool. For example:

using DelaunayTriangulation
p, q, r = (0.0, 0.0), (1.0, 0.0), (0.0, 1.0)
flag = DelaunayTriangulation.triangle_orientation(p, q, r)

Certificate.PositivelyOriented = 6

We could then inspect the result using e.g.

DelaunayTriangulation.is_positively_oriented(flag)

true

Predicates

The predicates we define, as mentioned, are primarily derived from those in ExactPredicates.jl, where we simply extend the orient, incircle, parallelorder, sameside, and meet predicates, allowing us to predicates for, for example, triangle_orientation and point_position_relative_to_line. Predicates for working with the boundary and ghost vertices are also implemented, for example, is_ghost_edge and is_boundary_node.