Struct spade::delaunay::ConstrainedDelaunayTriangulation

pub struct ConstrainedDelaunayTriangulation<V, K, L = DelaunayTreeLocate<<V as HasPosition>::Point>>where
    V: HasPosition2D,
    V::Point: TwoDimensional,
    K: DelaunayKernel<<V::Point as PointN>::Scalar>,
    L: DelaunayLocateStructure<V::Point>,{ /* private fields */ }

A two dimensional constrained Delaunay triangulation.

A constrained Delaunay triangulation is a triangulation that can contain constraint edges. These edges will be present in the resulting triangulation, the resulting triangulation does not necessarily fulfill the Delaunay property.

This implementation currently supports only weakly intersecting constraints, thus, constraint edges are allowed to touch at their start or end point but are not allowed to intersect at any interior point.

The constrained triangulation shares most of the implementation of the usual Delaunay triangulation, refer to DelaunayTriangulation for more information about type parameters, iteration, performance and more examples.

Example

use spade::delaunay::FloatCDT;
let mut cdt = FloatCDT::with_walk_locate();
let v0 = cdt.insert([0.0, 0.0f32]);
let v1 = cdt.insert([1.0, 0.0]);
cdt.add_constraint(v0, v1);
// Alternatively, consider using this shorthand
cdt.add_constraint_edge([1.0, 1.0], [1.0, 0.0]);
// This should print "2"
println!("Number of constraints: {}", cdt.num_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 = [1.0, -2.0];
let to = [1.0, 0.0];
if !cdt.intersects_constraint(&from, &to) {
  // No intersections, the edge can be added
  cdt.add_constraint_edge(from, to);
}

Implementations

impl<V, K> ConstrainedDelaunayTriangulation<V, K>where
    V: HasPosition2D,
    K: DelaunayKernel<<V::Point as PointN>::Scalar>,
    V::Point: TwoDimensional,

pub fn with_tree_locate() -> ConstrainedDelaunayTriangulation<V, K>

Shorthand constructor for a triangulation that is backed up by an r-tree for log(n) insertion and locate time on average.

pub fn with_walk_locate(
) -> ConstrainedDelaunayTriangulation<V, K, DelaunayWalkLocate>

Shorthand constructor for a triangulation that uses the DelaunayWalkLocate strategy for insertion and point location queries. This yields O(sqrt(n)) insertion time on average for randomly generated vertices.

impl<V, K, L> ConstrainedDelaunayTriangulation<V, K, L>where
    V: HasPosition2D,
    V::Point: TwoDimensional,
    K: DelaunayKernel<<V::Point as PointN>::Scalar>,
    L: DelaunayLocateStructure<V::Point>,

pub fn new() -> ConstrainedDelaunayTriangulation<V, K, L>

Creates a new constrained Delaunay triangulation.

pub fn vertex(&self, handle: FixedVertexHandle) -> VertexHandle<'_, V, CdtEdge>

Creates a dynamic vertex handle from a fixed vertex handle.

May panic if the handle was invalidated by a previous vertex removal.

pub fn vertex_mut(&mut self, handle: FixedVertexHandle) -> &mut V

Returns a mutable reference to the vertex data referenced by a FixedVertexHandle.

pub fn face(&self, handle: FixedFaceHandle) -> FaceHandle<'_, V, CdtEdge>

Creates a dynamic face handle from a fixed face handle.

May panic if the faces was invalidated by a previous vertex removal.

pub fn edge(&self, handle: FixedEdgeHandle) -> EdgeHandle<'_, V, CdtEdge>

Creates a dynamic edge handle from a fixed edge handle.

May panic if the handle was invalidated by a previous vertex removal.

pub fn num_vertices(&self) -> usize

Returns the number of vertices in this triangulation.

pub fn num_faces(&self) -> usize

Returns the number of faces in this triangulation.

This count does include the infinite face.

pub fn num_triangles(&self) -> usize

Returns the number of triangles in this triangulation.

As there is always exactly one face not being a triangle, this is equivalent to self.num_faces() - 1.

pub fn num_edges(&self) -> usize

Returns the number of edges in this triangulation.

pub fn triangles(&self) -> FacesIterator<'_, V, CdtEdge>

Returns an iterator over all triangles.

pub fn edges(&self) -> EdgesIterator<'_, V, CdtEdge>

Returns an iterator over all edges.

pub fn vertices(&self) -> VerticesIterator<'_, V, CdtEdge>

Returns an iterator over all vertices.

pub fn infinite_face(&self) -> FaceHandle<'_, V, CdtEdge>

Returns a handle to the infinite face.

pub fn is_degenerate(&self) -> bool

Returns true if the triangulation is degenerate

A triangulation is degenerate if all vertices of the triangulation lie on one line.

pub fn locate(
    &self,
    point: &V::Point
) -> PositionInTriangulation<VertexHandle<'_, V, CdtEdge>, FaceHandle<'_, V, CdtEdge>, EdgeHandle<'_, V, CdtEdge>>

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

pub fn locate_vertex(
    &self,
    point: &V::Point
) -> Option<VertexHandle<'_, V, CdtEdge>>

Locates a vertex at a given position.

Returns None if the point could not be found.

pub fn get_edge_from_neighbors(
    &self,
    from: FixedVertexHandle,
    to: FixedVertexHandle
) -> Option<EdgeHandle<'_, V, CdtEdge>>

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.

pub fn locate_with_hint(
    &self,
    point: &V::Point,
    hint: FixedVertexHandle
) -> PositionInTriangulation<VertexHandle<'_, V, CdtEdge>, FaceHandle<'_, V, CdtEdge>, EdgeHandle<'_, V, CdtEdge>>

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.

pub fn insert_with_hint(
    &mut self,
    t: V,
    hint: FixedVertexHandle
) -> FixedVertexHandle

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. This method is recommended in combination with DelaunayWalkLocate, 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.

pub fn locate_and_remove(&mut self, point: &V::Point) -> Option<V>

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.

pub fn remove(&mut self, vertex: FixedVertexHandle) -> V

Removes a vertex from the triangulation.

This operation runs in O(n²), where n is the degree of the removed vertex.

Handle invalidation

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

pub fn insert(&mut self, vertex: V) -> FixedVertexHandle

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 a handle to the new vertex. Use this handle with ConstrainedDelaunayTriangulation::vertex(..) to refer to it.

pub fn num_constraints(&self) -> usize

Returns the number of constraint edges.

pub fn is_constraint_edge(&self, edge: FixedEdgeHandle) -> bool

Returns true if a given edge is a constraint edge.

pub fn exists_constraint(
    &self,
    from: FixedVertexHandle,
    to: FixedVertexHandle
) -> bool

Checks if two vertices are connected by a constraint edge.

pub fn can_add_constraint(
    &self,
    from: FixedVertexHandle,
    to: FixedVertexHandle
) -> bool

Checks if a constraint edge can be added.

Returns false if the line from from to to intersects another constraint edge.

pub fn intersects_constraint(&self, from: &V::Point, to: &V::Point) -> bool

Checks if a line intersects a constraint edge.

Returns true if the edge from from to to intersects a constraint edge.

pub fn add_constraint_edge(&mut self, from: V, to: V) -> bool

Insert two points and creates a constraint between them.

Returns true if at least one constraint edge was added.

Panics

Panics if the new constraint edge intersects with an existing constraint edge.

pub fn add_constraint(
    &mut self,
    from: FixedVertexHandle,
    to: FixedVertexHandle
) -> bool

Adds a constraint edge between to vertices.

Returns true if at least one constraint edge was added. Note that the given constraint might be splitted into smaller edges if a vertex in the triangulation lies exactly on the constraint edge. Thus, cdt.exists_constraint(from, to) is not necessarily true after a call to this function.

Panics

Panics if the new constraint edge intersects an existing constraint edge.

impl<V, K> ConstrainedDelaunayTriangulation<V, K, DelaunayTreeLocate<V::Point>>where
    V: HasPosition2D,
    V::Point: TwoDimensional,
    K: DelaunayKernel<<V::Point as PointN>::Scalar>,

pub fn nearest_neighbor(
    &self,
    position: &V::Point
) -> Option<VertexHandle<'_, V, CdtEdge>>

Locates the nearest neighbor for a given point.

Trait Implementations

impl<V: Clone, K: Clone, L: Clone> Clone for ConstrainedDelaunayTriangulation<V, K, L>where
    V: HasPosition2D,
    V::Point: TwoDimensional,
    K: DelaunayKernel<<V::Point as PointN>::Scalar>,
    L: DelaunayLocateStructure<V::Point>,

fn clone(&self) -> ConstrainedDelaunayTriangulation<V, K, L>

Returns a copy of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<V, K, L> Default for ConstrainedDelaunayTriangulation<V, K, L>where
    V: HasPosition2D,
    V::Point: TwoDimensional,
    K: DelaunayKernel<<V::Point as PointN>::Scalar>,
    L: DelaunayLocateStructure<V::Point>,

fn default() -> Self

Returns the “default value” for a type.