Basic Usage

Creation and insertion

The recommended way of creating a new triangulation is done by calling DelaunayTriangulation::with_tree_locate or DelaunayTriangulation::with_walk_locate on the type shorthands FloatDelaunayTriangulation or IntDelaunayTriangulation. Inserting is done by calling - who would've guessed - insert:

use cgmath::Point2; // We could use nalgebra as well
use spade::delaunay::{FloatDelaunayTriangulation, IntDelaunayTriangulation};

let mut float_delaunay = FloatDelaunayTriangulation::with_tree_locate();
// Supports the insertion of f64-Vectors
float_delaunay.insert(Point2::new(0.1, 0.2));

let mut int_delaunay = IntDelaunayTriangulation::with_tree_locate();
// Supports the insertion of i64 or i32-Vectors
int_delaunay.insert(Point2::new(1032, 20));

More on the difference between with_tree_locate and with_walk_locate can be found in the Lookup Structure chapter.

Supported types

Every two dimensional object that implements the HasPosition trait can be inserted as a vertex into a delaunay triangulation. Let's define our own type, a simple point with some height, and insert it into the triangulation:

use nalgebra::Point2;
use spade::delaunay::FloatDelaunayTriangulation;
use spade::HasPosition;

struct PointWithHeight {
    position: Point2<f64>,
    height: f64,
}

impl HasPosition for PointWithHeight {
    type Point = Point2<f64>;
    fn position(&self) -> Point2<f64> {
        self.position
    }
}

// Create a new triangulation and insert some points
let mut triangulation = FloatDelaunayTriangulation::with_tree_locate();
triangulation.insert(
    PointWithHeight {
        position: Point2::new(4., 2.),
        height: 10.,
    });

Handles and neighbor discovery

Often we want to refer to vertices that we have inserted before. That's what handles are used for. Handles come in two varieties, fixed (e.g, FixedVertexHandle) and dynamic (same name without the "Fixed", e.g. VertexHandle).
FixedVertexHandles are meant to be stored and used to modify the triangulation, dynamic handles enable easy exploration and iteration of a triangulation. The distinction between these handles is necessary due to rust's ownership and borrowing system: VertexHandles store a reference to the triangulation that makes interactive exploration possible but prohibits any mutation. The fixed variant doesn't have this reference, allowing us to modify the triangulation at free will. We'll continue the previous example to demonstrate this:

// insert returns a fixed handle
let fixed_handle = triangulation.insert(PointWithHeight {
    position: Point2::new(4., 10.),
    height: 5.,
});
// We can now modify this point with the handle
triangulation.vertex_mut(fixed_handle).height = 7.;

// or retrieve it:
let dynamic_handle = triangulation.vertex(fixed_handle);
// The dynamic handle dereferences to the vertex data:
assert_eq!((*dynamic_handle).height, 7.);

// Let's inspect the neighbors of our new point in the triangulation:
for out_edge in dynamic_handle.ccw_out_edges() {
    // out_edge is a (dynamic) edge handle
    println!("height of neighbor: {}", (*out_edge.to()).height);
}

Similar to FixedEdgeHandle, there exists the types FaceHandle and EdgeHandle, both in fixed and dynamic versions. To create a dynamic handle from a fixed one, use DelaunayTriangulation::vertex(handle), ::edge(handle) and ::face(handle). To convert a dynamic handle into a fixed one, use <some dynamic handle>.fix().

Removal

Spade also supports removal of vertices in a triangulation by calling DelaunayTriangulation::remove(FixedVertexHandle). Note: Removing a vertex will 'randomly' invalidate vertex, edge and face handles. Do not use any stored handle after removal. Spade might offer a mechanism to keep vertex handles updated after a removal, it doesn't do so yet though. Note that the position of your vertices will not change. If needed, relocate them to get their new handles (see next section).

Lookup and Locate

Spade offers two methods to get vertices in a triangulation when only their position is known: locate and lookup . Lookup only works if the triangulation is backed by an r-tree, that is, if you created the tree with with_tree_locate. On the other hand, DelaunayTriangulation::locate(PointN) will always work and deliver additional information if the coordinates do not refer to a point. In this case, locate can tell you if the point lies on an edge, outside the convex hull or within a triangle.

Iterating

Iteration is done via the edges(), finite_faces() and vertices() methods that will return iterators over dynamic edge, face and vertex handles.

Convex hull and the infinite face

Every triangulation has at least one face, the infinite face. The infinite face is the face that completely surrounds the triangulation, it's adjacent edges form the convex hull. Here is a snippet that will retrieve a handle to the infinite face and then iterate the convex hull:

let infinite_face = triangulation.infinite_face();
for edge in infinite_face.adjacent_edges() {
  assert_eq!(edge.left_face(), infinite_face());
}

Degenerate case

If all vertices lie on a line, no triangulation can be build. We call this state degenerate. Use DelaunayTriangulation::is_degenerate() to check for this state. A degenerate triangulation will contain exactly one face and no edges (we might connect the vertices to form a line in the future though). Triangulations in degenerate state are not handled very efficiently, we don't recommend inserting lines consisting of many thousand vertices. After all, that's not what triangulations where made for...