Triangulation performance

In the previous sections, we have dealt with different kernels and locate methods. Let's see how these actually impact performance. We'll only look at insertion performance at the moment. We will combine two different lookup strategies - walk locate and R-Tree locate - with two different sets of input data: uniformly distributed points and points obtained by a random walk.
Feel free to jump to the TL;DR if you just want some quick tips about how to improve the triangulation's performance. The section about auto hinting might also be of interest.

Abbreviations

I this section we will use

• f64T to refer to the trivial kernel with f64 values
• f64F to refer to the float kernel
• i64T to refer to the trivial kernel with i64 values
• i64A to refer to the adaptive int kernel

Default case: Tree Lookup

Let's first see how much difference switching to a different kernel makes.

All kernels but the adaptive int kernel are roughly equally fast. The spikes that can be observed are due to memory reallocation once some internal Vectors have to increase their capacity.

Note: There are some somewhat easy optimizations for the adaptive int kernel that should make it roughly as fast as the other kernels. If you'd be interested in seeing this kernel go to its full potential, feel free to open up an issue.

Best case: Local insertion, walk lookup

Let's now remove the influence of the underlying R-Tree and use walking as locate method. Walking should be exceptionally fast if two consecutively inserted points are close together. We'll use a random walk to model this behaviour, the points are not uniformly distributed anymore.

We gain amortized constant insertion times and - even for small numbers of elements - much faster insertion times. The R-Tree hurts performance significantly, if speed is an issue for your application, try to avoid it.

Worst case: Non-local insertion, walk lookup

Sometimes, points are inserted very randomly. Let's see how well the triangulation walk locate can compete with an r-tree if the input points are uniformly distributed:

The cyan line shows the slowest tree based locate for reference. For uniformly distributed data, the tree backed variant heavily outperforms the walking strategy, at least for more than a few thousand points.

Caching: Screwing up complexity theory

There is one group missing: What happens if we insert points obtained by a random walk into a triangulation backed by an R-Tree? In theory, nothing should change - we would expect an asymptotic running time of O(log(n)). In practice, the triangulation seems to have a nearly constant insertion time:

This is most likely due to caching effects as all necessary data to insert a point into the triangulation and to update the r-tree is still in the cache from the previous insertion. There are still some open questions, e.g. why the floating point kernels fluctuate much more compared to the i64 variants.

Auto hinting

When using DelaunayTreeLookup, spade will use the result of the last query as hint for the next query. That means: Subsequent insertion, nearest neighbor, interpolation or locate queries that are positioned closely together will run in O(1) without the need of giving an explicit hint. This feature is implemented since version 1.1.0.

TL;DR

What does this chapter tell us after all?

• All kernels - with the exception of the (currently) slow adaptive int kernel - tend to be roughly equally fast.
• If you're inserting just "a few" vertices (< ~7000), walk lookup might be the fastest solution. When in doubt, benchmark your application, once with walk locate and once without.
• If you can give good insertion hints (see DelaunayTriangulation::insert_with_hint(..)), this will always yield noticeable performance improvements.
• Do not use walking lookup if you cannot give good hints. This becomes quickly significantly slower.