Spade

https://docs.rs/spade
Admin
A Rust library for computational geometry and Delaunay triangulations.
Tokens:271,702
Snippets:1,981
Trust Score:9.1
Update:4 months ago
Show doc for...
Tokens:
Raw
### Setup Initial Two Vertices and Edges in DCEL

Source: https://docs.rs/spade/latest/src/spade/delaunay_core/dcel_operations.rs.html

Initializes a DCEL with two vertices, connecting them with two opposing half-edges and setting up the outer face. This is useful for starting geometric constructions.

```rust
pub fn setup_initial_two_vertices<V, DE, UE, F>(
    dcel: &mut Dcel<V, DE, UE, F>,
    first_vertex: FixedVertexHandle,
    second_vertex: FixedVertexHandle,
) where
    DE: Default,
    UE: Default,
{
    let normalized = FixedDirectedEdgeHandle::new_normalized(0);
    let not_normalized = normalized.rev();

    dcel.edges.push(EdgeEntry::new(
        HalfEdgeEntry {
            next: not_normalized,
            prev: not_normalized,
            face: OUTER_FACE_HANDLE,
            origin: first_vertex,
        },
        HalfEdgeEntry {
            next: normalized,
            prev: normalized,
            face: OUTER_FACE_HANDLE,
            origin: second_vertex,
        },
    ));

    dcel.vertices[first_vertex.index()].out_edge = Some(normalized);
    dcel.vertices[second_vertex.index()].out_edge = Some(not_normalized);
    dcel.faces[OUTER_FACE_HANDLE.index()].adjacent_edge = Some(normalized);
}
```

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

### Nearest Neighbor Search Example

Source: https://docs.rs/spade/latest/src/spade/lib.rs.html

Implements a nearest neighbor search algorithm by greedily walking to the closest vertex. This example demonstrates using vertex handles, iterating over outgoing edges, and accessing vertex positions.

```rust
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;
        }
    }
}

# fn try_main() -> Result<(), spade::InsertionError> {

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);
}
# Ok(()) }
# fn main() { try_main().unwrap() }

```

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

### Default Triangle DCEL Setup

Source: https://docs.rs/spade/latest/src/spade/delaunay_core/dcel_operations.rs.html

Initializes a Dcel structure representing a basic triangle for testing purposes. This setup is crucial for verifying DCEL operations.

```rust
fn default_triangle() -> Dcel<usize, (), ()> {
    use super::{EdgeEntry, FaceEntry, HalfEdgeEntry, VertexEntry};

    let e0 = FixedDirectedEdgeHandle::new(0);
    let e1 = FixedDirectedEdgeHandle::new(1);
    let e2 = FixedDirectedEdgeHandle::new(2);
    let e3 = FixedDirectedEdgeHandle::new(3);
    let e4 = FixedDirectedEdgeHandle::new(4);
    let e5 = FixedDirectedEdgeHandle::new(5);

    let f0 = FixedFaceHandle::new(0);
    let f1 = FixedFaceHandle::new(1);

    let v0 = FixedVertexHandle::new(0);
    let v1 = FixedVertexHandle::new(1);
    let v2 = FixedVertexHandle::new(2);

    let edge0_1 = EdgeEntry::new(
        HalfEdgeEntry {
            face: f0,
            next: e2,
            prev: e4,
            origin: v0,
        },
        HalfEdgeEntry {
            face: f1,
            next: e5,
            prev: e3,
            origin: v1,
        },
    );

    let edge2_3 = EdgeEntry::new(
        HalfEdgeEntry {
            face: f0,
            next: e4,
            prev: e0,
            origin: v1,
        },
        HalfEdgeEntry {
            face: f1,
            next: e1,
            prev: e5,
            origin: v2,
        },
    );

    let edge4_5 = EdgeEntry::new(
        HalfEdgeEntry {
            face: f0,
            next: e0,
            prev: e2,
            origin: v2,
        },
        HalfEdgeEntry {
            face: f1,
            next: e3,
            prev: e1,
            origin: v0,
        },
    );

    let face0 = FaceEntry {
        adjacent_edge: Some(e0),
        data: (),
    };

    let face1 = FaceEntry {
        adjacent_edge: Some(e1),
        data: (),
    };

    let vertex0 = VertexEntry {
        // ... (rest of vertex entries would follow here)
    };
    // ... (remaining vertex and dcel construction)
    unimplemented!("DCEL construction not fully shown in source");
}

```

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

### Line Intersection Iterator Example

Source: https://docs.rs/spade/latest/src/spade/intersection_iterator.rs.html

Demonstrates how to use the LineIntersectionIterator to find all intersections between a line segment and a Delaunay triangulation. This example shows the creation of a triangulation and then iterating through its intersections.

```rust
use spade::{LineIntersectionIterator, Point2, DelaunayTriangulation};
# use spade::InsertionError;
# fn main() -> Result<(), InsertionError> {
let vertices = vec![
    Point2::new(-30.0, 20.0),  // v0
    Point2::new(0.0, -20.0),   // v1
    Point2::new(0.0, 20.0),    // v2
    Point2::new(14.0, 0.0),    // v3
    Point2::new(30.0, 0.0),    // v4
];

let triangulation = DelaunayTriangulation::<_>::bulk_load_stable(vertices)?;
for intersection in LineIntersectionIterator::new(
    &triangulation,
    Point2::new(-30.0, 0.0),
    Point2::new(40.0, 0.0),
) {
    println!("{:?}", intersection);
}
# Ok(())
# }
```

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

### Setup Initial Two Vertices for Face Creation

Source: https://docs.rs/spade/latest/src/spade/delaunay_core/dcel_operations.rs.html

Initializes a DCEL with two vertices and a connecting edge, preparing for face creation.

```rust
let mut dcel = Dcel::<_>::default();
let v0 = super::append_unconnected_vertex(&mut dcel, 0);
let v1 = super::append_unconnected_vertex(&mut dcel, 1);
super::setup_initial_two_vertices(&mut dcel, v0, v1);
```

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

### Setup Initial Two Vertices in DCEL

Source: https://docs.rs/spade/latest/src/spade/delaunay_core/dcel_operations.rs.html

Initializes a DCEL with two vertices and a connecting edge, performing a sanity check.

```rust
let mut dcel = Dcel::<_>::default();
super::append_unconnected_vertex(&mut dcel, 0);
super::append_unconnected_vertex(&mut dcel, 1);

super::setup_initial_two_vertices(
    &mut dcel,
    FixedVertexHandle::new(0),
    FixedVertexHandle::new(1),
);

dcel.sanity_check();
```

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

### ConstrainedDelaunayTriangulation Example

Source: https://docs.rs/spade/latest/spade/struct.ConstrainedDelaunayTriangulation.html

Demonstrates how to create a ConstrainedDelaunayTriangulation, insert points, add constraint edges, and query constraint information.

```APIDOC
## §Example
```
use spade::{ConstrainedDelaunayTriangulation, Point2, Triangulation};
let mut cdt = ConstrainedDelaunayTriangulation::<Point2<_>>::new();
let v0 = cdt.insert(Point2::new(0f64, 0.0))?;
let v1 = cdt.insert(Point2::new(1.0, 0.0))?;
cdt.add_constraint(v0, v1);
// Alternatively, consider using this shorthand
cdt.add_constraint_edge(Point2::new(1.0, 1.0), Point2::new(1.0, 0.0))?;
println!("Number of constraints: {}", cdt.num_constraints()); // 2 constraints
// Constraints are bidirectional!
assert!(cdt.exists_constraint(v1, v0));
assert!(cdt.exists_constraint(v0, v1));
// Check if a new constraint could be added
let from = Point2::new(1.0, -2.0);
let to = Point2::new(1.0, 0.0);
if !cdt.intersects_constraint(from, to) {
    // No intersections, the edge can be added
    cdt.add_constraint_edge(from, to)?;
}
```
```

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

### Get Edge Start and End Positions

Source: https://docs.rs/spade/latest/src/spade/delaunay_core/handles/handle_impls.rs.html

Returns the start and end positions of this edge. The first position is `self.from().position()`, the second is `self.to().position()`.

```rust
pub fn positions(&self) -> [Point2<<V as HasPosition>::Scalar>; 2] {
        [self.from().position(), self.to().position()]
    }
```

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

### Example: Projecting Points onto an Edge

Source: https://docs.rs/spade/latest/src/spade/delaunay_core/handles/handle_impls.rs.html

Demonstrates how to use `project_point` to determine if a point lies before, on, or behind a given edge in a Delaunay triangulation.

```rust
# fn main() -> Result<(), spade::InsertionError> {
# use spade::{Point2, Triangulation, DelaunayTriangulation};
# 
# let from = Point2::new(0.0, 0.0);
# let to = Point2::new(2.0, 0.0);
# 
# let mut triangulation: DelaunayTriangulation<_> = Default::default();
# let v0 = triangulation.insert(from)?;
# let v1 = triangulation.insert(to)?;
# // This edge goes from "from" to "to"
# let edge = triangulation.get_edge_from_neighbors(v0, v1).unwrap();
# 
# // These vertices are all projected before the edge
# assert!(edge.project_point(Point2::new(-0.2, 0.0)).is_before_edge());
# assert!(edge.project_point(Point2::new(-1002.0, -12.0)).is_before_edge());
# 
# // These vertices are all projected onto the edge
# assert!(edge.project_point(Point2::new(1.0, 5.0)).is_on_edge());
# assert!(edge.project_point(Point2::new(0.5, -2.0)).is_on_edge());
# assert!(edge.project_point(Point2::new(1.0, 0.0)).is_on_edge());
# 
# // These vertices are all projected behind the edge
# assert!(edge.project_point(Point2::new(4.000001, 0.0)).is_behind_edge());
# assert!(edge.project_point(Point2::new(5.0, -12.0)).is_behind_edge());
# # Ok (()) 
# }
```

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

### Get Origin Vertex of a Directed Edge

Source: https://docs.rs/spade/latest/spade/internals/struct.DynamicHandleImpl.html

Returns the origin vertex of a directed edge. This is the starting point of the edge.

```rust
pub fn from(&self) -> VertexHandle<'a, V, DE, UE, F>
```

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

### Example Usage of LastUsedVertexHintGenerator

Source: https://docs.rs/spade/latest/spade/struct.LastUsedVertexHintGenerator.html

Demonstrates how to use LastUsedVertexHintGenerator with DelaunayTriangulation for point insertions. This setup is beneficial when queries are spatially clustered.

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

type LastUsedVertexTriangulation =
    DelaunayTriangulation<Point2<f64>, (), (), (), LastUsedVertexHintGenerator>;

let mut triangulation = LastUsedVertexTriangulation::new();
// Start using the triangulation, e.g. by inserting vertices
triangulation.insert(Point2::new(0.0, 0.0));
```

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

### Get Edge Positions

Source: https://docs.rs/spade/latest/spade/handles/type.DirectedEdgeHandle.html

Returns the start and end positions of the edge. The first position is from the origin vertex, the second from the destination vertex.

```rust
pub fn positions(&self) -> [Point2<<V as HasPosition>::Scalar>; 2]

```

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

### Bulk Load Function Signature and Initialization

Source: https://docs.rs/spade/latest/src/spade/delaunay_core/bulk_load.rs.html

The main entry point for the bulk loading algorithm. It handles empty input and calculates the initial center point by averaging all vertex positions.

```Rust
pub fn bulk_load<V, T>(mut elements: Vec<V>) -> Result<T, InsertionError>
where
    V: HasPosition,
    T: Triangulation<Vertex = V>,
{
    if elements.is_empty() {
        return Ok(T::new());
    }

    let mut point_sum = Point2::<f64>::new(0.0, 0.0);

    for element in &elements {
        crate::validate_vertex(element)?;
        let position = element.position();

        point_sum = point_sum.add(position.to_f64());
    }

    // Set the initial center to the average of all positions. This should be a good choice for most triangulations.
    //
    // The research paper uses a different approach by taking the center of the points' bounding box.
    // However, this position might be far off the center off mass if the triangulation has just a few outliers.
    // This could lead to a very uneven angle distribution as nearly all points are might be in a very small angle segment
    // around the center. This degrades the hull-structure's lookup and insertion performance.

```

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

### Get Edge Entry

Source: https://docs.rs/spade/latest/src/spade/delaunay_core/handles/handle_impls.rs.html

Internal helper to get the edge entry from the DCEL.

```rust
fn entry(&self) -> &'a EdgeEntry<DE, UE> {
        self.dcel.edge_entry(self.handle.as_undirected())
    }
```

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

### Create and Configure RefinementParameters

Source: https://docs.rs/spade/latest/spade/struct.RefinementParameters.html

Demonstrates how to create and configure RefinementParameters for Delaunay refinement. This includes setting an angle limit, minimum and maximum allowed triangle areas, and excluding outer faces.

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

fn refine_cdt(cdt: &mut ConstrainedDelaunayTriangulation<Point2<f64>>) {
    let params = RefinementParameters::<f64>::new()
        .exclude_outer_faces(true)
        .keep_constraint_edges()
        .with_min_required_area(0.0001)
        .with_max_allowed_area(0.5)
        .with_angle_limit(AngleLimit::from_deg(25.0));

    cdt.refine(params);
}
```

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

### ConstrainedDelaunayTriangulation Example

Source: https://docs.rs/spade/latest/src/spade/cdt.rs.html

Demonstrates how to create a CDT, add constraint edges using vertex handles or point pairs, and check for existing constraints. It also shows how to check for intersections before adding a new constraint.

```rust
use spade::{ConstrainedDelaunayTriangulation, Point2, Triangulation};
# fn try_main() -> Result<(), spade::InsertionError> {
let mut cdt = ConstrainedDelaunayTriangulation::<Point2<_>>::new();
let v0 = cdt.insert(Point2::new(0f64, 0.0))?;
let v1 = cdt.insert(Point2::new(1.0, 0.0))?;
cdt.add_constraint(v0, v1);
// Alternatively, consider using this shorthand
cdt.add_constraint_edge(Point2::new(1.0, 1.0), Point2::new(1.0, 0.0))?;
println!("Number of constraints: {}", cdt.num_constraints()); // 2 constraints
// Constraints are bidirectional!
assert!(cdt.exists_constraint(v1, v0));
assert!(cdt.exists_constraint(v0, v1));
// Check if a new constraint could be added
let from = Point2::new(1.0, -2.0);
let to = Point2::new(1.0, 0.0);
if !cdt.intersects_constraint(from, to) {
    // No intersections, the edge can be added
    cdt.add_constraint_edge(from, to)?;
}
# Ok(()) }
# fn main() { try_main().unwrap() }
```

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

### Interpolate with Estimated Gradients

Source: https://docs.rs/spade/latest/src/spade/delaunay_core/interpolation.rs.html

Example of using `interpolate_gradient` where gradients are estimated on-the-fly or pre-calculated. This is useful when gradient data is not directly available.

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

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

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

let mut triangulation: DelaunayTriangulation<PointWithHeight> = Default::default();
// Insert some points into the triangulation
triangulation.insert(PointWithHeight { position: Point2::new(10.0, 10.0), height: 0.0 });
triangulation.insert(PointWithHeight { position: Point2::new(10.0, -10.0), height: 0.0 });
triangulation.insert(PointWithHeight { position: Point2::new(-10.0, 10.0), height: 0.0 });
triangulation.insert(PointWithHeight { position: Point2::new(-10.0, -10.0), height: 0.0 });

let nn = triangulation.natural_neighbor();

// Interpolate point at coordinates (1.0, 2.0).
let query_point = Point2::new(1.0, 2.0);
// Let's interpolate the value with estimated gradients. The gradient is the direction of steepest ascent for the function at that point
let value: f64 = nn.interpolate_gradient(|v| v.data().height, |v| nn.estimate_gradient(v, |h| h.data().height), 1.0, query_point).unwrap();

// could also have gone and calculated all grads upfront like this, notice the s in gradients
let grads = nn.estimate_gradients(|v| v.data().height);
let value: f64 = nn.interpolate_gradient(|v| v.data().height, &grads, 1.0, query_point).unwrap();

```

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

### Example of using mitigate_underflow

Source: https://docs.rs/spade/latest/spade/fn.mitigate_underflow.html

Demonstrates how to use `mitigate_underflow` to correct a position that would otherwise cause an `InsertionError::TooSmall` when inserted into a Delaunay triangulation.

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

let mut triangulation = DelaunayTriangulation::<_>::default();

let invalid_position = Point2::new(1.0e-44, 42.0);
// Oh no! We're not allowed to insert that point!
assert_eq!(
    triangulation.insert(invalid_position),
    Err(InsertionError::TooSmall)
);

let valid_position = spade::mitigate_underflow(invalid_position);

// That's better!
assert!(triangulation.insert(valid_position).is_ok());

// But keep in mind that the position has changed:
assert_ne!(invalid_position, valid_position);
assert_eq!(valid_position, Point2::new(0.0, 42.0));

```

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

### type_id

Source: https://docs.rs/spade/latest/spade/iterators/struct.VerticesInShapeIterator.html

Gets the TypeId of self. This is part of the Any trait implementation.

```APIDOC
## fn type_id(&self) -> TypeId

### Description
Gets the `TypeId` of `self`.

### Returns
- `TypeId`: The unique identifier for the type of `self`.
```

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

### Get Vertex Data

Source: https://docs.rs/spade/latest/spade/handles/type.VertexHandle.html

Returns a reference to the data associated with the vertex.

```rust
pub fn data(&self) -> &V
```

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

### Bulk Load Constrained Delaunay Triangulation with Epsilon Grid

Source: https://docs.rs/spade/latest/src/spade/delaunay_core/bulk_load.rs.html

Demonstrates bulk loading a Constrained Delaunay Triangulation (CDT) with vertices from an epsilon grid and a set of edges forming a zig-zag pattern. The CDT is then sanity-checked.

```rust
    #[test]
    fn test_cdt_bulk_load_on_epsilon_grid() -> Result<(), InsertionError> {
        const GRID_SIZE: usize = 20;

        let vertices = get_epsilon_grid(GRID_SIZE);
        // Creates a zig zag pattern
        let edges = (0..vertices.len() - 1).map(|i| [i, i + 1]).collect();

        let triangulation = ConstrainedDelaunayTriangulation::<_>::bulk_load_cdt(vertices, edges)?;

        triangulation.cdt_sanity_check();
        assert_eq!(triangulation.num_vertices(), GRID_SIZE * GRID_SIZE);
        assert_eq!(triangulation.num_constraints(), GRID_SIZE * GRID_SIZE - 1);
        Ok(())
    }
```

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

### Bulk Load Delaunay Triangulation with Integer Grid

Source: https://docs.rs/spade/latest/src/spade/delaunay_core/bulk_load.rs.html

Demonstrates bulk loading vertices that lie on integer coordinates, which can sometimes provoke special situations like points on lines. The triangulation is then sanity-checked.

```rust
    {
        // Inserts vertices on whole integer coordinates. This tends provokes special situations,
        // e.g. points being inserted exactly on a line.
        let mut rng = rand::rngs::StdRng::from_seed(*SEED2);
        const TEST_REPETITIONS: usize = 30;
        const GRID_SIZE: usize = 20;

        for _ in 0..TEST_REPETITIONS {
            let mut vertices = Vec::with_capacity(GRID_SIZE * GRID_SIZE);
            for x in 0..GRID_SIZE {
                for y in 0..GRID_SIZE {
                    vertices.push(Point2::new(x as f64, y as f64));
                }
            }

            vertices.shuffle(&mut rng);
            let triangulation = DelaunayTriangulation::<_>::bulk_load(vertices)?;
            assert_eq!(triangulation.num_vertices(), GRID_SIZE * GRID_SIZE);
            triangulation.sanity_check();
        }
        Ok(())
    }
```

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

### Get Vertex by Handle

Source: https://docs.rs/spade/latest/src/spade/triangulation.rs.html

Retrieves a specific vertex using its fixed handle.

```APIDOC
## get_vertex

### Description
Get a vertex by its index. To get the handle, wrap your local index in a FixedVertexHandle: `let handle = FixedVertexHandle::from_index(my_index);`

### Method
`&self`

### Parameters
#### Path Parameters
- **handle** (FixedVertexHandle) - Required - The handle to the vertex.

#### Return Value
- `Option<VertexHandle>` - An optional vertex handle if found.
```

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

### Insert Points and Add Constraint to CDT

Source: https://docs.rs/spade/latest/src/spade/cdt.rs.html

Demonstrates initializing a CDT, inserting multiple points, adding a constraint between two vertices, and performing a sanity check.

```rust
let mut cdt = Cdt::new();
cdt.insert(Point2::new(-8.403036273981348, -0.2248814041797189))?;
cdt.insert(Point2::new(-8.353215494321136, 0.6088667888877364))?;
cdt.insert(Point2::new(-7.811923439447166, -0.20003314976217013))?;
cdt.insert(Point2::new(-7.710431174668773, 0.40691184742787456))?;

let v0 = cdt.insert(Point2::new(-8.907731924022768, 1.7433952434737847))?;
let v1 = cdt.insert(Point2::new(-7.899415172394501, -1.4867902598716558))?;
cdt.cdt_sanity_check();
cdt.add_constraint(v0, v1);
cdt.cdt_sanity_check();
Ok(())
```

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

### Get Face Data

Source: https://docs.rs/spade/latest/src/spade/delaunay_core/handles/handle_impls.rs.html

Retrieves the user-defined data associated with a face handle.

```rust
pub fn data(&self) -> &F {
        self.dcel.face_data(self.handle)
    }
```

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

### DirectedVoronoiEdge::prev

Source: https://docs.rs/spade/latest/src/spade/delaunay_core/handles/public_handles.rs.html

Gets the previous directed Voronoi edge in clockwise order.

```APIDOC
## DirectedVoronoiEdge::prev

### Description
Returns the edge that is connected to this edge in clockwise order.

### Signature
`pub fn prev(&self) -> DirectedVoronoiEdge<'a, V, DE, UE, F>`

### Returns
The previous `DirectedVoronoiEdge` in clockwise order.
```

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

### initialize_from_triangulation Method Signature

Source: https://docs.rs/spade/latest/spade/trait.HintGenerator.html

Creates and initializes a new hint generator from an existing triangulation. This is useful for setting up hints based on a pre-existing structure.

```rust
fn initialize_from_triangulation<TR, V>(triangulation: &TR) -> Self
       where TR: Triangulation<Vertex = V>,
             V: HasPosition<Scalar = S>;
```

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

### DirectedVoronoiEdge::next

Source: https://docs.rs/spade/latest/src/spade/delaunay_core/handles/public_handles.rs.html

Gets the next directed Voronoi edge in counterclockwise order.

```APIDOC
## DirectedVoronoiEdge::next

### Description
Returns the edge that is connected to this edge in counterclockwise order.

### Signature
`pub fn next(&self) -> DirectedVoronoiEdge<'a, V, DE, UE, F>`

### Returns
The next `DirectedVoronoiEdge` in counterclockwise order.
```

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

### NaturalNeighbor Interpolation with Provided Gradients

Source: https://docs.rs/spade/latest/spade/struct.NaturalNeighbor.html

This example demonstrates how to use the `interpolate_gradient` method with pre-calculated gradients for each vertex. It assumes a `PointWithData` struct that includes position, height, and gradient information.

```APIDOC
## `NaturalNeighbor::interpolate_gradient` with Provided Gradients

### Description
Interpolates a value at a given query point using natural neighbor coordinates and provided gradients at each vertex. This method is suitable when gradients are known or have been pre-calculated.

### Method
`interpolate_gradient`

### Parameters
#### Path Parameters
None

#### Query Parameters
None

#### Request Body
None

### Function Signature
```rust
pub fn interpolate_gradient<F, G>( &self, vertex_value_fn: F, vertex_gradient_fn: G, scale: <V as HasPosition>::Scalar, query_point: Point2<<V as HasPosition>::Scalar>, ) -> Option<<V as HasPosition>::Scalar>
where
    F: Fn(VertexHandle<'_, V, DE, UE, F>) -> <V as HasPosition>::Scalar,
    G: Fn(VertexHandle<'_, V, DE, UE, F>) -> [<V as HasPosition>::Scalar; 2],
```

### Request Example
```rust
use spade::{DelaunayTriangulation, HasPosition, Point2};

struct PointWithData {
    position: Point2<f64>,
    height: f64,
    grad: [f64; 2],
}

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

let mut triangulation: DelaunayTriangulation<PointWithData> = Default::default();
triangulation.insert(PointWithData { position: Point2::new(10.0, 10.0), height: 0.0, grad: [-1., -1.] });
triangulation.insert(PointWithData { position: Point2::new(10.0, -10.0), height: 0.0, grad: [-1., 1.] });
triangulation.insert(PointWithData { position: Point2::new(-10.0, 10.0), height: 0.0, grad: [1., -1.] });
triangulation.insert(PointWithData { position: Point2::new(-10.0, -10.0), height: 0.0, grad: [1., 1.] });

let nn = triangulation.natural_neighbor();
let query_point = Point2::new(1.0, 2.0);
let value: f64 = nn.interpolate_gradient(|v| v.data().height, |v| v.data().grad, 1.0, query_point).unwrap();
```

### Response
#### Success Response (200)
Returns the interpolated value at the query point.

#### Response Example
```rust
// Example value (actual value depends on triangulation and query point)
let value: f64 = 0.5;
```
```

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

### DirectedVoronoiEdge::from

Source: https://docs.rs/spade/latest/src/spade/delaunay_core/handles/public_handles.rs.html

Gets the origin Voronoi vertex of a directed Voronoi edge.

```APIDOC
## DirectedVoronoiEdge::from

### Description
Returns the Voronoi vertex from which this directed Voronoi edge originates. If the edge is associated with an inner face, it returns the inner vertex; otherwise, it returns the outer vertex.

### Signature
`pub fn from(&self) -> VoronoiVertex<'a, V, DE, UE, F>`

### Returns
The origin `VoronoiVertex`.
```

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

### Hull Construction and Incremental Insertion

Source: https://docs.rs/spade/latest/src/spade/delaunay_core/bulk_load.rs.html

Demonstrates creating a triangulation, inserting initial points, constructing a hull, and then performing incremental insertions of new points, checking hull sanity after each step.

```rust
    #[test]
    fn test_hull() -> Result<(), InsertionError> {
        let mut triangulation = DelaunayTriangulation::<_>::new();
        triangulation.insert(Point2::new(1.0, 1.0))?;
        triangulation.insert(Point2::new(1.0, -1.0))?;
        triangulation.insert(Point2::new(-1.0, 1.0))?;
        triangulation.insert(Point2::new(-1.0, -1.0))?;

        let mut hull = Hull::from_triangulation(&triangulation, Point2::new(0.0, 0.0)).unwrap();
        super::hull_sanity_check(&triangulation, &hull);

        let additional_elements = [
            Point2::new(0.4, 2.0),
            Point2::new(-0.4, 3.0),
            Point2::new(-0.4, -4.0),
            Point2::new(3.0, 5.0),
        ];

        for (index, element) in additional_elements.iter().enumerate() {
            assert!(super::single_bulk_insertion_step(
                &mut triangulation,
                false,
                &mut hull,
                VertexToInsert::NewVertex(*element),
                &mut Vec::new(),
            )
            .is_none());

            if index != 0 {
                super::hull_sanity_check(&triangulation, &hull)
            }
        }
        Ok(())
    }
```

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

### DirectedVoronoiEdge::to

Source: https://docs.rs/spade/latest/src/spade/delaunay_core/handles/public_handles.rs.html

Gets the destination Voronoi vertex of a directed Voronoi edge.

```APIDOC
## DirectedVoronoiEdge::to

### Description
Returns the destination Voronoi vertex of this directed Voronoi edge.

### Signature
`pub fn to(&self) -> VoronoiVertex<'a, V, DE, UE, F>`

### Returns
The destination `VoronoiVertex`.
```

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

### Get Squared Edge Length

Source: https://docs.rs/spade/latest/spade/handles/type.UndirectedEdgeHandle.html

Calculates and returns the squared length of the edge.

```rust
pub fn length_2(&self) -> V::Scalar

```

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

### Create and Insert into DelaunayTriangulation

Source: https://docs.rs/spade/latest/spade/trait.Triangulation.html

Demonstrates creating a new DelaunayTriangulation and inserting points, showing the change in vertex, face, and edge counts.

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

let mut triangulation: DelaunayTriangulation<Point2<f64>> = DelaunayTriangulation::new();
// An empty triangulation has no vertices and one face
assert_eq!(triangulation.num_vertices(), 0);
assert_eq!(triangulation.num_all_faces(), 1);
assert_eq!(triangulation.num_inner_faces(), 0); // This count excludes the outer face
assert_eq!(triangulation.num_directed_edges(), 0);

triangulation.insert(Point2::new(0.0, 1.0));
assert_eq!(triangulation.num_vertices(), 1);
assert_eq!(triangulation.num_inner_faces(), 0);

triangulation.insert(Point2::new(1.0, 1.0));
// Two vertices define the first edge
assert_eq!(triangulation.num_undirected_edges(), 1);

triangulation.insert(Point2::new(1.0, 0.0));
assert_eq!(triangulation.num_vertices(), 3);
assert_eq!(triangulation.num_inner_faces(), 1);
```

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

### Get Vertex Position

Source: https://docs.rs/spade/latest/spade/handles/type.VertexHandle.html

Retrieves the 2D position of the vertex associated with the handle.

```rust
pub fn position(&self) -> Point2<V::Scalar>
```

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

### impl<T> CloneToUninit for T

Source: https://docs.rs/spade/latest/spade/enum.InsertionError.html

Provides an experimental, nightly-only API for cloning data to an uninitialized memory location.

```APIDOC
## unsafe fn clone_to_uninit(&self, dest: *mut u8)

### Description
🔬This is a nightly-only experimental API. (`clone_to_uninit`)
Performs copy-assignment from `self` to `dest`.

### Method
`clone_to_uninit`

### Parameters
- `self`: A reference to the value to be cloned.
- `dest`: A raw pointer to the uninitialized memory location where the data will be cloned.
```

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

### Initialize DCEL with Fixed Vertices

Source: https://docs.rs/spade/latest/src/spade/delaunay_core/dcel_operations.rs.html

Creates a new DCEL with pre-defined vertices and sets up the initial two vertices. Useful for starting with known points.

```rust
pub fn new_with_fixed_vertices<V, DE, UE, F>(
    vertices: Vec<V>,
    first_vertex: FixedVertexHandle,
    second_vertex: FixedVertexHandle,
) -> Dcel<V, DE, UE, F>
where
    DE: Default,
    UE: Default,
    F: Default,
{
    let vertices_len = vertices.len();

    let mut result = Dcel {
        vertices:
            vertices
                .into_iter()
                .map(|v| VertexEntry {
                    data: v,
                    out_edge: None,
                })
                .collect(),
        faces: Vec::with_capacity(vertices_len * 2),
        edges: Vec::with_capacity(vertices_len * 3),
    };

    let outer_face = FaceEntry {
        adjacent_edge: None,
        data: F::default(),
    };
    result.faces.push(outer_face);

    setup_initial_two_vertices(&mut result, first_vertex, second_vertex);

    result
}
```

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

### Vertex Count and Iterators

Source: https://docs.rs/spade/latest/src/spade/triangulation.rs.html

Methods to get the total number of vertices and iterators to traverse them.

```APIDOC
## num_vertices

### Description
Returns the number of vertices in this triangulation.

### Method
`&self`

### Return Value
- `usize` - The number of vertices.
```

```APIDOC
## vertices

### Description
An iterator visiting all vertices. The iterator type is [VertexHandle].

### Method
`&self`

### Return Value
- `VertexIterator` - An iterator over vertices.
```

```APIDOC
## fixed_vertices

### Description
An iterator visiting all vertices. The iterator type is [FixedVertexHandle].

### Method
`&self`

### Return Value
- `FixedVertexIterator` - An iterator over fixed vertices.
```

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

### CloneToUninit

Source: https://docs.rs/spade/latest/spade/iterators/struct.EdgesInShapeIterator.html

Performs copy-assignment from self to a destination pointer. This is a nightly-only experimental API.

```APIDOC
## unsafe fn clone_to_uninit(&self, dest: *mut u8)

### Description
Performs copy-assignment from `self` to `dest`.

### Method
`clone_to_uninit`

### Parameters
* `dest` (*mut u8) - The destination pointer to copy to.
```

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

### DelaunayElementType for FaceTag

Source: https://docs.rs/spade/latest/src/spade/delaunay_core/handles/handle_defs.rs.html

Implements the DelaunayElementType trait for FaceTag to get the number of faces from a DCEL.

```rust
impl DelaunayElementType for FaceTag {
    fn num_elements<V, DE, UE, F>(dcel: &Dcel<V, DE, UE, F>) -> usize {
        dcel.num_faces()
    }
}
```

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

### DelaunayElementType for VertexTag

Source: https://docs.rs/spade/latest/src/spade/delaunay_core/handles/handle_defs.rs.html

Implements the DelaunayElementType trait for VertexTag to get the number of vertices from a DCEL.

```rust
impl DelaunayElementType for VertexTag {
    fn num_elements<V, DE, UE, F>(dcel: &Dcel<V, DE, UE, F>) -> usize {
        dcel.num_vertices()
    }
}
```

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

### Bulk Load CDT with Vertices and Edges

Source: https://docs.rs/spade/latest/src/spade/cdt.rs.html

Demonstrates how to initialize a Constrained Delaunay Triangulation by bulk loading vertices and edges. The `try_bulk_load_cdt` function is used for this purpose, followed by a sanity check.

```rust
let vertices = vec![(0.0, 0.0), (100.0, 0.0), (0.0, 100.0)]
            .iter()
            .copied()
            .map(|(x, y)| Point2::new(x, y))
            .collect::<Vec<_>>();
        let edges = vec![(0, 1), (1, 2)];
        let result = ConstrainedDelaunayTriangulation::<Point2<f32>>::try_bulk_load_cdt(
            vertices,
            edges,
            |_| {},
        )
        .unwrap();

        result.cdt_sanity_check();
```

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

### Any Trait Implementation

Source: https://docs.rs/spade/latest/spade/internals/struct.FixedHandleImpl.html

Provides runtime type information.

```APIDOC
## fn type_id(&self) -> TypeId

### Description
Gets the `TypeId` of `self`.

### Method
`type_id`

### Parameters
- **self**: `&T` - A reference to the object.

### Response
- **TypeId** - The unique identifier for the type of `self`.
```

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

### Get Directed Edge Data

Source: https://docs.rs/spade/latest/spade/handles/type.DirectedEdgeHandle.html

Returns a reference to the data associated with this directed edge.

```rust
pub fn data(&self) -> &'a DE

```

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

### Get Adjacent Face

Source: https://docs.rs/spade/latest/spade/handles/type.DirectedEdgeHandle.html

Returns the handle to the face located to the left of this directed edge.

```rust
pub fn face(&self) -> FaceHandle<'a, PossiblyOuterTag, V, DE, UE, F>

```

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

### Natural Neighbor Interpolation Example

Source: https://docs.rs/spade/latest/spade/struct.NaturalNeighbor.html

Demonstrates how to create and use the NaturalNeighbor object for interpolating values at query points. It highlights the performance benefit of re-using the interpolation object.

```rust
use spade::{Point2, HasPosition, DelaunayTriangulation, InsertionError, Triangulation as _};

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

impl HasPosition for PointWithHeight {
    type Scalar = f64;

    fn position(&self) -> Point2<f64> {
        self.position
    }
}

fn main() -> Result<(), InsertionError> {
    let mut t = DelaunayTriangulation::<PointWithHeight>::new();
    t.insert(PointWithHeight { position: Point2::new(-1.0, -1.0), height: 42.0})?;
    t.insert(PointWithHeight { position: Point2::new(-1.0, 1.0), height: 13.37})?;
    t.insert(PointWithHeight { position: Point2::new(1.0, -1.0), height: 27.18})?;
    t.insert(PointWithHeight { position: Point2::new(1.0, 1.0), height: 31.41})?;

    // Set of query points (would be many more realistically):
    let query_points = [Point2::new(0.0, 0.1), Point2::new(0.5, 0.1)];

    // Good: Re-use interpolation object!
    let nn = t.natural_neighbor();
    for p in &query_points {
        println!("Value at {:?}: {:?}", p, nn.interpolate(|v| v.data().height, *p));
    }

    // Bad (slower): Don't re-use internal buffers
    for p in &query_points {
        println!("Value at {:?}: {:?}", p, t.natural_neighbor().interpolate(|v| v.data().height, *p));
    }
    Ok(())
}
```

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

### Create a New Delaunay Triangulation

Source: https://docs.rs/spade/latest/src/spade/triangulation.rs.html

Demonstrates how to create an empty Delaunay triangulation and insert points. An empty triangulation initially has no vertices and one outer face.

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

let mut triangulation: DelaunayTriangulation<Point2<f64>> = DelaunayTriangulation::new();
// An empty triangulation has no vertices and one face
assert_eq!(triangulation.num_vertices(), 0);
assert_eq!(triangulation.num_all_faces(), 1);
assert_eq!(triangulation.num_inner_faces(), 0); // This count excludes the outer face
assert_eq!(triangulation.num_directed_edges(), 0);

triangulation.insert(Point2::new(0.0, 1.0));
assert_eq!(triangulation.num_vertices(), 1);
assert_eq!(triangulation.num_inner_faces(), 0);

triangulation.insert(Point2::new(1.0, 1.0));

```

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

### Get Edge Destination Vertex

Source: https://docs.rs/spade/latest/spade/handles/type.DirectedEdgeHandle.html

Returns the handle to the destination vertex of the directed edge.

```rust
pub fn to(&self) -> VertexHandle<'a, V, DE, UE, F>

```

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

### Get Edge Origin Vertex

Source: https://docs.rs/spade/latest/spade/handles/type.DirectedEdgeHandle.html

Returns the handle to the origin vertex of the directed edge.

```rust
pub fn from(&self) -> VertexHandle<'a, V, DE, UE, F>

```

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

### Basic DelaunayTriangulation Usage

Source: https://docs.rs/spade/latest/spade/struct.DelaunayTriangulation.html

Demonstrates how to create a new DelaunayTriangulation, insert vertices, and assert basic properties like the number of vertices, inner faces, and edges.

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

fn main() -> Result<(), InsertionError> {

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

   // Insert three vertices that span one triangle (face)
   triangulation.insert(Point2::new(0.0, 1.0))?;
   triangulation.insert(Point2::new(1.0, 1.0))?;
   triangulation.insert(Point2::new(0.5, -1.0))?;

   assert_eq!(triangulation.num_vertices(), 3);
   assert_eq!(triangulation.num_inner_faces(), 1);
   assert_eq!(triangulation.num_undirected_edges(), 3);
   Ok(())
}
```

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

### Get Dual Voronoi Edge

Source: https://docs.rs/spade/latest/spade/handles/type.UndirectedEdgeHandle.html

Retrieves the corresponding edge in the dual Voronoi diagram.

```rust
pub fn as_voronoi_edge(&self) -> UndirectedVoronoiEdge<'a, V, DE, UE, F>

```
Tokens:
Raw