Module spade::handles

source ·
Expand description

Handle types used for traversal and modification of triangulations.

A handle can either be a “reference handle” or a “fixed handle”. Reference handles are used for immutable access to a triangulation. Fixed handles allow mutation but have a more limited API.

§Reference handles

Reference handles come in one of four variants:

  • FaceHandles refer to a single face (triangle) of the triangulation. They are used get the triangle’s adjacent vertices and edges. They also may refer to the single outer face.
  • VertexHandles refer to a single vertex of the triangulation. They allow to retrieve the vertex position and its outgoing edges.
  • DirectedEdgeHandles refer to a single directed edge. They allow to retrieve the edges origin and destination vertex, its adjacent face as well as its previous and next edge.
  • UndirectedEdgeHandles refer to an edge without specifying its direction.

All handles also allow to set and retrieve arbitrary additional data associated with that element. Refer to the type parameters of Triangulation for more details.

§Fixed handles

Reference handles all hold an immutable reference to the underlying triangulation. This reference is used to implement a feature rich and intuitive API. However, due to Rust’s ownership semantics, modification of a triangulation can not be done using these handles as that would require a mutable reference. This is required in some cases, e.g. whenever traversal of the triangulation is mixed with insertion operations or when attempting to remove vertices. As a solution, Spade relies on fixed handles for mutation: These are created from normal handles by calling some_handle.fix() and do not keep a reference to the triangulation.

Internally, fixed handles are implemented as indices into a Vec. Removing elements from the triangulation can possibly invalidate any fixed handle. Attempting to resolve an invalid handle may either refer to a different element or panic at run time. It is the callers responsibility to make sure that fixed handles are not used anymore after a removal operation has taken place.

Fixed handles also come in four variants, depending on which element they refer to:

§Retrieving handles by iteration

The Triangulation trait defines iterators for all handle types:

§Creating handles directly

In some cases it may be desireable to create vertex handles artificially by providing the index manually. This can be done by calling handles::FixedVertexHandle::from_index. Make sure that the provided index is smaller than the number of vertices in the triangulation.

§Converting between reference and fixed handles

Converting a reference handle into its fixed counterpart is performed via the fix() method (defined on any handle type).

Converting a fixed handle type back into a reference handle requires calling either Triangulation::vertex, Triangulation::face, Triangulation::directed_edge or Triangulation::undirected_edge.

§Example: Using handles

This example implements a nearest neighbor algorithm on a delaunay triangulation. Starting from an arbitrary start vertex, it greedily walks to the closes vertex until arriving at a local minimum. Due to the special properties of Delaunay triangulations, this is also the global nearest neighbor.

Note: Spade already implements this method, see DelaunayTriangulation::nearest_neighbor

use spade::handles::VertexHandle;
use spade::{DelaunayTriangulation, Point2, Triangulation};

fn nearest_neighbor(
    triangulation: &DelaunayTriangulation<Point2<f64>>,
    target_point: Point2<f64>,
) -> VertexHandle<Point2<f64>> {
    let mut current = triangulation.vertices().next().unwrap();
    let mut best_distance = current.position().distance_2(target_point);
    loop {
        let mut closer = None;
        for neighbor in current.out_edges().map(|edge| edge.to()) {
            let neighbor_distance = neighbor.position().distance_2(target_point);
            if neighbor_distance < best_distance {
                best_distance = neighbor_distance;
                closer = Some(neighbor);
                break;
            }
        }

        if let Some(closer) = closer {
            current = closer;
        } else {
            return current;
        }
    }
}


let vertices = vec![
    Point2::new(0.0, 1.0),
    Point2::new(1.0, 1.0),
    Point2::new(0.0, 0.0),
    Point2::new(1.0, 0.0),
];
let triangulation: DelaunayTriangulation<Point2<f64>> = Triangulation::bulk_load(vertices)?;

// Check that everything works!
for vertex in triangulation.vertices() {
    let nearest_neighbor = nearest_neighbor(&triangulation, vertex.position());
    assert_eq!(nearest_neighbor, vertex);
}

Structs§

  • InnerTag
    Marker type that signifies that a face is an inner faces.
  • PossiblyOuterTag
    Marker type that signifies that a face can possibly be the outer faces.

Enums§

Constants§

  • OUTER_FACE
    Returns a reference to the single outer face.

Type Aliases§