### Complete Delaunay Triangulation Workflow Example

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/02-delaunay-triangulation.md

A comprehensive example showcasing the creation of a Delaunay triangulation using bulk loading, finding the nearest neighbor, interpolating using natural neighbors, and querying triangulation properties. Ensure necessary imports are included.

```rust
use spade::{DelaunayTriangulation, Point2, Triangulation, PositionInTriangulation};

fn main() -> Result<(), spade::InsertionError> {
    // Create triangulation with bulk loading
    let vertices = vec![
        Point2::new(0.0, 0.0),
        Point2::new(1.0, 0.0),
        Point2::new(1.0, 1.0),
        Point2::new(0.0, 1.0),
    ];
    let mut triangulation = DelaunayTriangulation::<Point2<f64>>::bulk_load(vertices)?;
    
    // Find nearest neighbor
    if let Some(neighbor) = triangulation.nearest_neighbor(Point2::new(0.3, 0.3)) {
        println!("Nearest to (0.3, 0.3) is at {:?}", neighbor.position());
    }
    
    // Interpolate using natural neighbors
    let nn = triangulation.natural_neighbor();
    
    // Query triangulation structure
    println!("Vertices: {}", triangulation.num_vertices());
    println!("Faces: {}", triangulation.num_inner_faces());
    println!("Convex hull size: {}", triangulation.convex_hull_size());
    
    Ok(())
}
```

--------------------------------

### Complete Height Field Interpolation Example

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/05-interpolation.md

This example demonstrates how to set up a Delaunay triangulation with custom vertex data (height) and perform interpolation to find heights at arbitrary query points.

```rust
use spade::{
    DelaunayTriangulation,
    Point2,
    Triangulation,
    HasPosition,
    FloatTriangulation,
};

#[derive(Clone)]
struct HeightVertex {
    position: Point2<f64>,
    height: f64,
}

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

fn main() -> Result<(), spade::InsertionError> {
    // Create triangulation with measured points
    let mut tri: DelaunayTriangulation<HeightVertex> = DelaunayTriangulation::new();
    
    // Insert measured heights
    tri.insert(HeightVertex {
        position: Point2::new(0.0, 0.0),
        height: 100.0,
    })?;
    tri.insert(HeightVertex {
        position: Point2::new(10.0, 0.0),
        height: 110.0,
    })?;
    tri.insert(HeightVertex {
        position: Point2::new(10.0, 10.0),
        height: 120.0,
    })?;
    tri.insert(HeightVertex {
        position: Point2::new(0.0, 10.0),
        height: 105.0,
    })?;
    
    // Create interpolation object
    let nn = tri.natural_neighbor();
    
    // Query various positions
    let query_positions = vec![
        Point2::new(5.0, 5.0),
        Point2::new(7.5, 2.5),
        Point2::new(2.5, 7.5),
    ];
    
    for pos in query_positions {
        let interpolated_height = nn.interpolate(
            |v| v.data().height,
            pos
        );
        println!("Height at {:?}: {:.2}", pos, interpolated_height);
    }
    
    Ok(())
}
```

--------------------------------

### Example: Storing Edge Data

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/02-delaunay-triangulation.md

Illustrates how to associate custom data, like edge length, with each edge in the triangulation. This example shows the process of creating a triangulation with custom edge data, inserting points, and then calculating and storing the length for each edge.

```APIDOC
### Example: Storing Edge Data

```rust
#[derive(Default)]
struct EdgeWithLength {
    length: f64,
}

let mut triangulation: DelaunayTriangulation<Point2<f64>, (), EdgeWithLength>
    = DelaunayTriangulation::new();

triangulation.insert(Point2::new(0.0, 1.0))?;
triangulation.insert(Point2::new(1.0, 1.0))?;
triangulation.insert(Point2::new(0.5, -1.0))?;

for edge in triangulation.fixed_undirected_edges() {
    let edge_handle = triangulation.undirected_edge(edge);
    let positions = edge_handle.positions();
    let length = positions[0].distance_2(positions[1]).sqrt();
    triangulation.undirected_edge_data_mut(edge).length = length;
}
```
```

--------------------------------

### Complete CDT Workflow Example

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/03-constrained-delaunay.md

Demonstrates loading vertices and constraints, performing mesh refinement with specified angle limits and maximum additional vertices, and then iterating over the resulting triangulation. Ensure the 'spade' crate is added to your Cargo.toml.

```rust
use spade::{ConstrainedDelaunayTriangulation, Point2, Triangulation, RefinementParameters, AngleLimit};

fn main() -> Result<(), spade::InsertionError> {
    // Load vertices and constraints efficiently
    let vertices = vec![
        Point2::new(0.0, 0.0),
        Point2::new(10.0, 0.0),
        Point2::new(10.0, 10.0),
        Point2::new(0.0, 10.0),
        Point2::new(5.0, 5.0),
    ];
    
    let constraints = vec![
        [0, 1], [1, 2], [2, 3], [3, 0], // Outer rectangle
        [4, 1], [4, 2],                   // Interior constraints
    ];
    
    let mut cdt = ConstrainedDelaunayTriangulation::<Point2<f64>>::bulk_load_cdt(
        vertices,
        constraints
    )?;
    
    // Refine to ensure good triangle quality
    let result = cdt.refine(
        RefinementParameters::default()
            .with_angle_limit(AngleLimit::from_deg(25.0))
            .with_max_additional_vertices(500)
    );
    
    println!("Refinement complete: {}", result.refinement_complete);
    println!("Vertices: {}, Constraints: {}", cdt.num_vertices(), cdt.num_constraints());
    
    // Query and iterate
    for vertex in cdt.vertices() {
        println!("Vertex at {:?}", vertex.position());
    }
    
    Ok(())
}
```

--------------------------------

### Example: Storing Face Data

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/02-delaunay-triangulation.md

Provides an example of how to store custom data, such as the area, for each face (triangle) in the Delaunay triangulation. This involves defining a struct for the face data and initializing the triangulation with this custom type.

```APIDOC
### Example: Storing Face Data

```rust
#[derive(Default)]
struct FaceArea {
    area: f64,
}

let mut triangulation: DelaunayTriangulation<Point2<f64>, (), (), FaceArea>
    = DelaunayTriangulation::new();
```
```

--------------------------------

### Barycentric Interpolation Setup in Spade

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/05-interpolation.md

Initialize Barycentric interpolation using `barycentric()` on a `DelaunayTriangulation`. This provides linear interpolation within triangles.

```rust
use spade::FloatTriangulation;

let mut triangulation = DelaunayTriangulation::<PointWithValue>::new();
// ... insert vertices ...

let bary = triangulation.barycentric();
let interpolated = bary.interpolate(
    |vertex| vertex.data().value,
    Point2::new(0.5, 0.5)
);
```

--------------------------------

### Complete Handle and Iterator Usage in Rust

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/07-handles-and-iterators.md

Demonstrates inserting vertices, accessing them via reference handles, traversing edges, using fixed handles, and iterating over inner faces. This example shows the fundamental ways to interact with the triangulation data structure.

```rust
use spade::{DelaunayTriangulation, Point2, Triangulation};

fn main() -> Result<(), spade::InsertionError> {
    let mut tri = DelaunayTriangulation::<Point2<f64>>::new();
    
    // Insert vertices
    let v1 = tri.insert(Point2::new(0.0, 0.0))?;
    let v2 = tri.insert(Point2::new(1.0, 0.0))?;
    let v3 = tri.insert(Point2::new(0.5, 1.0))?;
    
    // Access through reference handles
    for vertex in tri.vertices() {
        println!("Vertex: {:?}", vertex.position());
        
        // Traverse edges
        for edge in vertex.out_edges() {
            println!("  -> {:?}", edge.to().position());
        }
    }
    
    // Access through fixed handles
    for handle in tri.fixed_vertices() {
        let vertex = tri.vertex(handle);
        println!("Fixed handle {} at {:?}", handle.index(), vertex.position());
    }
    
    // Iterate faces
    for face in tri.inner_faces() {
        let [v0, v1, v2] = face.vertices();
        println!("Face: {:?}, {:?}, {:?}",
            v0.position(), v1.position(), v2.position()
        );
    }
    
    Ok(())
}
```

--------------------------------

### Create Empty Delaunay Triangulation

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/02-delaunay-triangulation.md

Instantiates an empty Delaunay triangulation. This is a basic starting point for building a triangulation.

```rust
let mut triangulation: DelaunayTriangulation<Point2<f64>> = DelaunayTriangulation::new();
```

--------------------------------

### Custom Configuration for Triangulations

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/08-hint-generators.md

Provides examples of custom triangulation configurations using HierarchyHintGeneratorWithBranchFactor. 'MemorySavingTriangulation' uses a branch factor of 8 for memory-constrained systems, while 'SpeedOptimizedTriangulation' uses a branch factor of 32 for speed-critical applications.

```rust
use spade::{DelaunayTriangulation, HierarchyHintGeneratorWithBranchFactor, Point2};

// For memory-constrained systems
type MemorySavingTriangulation = DelaunayTriangulation<
    Point2<f64>,
    (),
    (),
    (),
    HierarchyHintGeneratorWithBranchFactor<f64, 8>
>;

// For speed-critical applications  
type SpeedOptimizedTriangulation = DelaunayTriangulation<
    Point2<f64>,
    (),
    (),
    (),
    HierarchyHintGeneratorWithBranchFactor<f64, 32>
>;

```

--------------------------------

### Natural Neighbor Interpolation Setup

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/02-delaunay-triangulation.md

Creates an interpolation object for natural neighbor interpolation using the `natural_neighbor` method. This object can be reused for multiple interpolations.

```rust
let nn = triangulation.natural_neighbor();
let interpolated_value = nn.interpolate(|vertex| vertex.data().height, Point2::new(0.5, 0.5));
```

--------------------------------

### Custom Vertex Data with Height

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/02-delaunay-triangulation.md

Example of defining a custom vertex struct that includes additional data like height, and implementing the `HasPosition` trait.

```rust
#[derive(Clone)]
struct VertexWithHeight {
    position: Point2<f64>,
    height: f64,
}

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

let mut triangulation: DelaunayTriangulation<VertexWithHeight> = DelaunayTriangulation::new();
```

--------------------------------

### Example: Storing Additional Vertex Data

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/02-delaunay-triangulation.md

Demonstrates how to store custom data, such as height, associated with each vertex in the Delaunay triangulation. This involves defining a struct that includes the position and the custom data, and implementing the HasPosition trait.

```APIDOC
### Example: Storing Additional Vertex Data

```rust
#[derive(Clone)]
struct VertexWithHeight {
    position: Point2<f64>,
    height: f64,
}

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

let mut triangulation: DelaunayTriangulation<VertexWithHeight> = DelaunayTriangulation::new();
```
```

--------------------------------

### Custom Edge Data with Length

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/02-delaunay-triangulation.md

Example of defining a custom edge struct to store edge-specific data, such as length. It demonstrates inserting points and calculating edge lengths.

```rust
#[derive(Default)]
struct EdgeWithLength {
    length: f64,
}

let mut triangulation: DelaunayTriangulation<Point2<f64>, (), EdgeWithLength>
    = DelaunayTriangulation::new();

triangulation.insert(Point2::new(0.0, 1.0))?;
triangulation.insert(Point2::new(1.0, 1.0))?;
triangulation.insert(Point2::new(0.5, -1.0))?;

for edge in triangulation.fixed_undirected_edges() {
    let edge_handle = triangulation.undirected_edge(edge);
    let positions = edge_handle.positions();
    let length = positions[0].distance_2(positions[1]).sqrt();
    triangulation.undirected_edge_data_mut(edge).length = length;
}
```

--------------------------------

### Add Constraints to CDT (Valid and Invalid Examples)

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/03-constrained-delaunay.md

Demonstrates how to add constraints to a ConstrainedDelaunayTriangulation. Only constraints that touch at endpoints are supported; interior intersections will cause panics. Use `insert` to add vertices and `add_constraint` or `add_constraint_edge` to define constraints.

```rust
// Valid: sharing endpoints
let v0 = cdt.insert(Point2::new(0.0, 0.0))?;
let v1 = cdt.insert(Point2::new(1.0, 0.0))?;
let v2 = cdt.insert(Point2::new(1.0, 1.0))?;
cdt.add_constraint(v0, v1);
cdt.add_constraint(v1, v2); // OK: shares endpoint v1

// Invalid: interior intersection
cdt.add_constraint_edge(
    Point2::new(0.0, 0.5),
    Point2::new(1.0, 0.5)
)?; // Panics if intersects existing constraints
```

--------------------------------

### Creating a Quality Mesh with Constraints

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/09-refinement.md

Shows how to initialize a CDT, define a square domain with constraints, and then refine the mesh to meet quality criteria like angle limits. This is useful for generating well-formed meshes for simulations or analysis.

```rust
use spade::{ConstrainedDelaunayTriangulation, Point2, RefinementParameters, AngleLimit, Triangulation};

fn create_quality_mesh() -> Result<(), spade::InsertionError> {
    let mut cdt = ConstrainedDelaunayTriangulation::<Point2<f64>>::new();
    
    // Define domain boundary (outer square)
    let corners = [
        Point2::new(-1.0, -1.0),
        Point2::new(1.0, -1.0),
        Point2::new(1.0, 1.0),
        Point2::new(-1.0, 1.0),
    ];
    
    let mut vertices = Vec::new();
    for corner in &corners {
        vertices.push(cdt.insert(*corner)?);
    }
    
    // Add boundary constraints
    for i in 0..4 {
        let j = (i + 1) % 4;
        cdt.add_constraint(vertices[i], vertices[j]);
    }
    
    // Refine to create quality mesh
    println!("Initial: {} vertices, {} faces", cdt.num_vertices(), cdt.num_inner_faces());
    
    let result = cdt.refine(
        RefinementParameters::default()
            .with_angle_limit(AngleLimit::from_deg(25.0))
            .with_max_additional_vertices(10000)
    );
    
    println!("Refined: {} vertices, {} faces", cdt.num_vertices(), cdt.num_inner_faces());
    println!("Complete: {}", result.refinement_complete);
    
    Ok(())
}
```

--------------------------------

### Complete Delaunay Triangulation Workflow

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/01-triangulation-trait.md

Demonstrates the full lifecycle of a Delaunay triangulation, including insertion of points, locating points within faces, iterating over edges, and removing vertices. Ensure that the `spade` crate is added as a dependency.

```rust
use spade::{DelaunayTriangulation, Point2, Triangulation, PositionInTriangulation};

fn main() -> Result<(), spade::InsertionError> {
    // Create and populate triangulation
    let mut triangulation: DelaunayTriangulation<Point2<f64>> = DelaunayTriangulation::new();
    let v1 = triangulation.insert(Point2::new(0.0, 0.0))?;
    let v2 = triangulation.insert(Point2::new(1.0, 0.0))?;
    let v3 = triangulation.insert(Point2::new(0.5, 1.0))?;
    
    // Query location
    match triangulation.locate(Point2::new(0.5, 0.3)) {
        PositionInTriangulation::OnFace(face) => {
            let face_handle = triangulation.face(face);
            println!("Found in face with vertices:");
            for vertex in face_handle.vertices() {
                println!("  {:?}", vertex.position());
            }
        },
        _ => println!("Point not in a face"),
    }
    
    // Iterate over all edges
    for edge in triangulation.undirected_edges() {
        println!("Edge from {:?} to {:?}", edge.from().position(), edge.to().position());
    }
    
    // Remove vertex
    triangulation.remove(v1);
    
    Ok(())
}
```

--------------------------------

### Get Total Number of Constraints in CDT

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/03-constrained-delaunay.md

Retrieves the count of all constraint edges currently present in the triangulation.

```rust
println!("Total constraints: {}", cdt.num_constraints());
```

--------------------------------

### Create Default Refinement Parameters

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/09-refinement.md

Initializes `RefinementParameters` with default settings for angle limit, maximum additional vertices, and outer face exclusion.

```rust
use spade::RefinementParameters;

let params = RefinementParameters::default();
```

--------------------------------

### Normalize Coordinates to [-1, 1] Range

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/06-errors.md

Example of normalizing coordinates to a smaller range to avoid overflow issues.

```rust
// Normalize coordinates to [-1, 1] range
let min_x = vertices.iter().map(|v| v.x).fold(f64::INFINITY, f64::min);
let max_x = vertices.iter().map(|v| v.x).fold(f64::NEG_INFINITY, f64::max);
let range_x = max_x - min_x;

for vertex in &mut vertices {
    vertex.x = 2.0 * (vertex.x - min_x) / range_x - 1.0;
}
```

--------------------------------

### Spade Hint Generators

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/00-quick-reference.md

Demonstrates the initialization of DelaunayTriangulation with different hint generators for performance tuning.

```rust
let tri: DelaunayTriangulation<Point2<f64>> = DelaunayTriangulation::new();
```

```rust
type FastTri = DelaunayTriangulation<Point2<f64>, (), (), (), HierarchyHintGenerator<f64>>;
let tri = FastTri::new();
```

```rust
type CustomTri = DelaunayTriangulation<
    Point2<f64>,
    (),
    (),
    (),
    HierarchyHintGeneratorWithBranchFactor<f64, 32>
>;

```

--------------------------------

### Troubleshooting Incomplete Refinement

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/09-refinement.md

Demonstrates how to handle incomplete refinement by increasing angle and vertex limits and retrying the refinement process.

```rust
let result = cdt.refine(params);

if !result.refinement_complete {
    // Increase limits
    let params2 = RefinementParameters::default()
        .with_angle_limit(AngleLimit::from_deg(30.0))
        .with_max_additional_vertices(100000);
    
    let result2 = cdt.refine(params2);
}
```

--------------------------------

### Integer Kernel Insertion Benchmarks

Source: https://github.com/stoeoef/spade/blob/master/benches/README.md

Benchmarks for inserting integer i64 values using adaptive and trivial kernels with different locating strategies. Performance is measured against varying data sizes.

```text
insert/uniform_i64/adaptive_kernel/tree_locate/1        1.00   264.8±35.94ns        ? B/sec
insert/uniform_i64/adaptive_kernel/tree_locate/4        1.00      2.5±0.37µs        ? B/sec
insert/uniform_i64/adaptive_kernel/tree_locate/16       1.00     63.4±5.57µs        ? B/sec
insert/uniform_i64/adaptive_kernel/tree_locate/64       1.00   470.6±22.35µs        ? B/sec
insert/uniform_i64/adaptive_kernel/tree_locate/256      1.00      2.4±0.05ms        ? B/sec
insert/uniform_i64/adaptive_kernel/tree_locate/1024     1.00     10.8±0.11ms        ? B/sec
insert/uniform_i64/adaptive_kernel/tree_locate/4096     1.00     46.2±0.34ms        ? B/sec
insert/uniform_i64/adaptive_kernel/tree_locate/16384    1.00    196.4±1.26ms        ? B/sec
insert/uniform_i64/walk_locate/1        1.00    114.2±1.02ns        ? B/sec
insert/uniform_i64/walk_locate/4        1.00      2.2±0.46µs        ? B/sec
insert/uniform_i64/walk_locate/16       1.00     54.7±4.88µs        ? B/sec
insert/uniform_i64/walk_locate/64       1.00   394.6±14.43µs        ? B/sec
insert/uniform_i64/walk_locate/256      1.00      2.0±0.03ms        ? B/sec
insert/uniform_i64/walk_locate/1024     1.00      9.2±0.08ms        ? B/sec
insert/uniform_i64/walk_locate/4096     1.00     42.9±0.25ms        ? B/sec
insert/uniform_i64/walk_locate/16384    1.00    217.8±0.93ms        ? B/sec
insert/uniform_i64/trivial_kernel/tree_locate/1         1.00   305.3±32.50ns        ? B/sec
insert/uniform_i64/trivial_kernel/tree_locate/4         1.00  1381.6±57.60ns        ? B/sec
insert/uniform_i64/trivial_kernel/walk_locate/1         1.00     81.0±1.87ns        ? B/sec
insert/uniform_i64/trivial_kernel/walk_locate/4         1.00   743.0±23.15ns        ? B/sec
```

--------------------------------

### Float Kernel Insertion Benchmarks

Source: https://github.com/stoeoef/spade/blob/master/benches/README.md

Benchmarks for inserting float64 values using different kernels and locating strategies. Results show performance variations based on data size and algorithm.

```text
insert/uniform_f64/float_kernel/tree_locate/1           1.00   247.7±34.48ns        ? B/sec
insert/uniform_f64/float_kernel/tree_locate/4           1.00  1359.9±43.54ns        ? B/sec
insert/uniform_f64/float_kernel/tree_locate/16          1.00     10.4±0.25µs        ? B/sec
insert/uniform_f64/float_kernel/tree_locate/64          1.00     73.5±0.84µs        ? B/sec
insert/uniform_f64/float_kernel/tree_locate/256         1.00    402.8±1.16µs        ? B/sec
insert/uniform_f64/float_kernel/tree_locate/1024        1.00      2.0±0.01ms        ? B/sec
insert/uniform_f64/float_kernel/tree_locate/4096        1.00      9.3±0.07ms        ? B/sec
insert/uniform_f64/float_kernel/tree_locate/16384       1.00     43.3±0.56ms        ? B/sec
insert/uniform_f64/float_kernel/walk_locate/1           1.00    116.7±1.10ns        ? B/sec
insert/uniform_f64/float_kernel/walk_locate/4           1.00   982.8±14.96ns        ? B/sec
insert/uniform_f64/float_kernel/walk_locate/16          1.00      4.9±0.26µs        ? B/sec
insert/uniform_f64/float_kernel/walk_locate/64          1.00     22.8±0.61µs        ? B/sec
insert/uniform_f64/float_kernel/walk_locate/256         1.00    171.0±0.62µs        ? B/sec
insert/uniform_f64/float_kernel/walk_locate/1024        1.00   1084.2±1.40µs        ? B/sec
insert/uniform_f64/float_kernel/walk_locate/4096        1.00     10.3±0.03ms        ? B/sec
insert/uniform_f64/float_kernel/walk_locate/16384       1.00     91.8±0.44ms        ? B/sec
insert/uniform_f64/trivial_kernel/tree_locate/1         1.00   290.5±26.25ns        ? B/sec
insert/uniform_f64/trivial_kernel/tree_locate/4         1.00  1348.2±50.04ns        ? B/sec
insert/uniform_f64/trivial_kernel/tree_locate/16        1.00     10.1±0.22µs        ? B/sec
insert/uniform_f64/trivial_kernel/tree_locate/64        1.00     68.3±1.07µs        ? B/sec
insert/uniform_f64/trivial_kernel/tree_locate/256       1.00    374.8±1.14µs        ? B/sec
insert/uniform_f64/trivial_kernel/tree_locate/1024      1.00   1891.8±7.48µs        ? B/sec
insert/uniform_f64/trivial_kernel/tree_locate/4096      1.00      8.8±0.08ms        ? B/sec
insert/uniform_f64/trivial_kernel/tree_locate/16384     1.00     41.0±0.58ms        ? B/sec
insert/uniform_f64/trivial_kernel/walk_locate/1         1.00    115.5±0.84ns        ? B/sec
insert/uniform_f64/trivial_kernel/walk_locate/4         1.00   967.5±17.72ns        ? B/sec
insert/uniform_f64/trivial_kernel/walk_locate/16        1.00      4.5±0.30µs        ? B/sec
insert/uniform_f64/trivial_kernel/walk_locate/64        1.00     19.1±0.80µs        ? B/sec
insert/uniform_f64/trivial_kernel/walk_locate/256       1.00    123.0±0.73µs        ? B/sec
insert/uniform_f64/trivial_kernel/walk_locate/1024      1.00    802.2±3.29µs        ? B/sec
insert/uniform_f64/trivial_kernel/walk_locate/4096      1.00      7.8±0.04ms        ? B/sec
insert/uniform_f64/trivial_kernel/walk_locate/16384     1.00     73.3±0.58ms        ? B/sec
```

--------------------------------

### Create and Use FixedVertexHandle

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/07-handles-and-iterators.md

Demonstrates creating a FixedVertexHandle from an index, retrieving its index, converting it to a reference handle, and accessing/mutating its data.

```rust
let handle = FixedVertexHandle::from_index(5);
let index = handle.index();
let ref_handle = triangulation.vertex(handle);
let position = ref_handle.position();
let vertex_data = triangulation.vertex_data_mut(handle);
vertex_data.custom_field = 42;
```

--------------------------------

### Checking for Edge Intersection using as_edge_intersection

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/10-line-intersection.md

Provides an example of using the `as_edge_intersection` helper method on an `Intersection` enum to conditionally check if the intersection is an edge crossing.

```rust
for intersection in LineIntersectionIterator::new(&tri, from, to) {
    if let Some(edge) = intersection.as_edge_intersection() {
        println!("Found edge intersection");
    }
}
```

--------------------------------

### Integer Kernel Locate Benchmarks

Source: https://github.com/stoeoef/spade/blob/master/benches/README.md

Benchmark results for locating points using integer kernels. Shows performance for 'adaptive_kernel' and 'trivial_kernel' with integer data.

```text
locate/uniform_i64/adaptive_kernel/tree_locate/1        1.00    509.7±0.36ns        ? B/sec
locate/uniform_i64/adaptive_kernel/tree_locate/4        1.00    588.9±0.47ns        ? B/sec
locate/uniform_i64/adaptive_kernel/walk_locate/1        1.00    505.0±1.25ns        ? B/sec
locate/uniform_i64/adaptive_kernel/walk_locate/4        1.00    548.2±0.31ns        ? B/sec
locate/uniform_i64/trivial_kernel/walk_locate/1         1.00    510.2±0.30ns        ? B/sec
```

--------------------------------

### Custom Face Data with Area

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/02-delaunay-triangulation.md

Example of defining a custom face struct to store face-specific data, such as area. Initializes a triangulation with custom face data.

```rust
#[derive(Default)]
struct FaceArea {
    area: f64,
}

let mut triangulation: DelaunayTriangulation<Point2<f64>, (), (), FaceArea>
    = DelaunayTriangulation::new();
```

--------------------------------

### Manual Hints for Insertion and Location

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/08-hint-generators.md

Provides manual hints to the `insert_with_hint` and `locate_with_hint` methods. Use when you have prior knowledge of nearby vertices or a specific location to narrow down the search space.

```rust
let hint_vertex = triangulation.vertices().next().unwrap().fix();

// Insert with hint
let handle = triangulation.insert_with_hint(vertex, hint_vertex)?;

// Locate with hint
let position = triangulation.locate_with_hint(
    Point2::new(0.5, 0.5),
    hint_vertex
);
```

--------------------------------

### Access and Modify Edge Data in CDT

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/03-constrained-delaunay.md

Iterate over fixed undirected edges in a ConstrainedDelaunayTriangulation and modify their associated data. This example shows how to set edge color based on whether it's a constraint edge or a Delaunay edge.

```rust
#[derive(Default)]
struct EdgeInfo {
    color: u32,
}

let mut cdt: ConstrainedDelaunayTriangulation<Point2<f64>, (), EdgeInfo> 
    = ConstrainedDelaunayTriangulation::new();

// ... insert vertices and constraints ...

for edge_handle in cdt.fixed_undirected_edges() {
    let edge_data = cdt.undirected_edge_data_mut(edge_handle);
    if edge_data.is_constraint_edge() {
        edge_data.data_mut().color = 0xFF0000; // Red for constraints
    } else {
        edge_data.data_mut().color = 0x000000; // Black for Delaunay edges
    }
}
```

--------------------------------

### Iterating and Accessing Vertex Data

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/07-handles-and-iterators.md

Demonstrates how to obtain VertexHandles through iteration and access their position, custom data, and connected outgoing edges. Also shows conversion to a fixed handle.

```rust
for vertex in triangulation.vertices() {
    println!("Position: {:?}", vertex.position());
    println!("Data: {:?}", vertex.data());
    
    // Iterate connected edges
    for edge in vertex.out_edges() {
        println!("  Edge to: {:?}", edge.to().position());
    }
    
    // Convert to fixed handle for storage
    let fixed = vertex.fix();
}
```

--------------------------------

### Run Specific Benchmarks with Filter

Source: https://github.com/stoeoef/spade/blob/master/benches/README.md

Execute a specific set of benchmarks by providing a filter argument. Use filters like 'f64' for floating-point tests or 'i64' for integer tests.

```bash
cargo bench --bench delaunay -- <filter>
```

--------------------------------

### Delaunay Triangulation with HierarchyHintGenerator

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/02-delaunay-triangulation.md

Shows how to instantiate a Delaunay triangulation using HierarchyHintGenerator for faster lookups, especially beneficial for random access queries. Requires importing the necessary types.

```rust
use spade::{DelaunayTriangulation, HierarchyHintGenerator, Point2};

type FastTriangulation = DelaunayTriangulation<Point2<f64>, (), (), (), HierarchyHintGenerator<f64>>;
let triangulation = FastTriangulation::new();
```

--------------------------------

### nearest_neighbor

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/02-delaunay-triangulation.md

Finds the vertex closest to a given position. This method has an average time complexity of O(sqrt(n)) and is implemented using a greedy walking approach starting from a hint vertex. It returns an Option containing a vertex handle or None if no neighbor is found.

```APIDOC
## `nearest_neighbor(&self, position: Point2<V::Scalar>) -> Option<VertexHandle>`

### Description
Finds the vertex closest to a given position.

### Parameters
#### Path Parameters
- **position** (Point2) - Required - Query position

### Returns
- **Option<VertexHandle>** - Option with vertex handle or None

### Time Complexity
- O(sqrt(n)) average

### Notes
- Implemented via greedy walking from hint vertex.
```

--------------------------------

### Check Refinement Results

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/09-refinement.md

This snippet demonstrates how to set refinement parameters, perform refinement, and then check the `RefinementResult` to determine success or failure, printing relevant statistics.

```rust
use spade::{RefinementParameters, AngleLimit};

let params = RefinementParameters::default()
    .with_angle_limit(AngleLimit::from_deg(25.0))
    .with_max_additional_vertices(1000);

let result = cdt.refine(params);

if result.refinement_complete {
    println!("Refinement successful!");
    println!("Vertices added: {}", cdt.num_vertices());
} else {
    println!("Refinement incomplete - vertex limit reached");
    println!("Consider increasing with_max_additional_vertices ()");
}

println!("Excluded outer faces: {}", result.excluded_faces.len());
```

--------------------------------

### Float Kernel Locate Benchmarks

Source: https://github.com/stoeoef/spade/blob/master/benches/README.md

Benchmark results for locating points using float kernels. Compares 'tree_locate' and 'walk_locate' performance across different dataset sizes.

```text
locate/uniform_f64/float_kernel/tree_locate/1           1.00    513.1±0.67ns        ? B/sec
locate/uniform_f64/float_kernel/tree_locate/4           1.00    585.4±0.49ns        ? B/sec
locate/uniform_f64/float_kernel/tree_locate/16          1.00    642.2±0.61ns        ? B/sec
locate/uniform_f64/float_kernel/tree_locate/64          1.00    690.5±0.71ns        ? B/sec
locate/uniform_f64/float_kernel/tree_locate/256         1.00    763.1±0.60ns        ? B/sec
locate/uniform_f64/float_kernel/tree_locate/1024        1.00    850.2±2.35ns        ? B/sec
locate/uniform_f64/float_kernel/tree_locate/4096        1.00    975.9±3.17ns        ? B/sec
locate/uniform_f64/float_kernel/tree_locate/16384       1.00   1154.4±4.17ns        ? B/sec
locate/uniform_f64/float_kernel/walk_locate/1           1.00    514.2±0.27ns        ? B/sec
locate/uniform_f64/float_kernel/walk_locate/4           1.00    569.6±0.57ns        ? B/sec
locate/uniform_f64/float_kernel/walk_locate/16          1.00    629.0±0.39ns        ? B/sec
locate/uniform_f64/float_kernel/walk_locate/64          1.00    811.2±0.66ns        ? B/sec
locate/uniform_f64/float_kernel/walk_locate/256         1.00    841.4±0.56ns        ? B/sec
locate/uniform_f64/float_kernel/walk_locate/1024        1.00   1010.0±1.12ns        ? B/sec
locate/uniform_f64/float_kernel/walk_locate/4096        1.00      3.0±0.00µs        ? B/sec
locate/uniform_f64/float_kernel/walk_locate/16384       1.00      3.8±0.01µs        ? B/sec
locate/uniform_f64/trivial_kernel/tree_locate/1         1.00    512.6±0.40ns        ? B/sec
locate/uniform_f64/trivial_kernel/tree_locate/4         1.00    580.9±0.49ns        ? B/sec
locate/uniform_f64/trivial_kernel/tree_locate/16        1.00    637.1±2.80ns        ? B/sec
locate/uniform_f64/trivial_kernel/tree_locate/64        1.00    681.5±1.24ns        ? B/sec
locate/uniform_f64/trivial_kernel/tree_locate/256       1.00    736.6±1.32ns        ? B/sec
locate/uniform_f64/trivial_kernel/tree_locate/1024      1.00    816.9±2.19ns        ? B/sec
locate/uniform_f64/trivial_kernel/tree_locate/4096      1.00    937.1±6.65ns        ? B/sec
locate/uniform_f64/trivial_kernel/tree_locate/16384     1.00   1136.4±1.70ns        ? B/sec
locate/uniform_f64/trivial_kernel/walk_locate/1         1.00    509.4±0.43ns        ? B/sec
locate/uniform_f64/trivial_kernel/walk_locate/4         1.00    561.4±0.90ns        ? B/sec
locate/uniform_f64/trivial_kernel/walk_locate/16        1.00    592.4±0.33ns        ? B/sec
locate/uniform_f64/trivial_kernel/walk_locate/64        1.00    704.7±0.22ns        ? B/sec
locate/uniform_f64/trivial_kernel/walk_locate/256       1.00    723.9±0.31ns        ? B/sec
locate/uniform_f64/trivial_kernel/walk_locate/1024      1.00    843.0±0.74ns        ? B/sec
locate/uniform_f64/trivial_kernel/walk_locate/4096      1.00      2.3±0.00µs        ? B/sec
locate/uniform_f64/trivial_kernel/walk_locate/16384     1.00      3.1±0.01µs        ? B/sec
```

--------------------------------

### Bulk Load Vertices into Triangulation

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/00-quick-reference.md

Efficiently create a Delaunay triangulation by loading a collection of vertices. This is often the fastest method for initial triangulation.

```rust
let tri = DelaunayTriangulation::bulk_load(vertices?);
```

--------------------------------

### Delaunay Triangulation with Configurable HierarchyHintGenerator

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/02-delaunay-triangulation.md

Illustrates the creation of a Delaunay triangulation with a configurable HierarchyHintGenerator, allowing customization of the branch factor for the hierarchy. This offers fine-grained control over performance characteristics.

```rust
use spade::{DelaunayTriangulation, HierarchyHintGeneratorWithBranchFactor, Point2};

type CustomTriangulation = DelaunayTriangulation<
    Point2<f64>,
    (),
    (),
    (),
    HierarchyHintGeneratorWithBranchFactor<f64, 32>
>;
```

--------------------------------

### Simple Delaunay Triangulation

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/02-delaunay-triangulation.md

Demonstrates the creation of a basic Delaunay triangulation using the default LastUsedVertexHintGenerator. This is suitable for general use cases where performance is not critically dependent on complex spatial queries.

```rust
type SimpleTriangulation = DelaunayTriangulation<Point2<f64>>;
let triangulation = SimpleTriangulation::new();
```

--------------------------------

### AngleLimit Constructors

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/09-refinement.md

Provides methods to create an AngleLimit instance from degrees, radians, or a circumradius-to-edge ratio.

```APIDOC
## AngleLimit

Specifies the minimum allowed angle.

### Constructors

#### `from_deg(degree: f64) -> Self`

Create from angle in degrees.

**Input**: Angle in degrees (0 to 360)
**Default**: 30°
**0°**: Disables angle refinement

#### `from_rad(rad: f64) -> Self`

Create from angle in radians.

#### `from_radius_to_shortest_edge_ratio(ratio: f64) -> Self`

Create from circumradius-to-edge ratio.

For a face with circumradius R and shortest edge length e, the ratio R/e is related to the minimum angle θ by:

```
R/e = 1 / (2 * sin(θ))
```

**Reference table:**

| Angle (deg) | Angle (rad) | Ratio |
|---|---|---|
| 20° | 0.349 | 1.46 |
| 25° | 0.436 | 1.18 |
| 30° | 0.524 | 1.00 |
| 35° | 0.611 | 0.86 |

Larger ratio = smaller allowed minimum angle = less refinement.
```

--------------------------------

### Random Access Triangulation with HierarchyHintGenerator

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/08-hint-generators.md

Shows how to create a Delaunay triangulation with HierarchyHintGenerator for fast random access queries. Includes bulk loading for efficient initialization and performing nearest neighbor searches.

```rust
use spade::HierarchyHintGenerator;

type RandomAccessTriangulation = DelaunayTriangulation<
    Point2<f64>,
    (),
    (),
    (),
    HierarchyHintGenerator<f64>
>;

let mut tri = RandomAccessTriangulation::new();

// Bulk load for efficient initialization
let vertices = vec![/* many random points */];
let mut tri = RandomAccessTriangulation::bulk_load(vertices)?;

// Fast random queries
let queries = vec![
    Point2::new(0.3, 0.7),
    Point2::new(-0.5, 0.2),
    Point2::new(0.9, -0.1),
];

for query in queries {
    if let Some(nearest) = tri.nearest_neighbor(query) {
        println!("Found nearest at {:?}", nearest.position());
    }
}
```

--------------------------------

### Create AngleLimit from Circumradius-to-Edge Ratio

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/09-refinement.md

Use `from_radius_to_shortest_edge_ratio` to create an AngleLimit instance based on the ratio of a face's circumradius to its shortest edge. A larger ratio corresponds to a smaller minimum angle.

```rust
use spade::AngleLimit;

// Equivalent to 30 degrees
let limit = AngleLimit::from_radius_to_shortest_edge_ratio(1.0);

// Equivalent to 25 degrees
let limit = AngleLimit::from_radius_to_shortest_edge_ratio(1.18);
```

--------------------------------

### Create and Manipulate Constrained Delaunay Triangulation

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/00-quick-reference.md

Demonstrates how to create a new CDT, insert vertices, add constraints, and check for their existence. Use this for building triangulations with predefined edges.

```rust
let mut cdt = ConstrainedDelaunayTriangulation::<Point2<f64>>::new();
let v1 = cdt.insert(Point2::new(0.0, 0.0))?;
let v2 = cdt.insert(Point2::new(1.0, 0.0))?;
cdt.add_constraint(v1, v2);
if cdt.exists_constraint(v1, v2) {
    println!("Constraint exists");
}
```

--------------------------------

### Create Triangulation with Custom Hint Generator

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/00-quick-reference.md

Instantiate a Delaunay triangulation using a custom hint generator for potentially optimized insertion performance.

```rust
type FastTri = DelaunayTriangulation<Point2<f64>, (), (), (), HierarchyHintGenerator<f64>>;
let tri = FastTri::new();
```

--------------------------------

### Create and Use FixedDirectedEdgeHandle

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/07-handles-and-iterators.md

Shows how to create a FixedDirectedEdgeHandle from an index and access the corresponding directed edge in the triangulation.

```rust
let handle = FixedDirectedEdgeHandle::from_index(10);
let edge = triangulation.directed_edge(handle);
```

--------------------------------

### Walking to Neighboring Vertices

Source: https://github.com/stoeoef/spade/blob/master/_autodocs/07-handles-and-iterators.md

Illustrates how to find the position of a vertex's neighbor by iterating through its outgoing edges.

```rust
let vertex = triangulation.vertices().next().unwrap();
for edge in vertex.out_edges() {
    let neighbor = edge.to();
    println!("Neighbor at {:?}", neighbor.position());
}
```