Trait spade::Triangulation

pub trait Triangulation: Default {
    type Vertex: HasPosition;
    type DirectedEdge: Default;
    type UndirectedEdge: Default;
    type Face: Default;
    type HintGenerator: HintGenerator<<Self::Vertex as HasPosition>::Scalar>;

    // Provided methods
    fn new() -> Self { ... }
    fn with_capacity(
        num_vertices: usize,
        num_undirected_edges: usize,
        num_faces: usize
    ) -> Self { ... }
    fn clear(&mut self) { ... }
    fn bulk_load(elements: Vec<Self::Vertex>) -> Result<Self, InsertionError> { ... }
    fn vertex(
        &self,
        handle: FixedVertexHandle
    ) -> VertexHandle<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face> { ... }
    fn vertex_data_mut(
        &mut self,
        handle: FixedVertexHandle
    ) -> &mut Self::Vertex { ... }
    fn face<InnerOuter: InnerOuterMarker>(
        &self,
        handle: FixedFaceHandle<InnerOuter>
    ) -> FaceHandle<'_, InnerOuter, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face> { ... }
    fn outer_face(
        &self
    ) -> FaceHandle<'_, PossiblyOuterTag, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face> { ... }
    fn directed_edge(
        &self,
        handle: FixedDirectedEdgeHandle
    ) -> DirectedEdgeHandle<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face> { ... }
    fn undirected_edge(
        &self,
        handle: FixedUndirectedEdgeHandle
    ) -> UndirectedEdgeHandle<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face> { ... }
    fn undirected_edge_data_mut(
        &mut self,
        handle: FixedUndirectedEdgeHandle
    ) -> &mut Self::UndirectedEdge { ... }
    fn num_all_faces(&self) -> usize { ... }
    fn num_inner_faces(&self) -> usize { ... }
    fn num_undirected_edges(&self) -> usize { ... }
    fn num_directed_edges(&self) -> usize { ... }
    fn convex_hull_size(&self) -> usize { ... }
    fn directed_edges(
        &self
    ) -> DirectedEdgeIterator<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face> { ... }
    fn undirected_edges(
        &self
    ) -> UndirectedEdgeIterator<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face> { ... }
    fn num_vertices(&self) -> usize { ... }
    fn vertices(
        &self
    ) -> VertexIterator<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face> { ... }
    fn fixed_vertices(&self) -> FixedVertexIterator { ... }
    fn all_faces(
        &self
    ) -> FaceIterator<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face> { ... }
    fn inner_faces(
        &self
    ) -> InnerFaceIterator<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face> { ... }
    fn voronoi_faces(
        &self
    ) -> VoronoiFaceIterator<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face> { ... }
    fn directed_voronoi_edges(
        &self
    ) -> DirectedVoronoiEdgeIterator<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face> { ... }
    fn undirected_voronoi_edges(
        &self
    ) -> UndirectedVoronoiEdgeIterator<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face> { ... }
    fn locate(
        &self,
        point: Point2<<Self::Vertex as HasPosition>::Scalar>
    ) -> PositionInTriangulation { ... }
    fn locate_vertex(
        &self,
        point: Point2<<Self::Vertex as HasPosition>::Scalar>
    ) -> Option<VertexHandle<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face>> { ... }
    fn get_edge_from_neighbors(
        &self,
        from: FixedVertexHandle,
        to: FixedVertexHandle
    ) -> Option<DirectedEdgeHandle<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face>> { ... }
    fn locate_with_hint(
        &self,
        point: Point2<<Self::Vertex as HasPosition>::Scalar>,
        hint: FixedVertexHandle
    ) -> PositionInTriangulation { ... }
    fn insert_with_hint(
        &mut self,
        t: Self::Vertex,
        hint: FixedVertexHandle
    ) -> Result<FixedVertexHandle, InsertionError> { ... }
    fn locate_and_remove(
        &mut self,
        point: Point2<<Self::Vertex as HasPosition>::Scalar>
    ) -> Option<Self::Vertex> { ... }
    fn remove(&mut self, vertex: FixedVertexHandle) -> Self::Vertex { ... }
    fn insert(
        &mut self,
        vertex: Self::Vertex
    ) -> Result<FixedVertexHandle, InsertionError> { ... }
    fn fixed_undirected_edges(&self) -> FixedUndirectedEdgeIterator { ... }
    fn fixed_directed_edges(&self) -> FixedDirectedEdgeIterator { ... }
    fn fixed_all_faces(&self) -> FixedFaceIterator { ... }
    fn fixed_inner_faces(&self) -> FixedInnerFaceIterator { ... }
    fn all_vertices_on_line(&self) -> bool { ... }
    fn convex_hull(
        &self
    ) -> HullIterator<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face> { ... }
    fn face_data_mut<InnerOuter: InnerOuterMarker>(
        &mut self,
        handle: FixedFaceHandle<InnerOuter>
    ) -> &mut Self::Face { ... }
    fn directed_edge_data_mut(
        &mut self,
        handle: FixedDirectedEdgeHandle
    ) -> &mut Self::DirectedEdge { ... }
}

Defines common operations on triangulations.

These operations are both available for ConstrainedDelaunayTriangulations as well as regular DelaunayTriangulations.

Required Associated Types

type Vertex: HasPosition

The triangulation’s vertex type.

type DirectedEdge: Default

The triangulation’s edge type. Any new edge is created by using the Default trait.

type UndirectedEdge: Default

The triangulation’s undirected edge type. Any new edge is created by using the Default trait.

type Face: Default

The triangulation’s face type. Any new face is created by using the Default trait.

type HintGenerator: HintGenerator<<Self::Vertex as HasPosition>::Scalar>

The hint generator used by the triangulation. See HintGenerator for more information.

Provided Methods

fn new() -> Self

Creates a new triangulation.

A newly created triangulation contains no vertices, no edges and the single outer face.

Example

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);

fn with_capacity( num_vertices: usize, num_undirected_edges: usize, num_faces: usize ) -> Self

Creates a new triangulation and pre-allocates some space for vertices, edges and faces

fn clear(&mut self)

Removes all edges, faces and vertices from the triangulation.

This method does not change the allocated internal capacity.

fn bulk_load(elements: Vec<Self::Vertex>) -> Result<Self, InsertionError>

Creates a new triangulation populated with some vertices.

This will usually be more efficient than inserting the elements sequentially by calling insert.

Returns an InsertionError if any input coordinate is invalid. This method should never fail if all vertices were successfully checked with crate::validate_vertex.

Runtime

This method has a run time of O(n) but will run near linearly in practice. The runtime can be as worse as O(n²) if the inputs are very degenerate, e.g. if all input vertices lie on the same line.

Comparison to incremental insertion

This graph shows the difference between incremental and bulk loading for a different number of random points - bulk loading becomes more efficient very quickly.

fn vertex( &self, handle: FixedVertexHandle ) -> VertexHandle<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face>

Converts a fixed vertex handle to a reference vertex handle.

See also the handles module for more information.

fn vertex_data_mut(&mut self, handle: FixedVertexHandle) -> &mut Self::Vertex

Returns a mutable reference to the associated data of a vertex.

fn face<InnerOuter: InnerOuterMarker>( &self, handle: FixedFaceHandle<InnerOuter> ) -> FaceHandle<'_, InnerOuter, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face>

Converts a fixed face handle to a reference face handle.

See also the handles module for more information.

fn outer_face( &self ) -> FaceHandle<'_, PossiblyOuterTag, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face>

Returns a reference handle to the single outer face of this triangulation.

fn directed_edge( &self, handle: FixedDirectedEdgeHandle ) -> DirectedEdgeHandle<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face>

Converts a fixed directed edge handle handle to a reference directed edge handle.

See also the handles module for more information.

fn undirected_edge( &self, handle: FixedUndirectedEdgeHandle ) -> UndirectedEdgeHandle<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face>

Converts a fixed undirected edge handle to a reference undirected edge handle.

See also the handles module for more information.

fn undirected_edge_data_mut( &mut self, handle: FixedUndirectedEdgeHandle ) -> &mut Self::UndirectedEdge

Returns a mutable reference ot the associated data of an undirected edge.

fn num_all_faces(&self) -> usize

Returns the number of all faces, including the single outer face, of this triangulation.

This is always equal to triangulation.num_inner_faces() + 1.

fn num_inner_faces(&self) -> usize

Returns the number of inner faces in this triangulation.

fn num_undirected_edges(&self) -> usize

Returns the number of undirected edges in this triangulation.

fn num_directed_edges(&self) -> usize

Returns the number of directed edges in this triangulation.

fn convex_hull_size(&self) -> usize

Returns the number of edges of the convex hull.

See also convex_hull

Complexity

This method does not need to iterate through the convex hull and has a complexity of O(1)

fn directed_edges( &self ) -> DirectedEdgeIterator<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face>

An iterator visiting all directed edges.

The iterator type is DirectedEdgeHandle.

fn undirected_edges( &self ) -> UndirectedEdgeIterator<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face>

An iterator over all undirected edges.

The iterator type is UndirectedEdgeHandle

fn num_vertices(&self) -> usize

Returns the number vertices in this triangulation.

fn vertices( &self ) -> VertexIterator<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face>

An iterator visiting all vertices.

The iterator type is VertexHandle

fn fixed_vertices(&self) -> FixedVertexIterator

An iterator visiting all vertices.

The iterator type is FixedVertexHandle

fn all_faces( &self ) -> FaceIterator<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face>

An iterator visiting all faces.

The first returned face is the outer face, all other faces will be inner faces. The iterator type is FaceHandle<PossiblyOuterTag, …>.

See also inner_faces()

fn inner_faces( &self ) -> InnerFaceIterator<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face>

An iterator visiting all inner faces. The iterator type is FaceHandle<InnerTag, …>.

fn voronoi_faces( &self ) -> VoronoiFaceIterator<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face>

An iterator visiting all faces of the Voronoi diagram.

The iterator type is VoronoiFace

fn directed_voronoi_edges( &self ) -> DirectedVoronoiEdgeIterator<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face>

An iterator visiting all directed voronoi edges.

The iterator type is (DirectedVoronoiEdge)crate::handles::DirectedVoronoiEdge

fn undirected_voronoi_edges( &self ) -> UndirectedVoronoiEdgeIterator<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face>

An iterator visiting all undirected voronoi edges.

The iterator type is (UndirectedVoronoiEdge)crate::handles::UndirectedVoronoiEdge

fn locate( &self, point: Point2<<Self::Vertex as HasPosition>::Scalar> ) -> PositionInTriangulation

Returns information about the location of a point in a triangulation.

fn locate_vertex( &self, point: Point2<<Self::Vertex as HasPosition>::Scalar> ) -> Option<VertexHandle<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face>>

Locates a vertex at a given position.

Returns None if the point could not be found.

fn get_edge_from_neighbors( &self, from: FixedVertexHandle, to: FixedVertexHandle ) -> Option<DirectedEdgeHandle<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face>>

Returns an edge between two vertices.

If the edge does not exist, None is returned. This operation runs in O(n) time, where n is the degree of from.

fn locate_with_hint( &self, point: Point2<<Self::Vertex as HasPosition>::Scalar>, hint: FixedVertexHandle ) -> PositionInTriangulation

Returns information about the location of a point in a triangulation.

Additionally, a hint can be given to speed up computation. The hint should be a vertex close to the position that is being looked up.

See also locate, locate_vertex

fn insert_with_hint( &mut self, t: Self::Vertex, hint: FixedVertexHandle ) -> Result<FixedVertexHandle, InsertionError>

Inserts a new vertex into the triangulation.

A hint can be given to speed up the process. The hint should be a handle of a vertex close to the new vertex. in this case the insertion time can be reduced to O(1) on average if the hint is close. If the hint is randomized, running time will be O(sqrt(n)) on average with an O(n) worst case.

See also insert

fn locate_and_remove( &mut self, point: Point2<<Self::Vertex as HasPosition>::Scalar> ) -> Option<Self::Vertex>

Attempts to remove a vertex from the triangulation.

Returns the removed vertex data if it could be found.

Handle invalidation

This method will invalidate all vertex, edge and face handles upon successful removal.

See also remove

fn remove(&mut self, vertex: FixedVertexHandle) -> Self::Vertex

Removes a vertex from the triangulation.

This operation runs in O(d²), where d is the degree of the removed vertex (the number of its outgoing edges).

Handle invalidation

This method will invalidate all vertex, edge and face handles.

fn insert( &mut self, vertex: Self::Vertex ) -> Result<FixedVertexHandle, InsertionError>

Inserts a new vertex into the triangulation.

This operation runs in O(log(n)) on average when using a tree lookup to back up the triangulation, or in O(sqrt(n)) when using a walk lookup. n denotes the number of vertices, the given running times assume that input data is given uniformly randomly distributed. If the point has already been contained in the triangulation, the old vertex is overwritten.

Returns either a handle to the new vertex or an error if the vertex could not be inserted. The triangulation will remain unchanged if an error ocurred.

Use vertex to retrieve more information about the inserted vertex.

Example

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

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

let vertices = vec![Point2::new(0.0, 1.0), Point2::new(4.0, 2.0), Point2::new(3.0, 4.0)];
for vertex in vertices {
  // While not required in this example, it might be a good idea in general to prevent underflow errors like this:
  let corrected_position = spade::mitigate_underflow(vertex);
  triangulation.insert(corrected_position)?;
}

// Done!
assert_eq!(triangulation.num_inner_faces(), 1);
assert_eq!(triangulation.num_vertices(), 3);

See also insert_with_hint, validate_vertex, mitigate_underflow, bulk_load

fn fixed_undirected_edges(&self) -> FixedUndirectedEdgeIterator

An iterator visiting all undirected edges.

The iterator type is FixedUndirectedEdgeHandle.

fn fixed_directed_edges(&self) -> FixedDirectedEdgeIterator

An iterator visiting all directed edges.

The iterator type is FixedDirectedEdgeHandle.

fn fixed_all_faces(&self) -> FixedFaceIterator

An iterator visiting all faces.

The first returned element is the outer face. All other faces are inner faces.

The iterator type is FixedFaceHandle<PossiblyOuterTag, …>.

fn fixed_inner_faces(&self) -> FixedInnerFaceIterator

An iterator visiting all inner faces of the triangulation.

The iterator type is FixedFaceHandle<InnerTag, …>.

fn all_vertices_on_line(&self) -> bool

Returns true if all vertices lie on a single line.

This is always the case for triangulations with 0, 1 or two vertices.

fn convex_hull( &self ) -> HullIterator<'_, Self::Vertex, Self::DirectedEdge, Self::UndirectedEdge, Self::Face>

Returns an iterator over all convex hull edges.

The edges are returned in clockwise order as seen from any point in the triangulation.

A triangulation with its convex hull being highlighted. e0 .. e5 denote the returned edges in clockwise order.

See also convex_hull_size

fn face_data_mut<InnerOuter: InnerOuterMarker>( &mut self, handle: FixedFaceHandle<InnerOuter> ) -> &mut Self::Face

Returns a mutable reference to the associated data of a face.

fn directed_edge_data_mut( &mut self, handle: FixedDirectedEdgeHandle ) -> &mut Self::DirectedEdge

Returns a mutable reference to the associated data of a directed edge.

Object Safety

This trait is not object safe.

Implementors

impl<V, DE, UE, F, L> Triangulation for ConstrainedDelaunayTriangulation<V, DE, UE, F, L>

where V: HasPosition, DE: Default, UE: Default, F: Default, L: HintGenerator<<V as HasPosition>::Scalar>,

type Vertex = V

type DirectedEdge = DE

type UndirectedEdge = CdtEdge<UE>

type Face = F

type HintGenerator = L

impl<V, DE, UE, F, L> Triangulation for DelaunayTriangulation<V, DE, UE, F, L>

where V: HasPosition, DE: Default, UE: Default, F: Default, L: HintGenerator<<V as HasPosition>::Scalar>,

type Vertex = V

type DirectedEdge = DE

type UndirectedEdge = UE

type Face = F

type HintGenerator = L