spade

spade is a Rust library providing robust 2D Delaunay triangulations. It is designed for correctness using precise geometric predicates to avoid rounding errors.

Key features include:

• 2D Delaunay triangulation: Supports both incremental and bulk loading creation. Can be optionally backed by a hierarchy structure to improve performance for nearest neighbor searches and insertions.
• Vertex removal: Supports removing vertices from an existing triangulation.
• Constrained Delaunay triangulation (CDT): Supports 2D constrained triangulations.
• Delaunay refinement: Implementation of refinement algorithms.
• Voronoi diagrams: Ability to extract the dual Voronoi graph from a triangulation.
• Natural neighbor interpolation: Provides interpolation capabilities based on the triangulation.

Delaunay benchmarks are categorized by the operation being performed and the data type used. They test various combinations of kernels and locate-strategies across different input sizes (n quadrupling from 1 to 16384).

Operations

• Insertion: Measures the time taken to insert $n$ random values.
• Locate Queries: Measures the time taken to locate a random point within a tree containing $n$ random points.

Data Types (Kernels)

• Float Kernels: Benchmarks using floating-point types (e.g., f64).
• Integer Kernels: Benchmarks using integer types (e.g., i64).

Spade separates the public interface of a triangulation from its internal Delaunay maintenance logic.

• Triangulation Trait: This is the primary public interface. It contains the functions common to both Constrained Delaunay Triangulations (CDTs) and unconstrained triangulations.
• TriangulationExt Trait: This is an internal (pub(crate)) trait. It provides the helper methods used by both CDTs and Delaunay Triangulations (DTs) to maintain the Delaunay property.

The DCEL is the underlying topological structure used by Spade to manage the connectivity of vertices, edges, and faces.

Key Characteristics:

• Topology vs. Geometry: Unlike the Triangulation traits, the DCEL and its operations (dcel_operations.rs) do not require a V: HasPosition bound. This means the DCEL is purely concerned with the topology (how elements are connected) rather than their actual spatial coordinates.
• Positioning: Spatial positions are only required when evaluating the Delaunay property (via TriangulationExt).
• Accessors: The DCEL provides major accessor methods for navigating the triangulation's elements.

To run the benchmark suite comparing different Delaunay triangulation implementations (delaunator, cdt, and spade), clone the repository and execute the following commands:

Standard Benchmarks

Run the standard insertion benchmarks (testing uniform and local insertion distributions) from the delaunay_compare directory:

cd delaunay_compare
cargo bench

Results are stored in <repository_root>/target/criterion.

CDT Bulk Loading Benchmark

To run the specific benchmark for Constrained Delaunay Triangulation (CDT) using real-world data (e.g., the Europe coastline dataset), run:

cargo run --release --example real_data_benchmark

The project uses the criterion crate for benchmarking. You can run all benchmarks using cargo bench. To run a specific subset of benchmarks, use a filter after the --bench <name> flag.

Common filters include:

• f64: Runs only floating-point tests.
• i64: Runs only integer tests.

# Run all benchmarks
cargo bench

# Run only floating-point benchmarks
cargo bench --bench delaunay -- f64

# Run only integer benchmarks
cargo bench --bench delaunay -- i64

Based on benchmark results, keep these considerations in mind when using spade:

• Performance vs. Features: For large triangulations, spade (without a hierarchy) is highly favorable. For small triangulations, delaunator and cdt may have a slight edge.
• Hierarchy Usage: Use spade's HierarchyHintGenerator only if you specifically require efficient position lookup (e.g., for nearest neighbor searches), as it incurs additional construction time.
• Stable Bulk Loading: spade supports a stable bulk load variant that maintains relative vertex order, but it is currently not optimized and is relatively slow. Use it with caution.
• Coordinate Limits: spade supports a specific range of coordinate values ($2^{-142} < |x| < 2^{201}$), whereas other libraries may allow any f64 but risk overflow.

Spade provides two primary triangulation types:

• DelaunayTriangulation: A standard 2D Delaunay triangulation. It uses exact geometric predicate evaluation to prevent construction errors caused by floating-point precision loss.
• ConstrainedDelaunayTriangulation: A 2D constrained Delaunay triangulation that supports vertex removal.

Both types support natural neighbor interpolation via the NaturalNeighbor type.

The types FixedHandleImpl and DynamicHandleImpl are internal implementation details. While they are marked pub, they are intended for documentation purposes only and are not part of the stable public API. Their removal in future versions will not be considered a breaking change.

Instead of using these types directly, use the high-level handle types provided in the handles module.

The PointProjection struct represents the projected position of a point relative to an edge. It is typically returned by project_point.

Use these methods to determine where a point lies in relation to a line segment:

• is_before_edge(): Returns true if the projection is before the start of the edge.
• is_behind_edge(): Returns true if the projection is after the end of the edge.
• is_on_edge(): Returns true if the projection lies on the segment.
• relative_position(): Returns a value between 0.0 and 1.0 representing the linear interpolation along the edge (if on the edge).

// Example of checking projection status
let projection = project_point(p1, p2, query_point);
if projection.is_on_edge() {
    let pos = projection.relative_position(); // 0.0 to 1.0
}