Precision errors and calculation kernels

This section goes into detail about precision problems when creating delaunay triangulations. Feel free to skip to th TL;DR at the end if this section.

What can go wrong?

When creating delaunay triangulations, the processor needs to make geometric queries, all based on two tests: The in circle test (is a point inside the circle going through three other points?) and the orientation test (are three points ordered clockwise?). Failing to correctly answer these tests can lead to panics, endless loops or wrong results at run time. Unfortunately, naive implementation of the tests can yield incorrect results due to floating point rounding errors. Spade offers two possible workarounds:

• Discretize your floating point values and convert them to integral values. These do not suffer from rounding issues but are prone to over and underflow faults.
• Use an adaptive calculation method that increases floating point accuracy until the result is correct (recommended).

Calculation kernels

Calculation kernels describe how the aforementioned tests are solved. Spade offers three different kernels to deal with various situations:

• spade::kernels::FloatKernel is the recommended, 'go-to' kernel if you're in doubt. It is reasonably fast, works with vectors over f64 coordinates and mitigates rounding errors. Overflow errors are possible, yet very unlikely as the value range of f64 is large.
• spade::kernels::TrivialKernel 'assumes' that all native operations are precise (which is true for integral types). Still, over and underflow can happen.
• spade::kernels::AdaptiveIntKernel can be used for i64 coordinates. It monitors all calculations while performing the tests. If an overflow was detected, it will switch to a heap allocated big integer and complete the test.

A calculation kernel is a part of the triangulations type signature. Here's an example of how you could create a triangulation with the AdaptiveIntKernel:

use spade::delaunay::{DelaunayTriangulation, RTreeDelaunayLocate};
use spade::kernels::AdaptiveIntKernel;

let mut d: DelaunayTriangulation<_, AdaptiveIntKernel, RTreeDelaunayLocate<_>>
    = DelaunayTriangulation::new();
d.insert(Point2::new(200, -200i64));

TL;DR.

Let's summarize. Do you need floating point type coordinates?

• Yes: Use FloatTriangulation::with_tree_locate() or FloatTriangulation::with_walk_locate() to create your triangulation.
• No: Are your coordinates within the range of approximately ±100,000?
  • Yes: Use i64 as coordinate type and create your triangulation with IntKernel::with_tree_locate() (or walk lookup)
  • No: Use the AdaptiveIntKernel. See the code example above for how this might look like.