Locate Structure
Insertion into a triangulation consists of 2 steps:
- Find the triangle that contains the new point
- Create new faces in this triangle, flip edges until the delaunay properties are met again.
The second step runs in O(1) on average. Spade offers two different strategies to deal with the first step:
- Insert all points into an R-Tree. R-Trees can help to locate the necessary triangle in O(log(n)).
- Walk along the triangulation in the direction of the new point, starting at a 'random' point. For random uniform point distributions, this will run in O() on average.
Backing up a delaunay triangulation with an R-Tree is a safe solution that will yield a logarithmic insertion time on average, that's why it is recommended as default locate strategy.
Giving a hint
Sometimes we can do better than O(log(n)). Often, points are not inserted uniformly random but very close to each other (e.g., when performing a random walk, or if the points are presorted along a morton curve. Then we can give the triangulation a "hint" about where it should start walking towards the needed triangle, thats what insert_with_hint is used for:
triangulation.insert_with_hint(new_point, handle_of_point_close_to_new_point);
If we know that we can give a good hint in most cases in advance, we can entirely skip the r-tree. This will save memory and can reduce insertion time to O(1). To do so, create the triangulation with with_walk_locate():
let mut triangulation = FloatDelaunayTriangulation::with_walk_locate();
It doesn't even matter if every hint is good, it's enough if most hints will be close.
By default, a triangulation created with with_walk_locate will use the last inserted point as a hint.
The section "Triangulation performance" will give you an overview about how fast and slow the different approaches are.
TL; DR
If you insert points that are very close to each other, consider creating your triangulation with FloatTriangulation::with_walk_locate().
This can reduce insertion time from O(log(n)) to O(1) on average.