Struct spade::ConstrainedDelaunayTriangulation

pub struct ConstrainedDelaunayTriangulation<V, DE = (), UE = (), F = (), L = LastUsedVertexHintGenerator>
where
    V: HasPosition,
    DE: Default,
    UE: Default,
    F: Default,
    L: HintGenerator<<V as HasPosition>::Scalar>,
{ /* private fields */ }

A two dimensional constrained Delaunay triangulation.

A constrained Delaunay triangulation (CDT) is a triangulation that can contain constraint edges. These edges will always be present in the resulting triangulation.

Left: A CDT with 4 constraint edges. Right: The same triangulation without constraint edges

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::{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)?;
}

See also

Refer to Triangulation for most implemented methods on this type. Refer to DelaunayTriangulation for general information about using Delaunay triangulations.

Implementations

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

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

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 num_constraints(&self) -> usize

Returns the number of constraint edges.

pub fn is_constraint_edge(&self, edge: FixedUndirectedEdgeHandle) -> 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, line_from: Point2<V::Scalar>, line_to: Point2<V::Scalar> ) -> 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_edges( &mut self, vertices: impl IntoIterator<Item = V>, closed: bool ) -> Result<(), InsertionError>

Creates a several constraint edges by taking and connecting vertices from an iterator.

Every two sequential vertices in the input iterator will be connected by a constraint edge. If closed is set to true, the first and last vertex will also be connected.

Special cases:

• Does nothing if input iterator is empty
• Only inserts the single vertex if the input iterator contains exactly one element

Example

use spade::{ConstrainedDelaunayTriangulation, Point2};

const NUM_VERTICES: usize = 51;

let mut cdt = ConstrainedDelaunayTriangulation::<_>::default();

// Iterates through vertices on a circle
let vertices = (0..NUM_VERTICES).map(|i| {
    let angle = std::f64::consts::PI * 2.0 * i as f64 / NUM_VERTICES as f64;
    let (sin, cos) = angle.sin_cos();
    Point2::new(sin, cos)
});

cdt.add_constraint_edges(vertices, true)?;

Panics

Panics if any of the generated constraints intersects with any other constraint edge.

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

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. Use can_add_constraint to check.

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.

Returns false and does nothing if from == to.

Panics

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

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

where V: HasPosition + From<Point2<<V as HasPosition>::Scalar>>, DE: Default, UE: Default, F: Default, L: HintGenerator<<V as HasPosition>::Scalar>, <V as HasPosition>::Scalar: Float,

pub fn refine( &mut self, parameters: RefinementParameters<V::Scalar> ) -> RefinementResult

Refines a triangulation by inserting additional points to improve the quality of its mesh.

Mesh quality, when applied to constrained delaunay triangulations (CDT), usually refers to how skewed its triangles are. A skewed triangle is a triangle with very large or very small (acute) inner angles. Some applications (e.g. interpolation and finite element methods) perform poorly in the presence of skewed triangles.

Refining by inserting additional points (called “steiner points”) may increase the minimum angle. The given RefinementParameters should be used to modify the refinement behavior.

General usage

The vertex type must implement From<Point2<...>> - otherwise, Spade cannot construct new steiner points at a certain location. The refinement itself happens in place and will result in a valid CDT.

use spade::{ConstrainedDelaunayTriangulation, RefinementParameters, Point2, InsertionError, Triangulation};

fn get_refined_triangulation(vertices: Vec<Point2<f64>>) ->
    Result<ConstrainedDelaunayTriangulation<Point2<f64>>,  InsertionError>
{
    let mut cdt = ConstrainedDelaunayTriangulation::bulk_load(vertices)?;
    let result = cdt.refine(RefinementParameters::default());
    if !result.refinement_complete {
        panic!("Refinement failed - I should consider using different parameters.")
    }

    return Ok(cdt)
}

Example image

Unrefined	Refined

A refinement example. The CDT on the left has some acute angles and skewed triangles. The refined CDT on the right contains several additional points that prevents such triangles from appearing while keeping all input vertices and constraint edges.

Quality guarantees

Refinement will ensure that the resulting triangulation fulfills a few properties:

• The triangulation’s minimum angle will be larger than the angle specified by with_angle_limit.
  Exception: Acute input angles (small angles between initial constraint edges) cannot be maximized as the constraint edges must be kept intact. The algorithm will, for the most part, leave those places unchanged.
  Exception: The refinement will often not be able to increase the minimal angle much above 30 degrees as every newly inserted steiner point may create additional skewed triangles.
• The refinement will fullfil the Delaunay Property: Every triangle’s circumcenter will not contain any other vertex.
  Exception: Refining with keep_constraint_edges cannot restore the Delaunay property if doing so would require splitting a constraint edge.
  Exception: Refining with exclude_outer_faces will not restore the Delaunay property of any outer face.
• Spade allows to specify a maximum allowed triangle area. The algorithm will attempt to subdivide any triangle with an area larger than this, independent of its smallest angle.
• Spade allows to specify a minimum required triangle area. The refinement will attempt to ignore any triangle with an area smaller than this parameter. This can prevent the refinement algorithm from over-refining in some cases.

General limitations

The algorithm may fail to terminate in some cases for a minimum angle limit larger than 30 degrees. Such a limit can result in an endless loop: Every additionally inserted point creates more triangles that need to be refined.

To prevent this, spade limits the number of additionally inserted steiner points (see RefinementParameters::with_max_additional_vertices). However, this may leave the refinement in an incomplete state - some areas of the input mesh may not have been triangulated at all, some will be overly refined. Use RefinementResult::refinement_complete to identify if a refinement operation has succeeded without running out of vertices.

For mitigation, consider either lowering the minimum angle limit (see RefinementParameters::with_angle_limit) or introduce a minimum required area.

Meshes with very small input angles (angles between two constraint edges) may lead to poorly refined results. Please consider providing a bug report if you encounter an input mesh which you think isn’t refined well.

Stability guarantees

While changing the interface of this method is considered to be a breaking change, changes to the specific refinement process (e.g. which faces are split in which order) are not. Any patch release may change how the same input mesh is being refined.

References

This is an adaption of the classical refinement algorithms introduced by Jim Ruppert and Paul Chew.

For a good introduction to the topic, refer to the slides from a short course at the thirteenth and fourteenth International Meshing Roundtables (2005) by Jonathan Richard Shewchuk: https://people.eecs.berkeley.edu/~jrs/papers/imrtalk.pdf

Wikipedia: https://en.wikipedia.org/wiki/Delaunay_refinement

Trait Implementations

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

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

fn clone(&self) -> ConstrainedDelaunayTriangulation<V, DE, UE, F, L>

Returns a copy of the value.

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

Performs copy-assignment from source.

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

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

fn default() -> Self

Returns the “default value” for a type.

impl<V, DE, UE, F, L> From<DelaunayTriangulation<V, DE, UE, F, L>> for ConstrainedDelaunayTriangulation<V, DE, UE, F, L>

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

fn from(value: DelaunayTriangulation<V, DE, UE, F, L>) -> Self

Converts to this type from the input type.

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

The triangulation’s vertex type.

type DirectedEdge = DE

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

type UndirectedEdge = CdtEdge<UE>

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

type Face = F

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

type HintGenerator = L

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

fn clear(&mut self)

Removes all edges, faces and vertices from the triangulation.

fn new() -> Self

Creates a new triangulation.

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 bulk_load(elements: Vec<Self::Vertex>) -> Result<Self, InsertionError>

Creates a new triangulation populated with some vertices.

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

Converts a fixed vertex handle to a reference vertex handle.

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.

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.

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.

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.

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.

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

An iterator visiting all directed edges.

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

An iterator over all undirected edges.

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.

fn fixed_vertices(&self) -> FixedVertexIterator

An iterator visiting all vertices.

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

An iterator visiting all 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.

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

An iterator visiting all directed voronoi edges.

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

An iterator visiting all undirected voronoi edges.

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.

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.

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.

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

Inserts a new vertex into the triangulation.

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

Attempts to remove a vertex from the triangulation.

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

Removes a vertex from the triangulation.

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

Inserts a new vertex into the triangulation.

fn fixed_undirected_edges(&self) -> FixedUndirectedEdgeIterator

An iterator visiting all undirected edges.

fn fixed_directed_edges(&self) -> FixedDirectedEdgeIterator

An iterator visiting all directed edges.

fn fixed_all_faces(&self) -> FixedFaceIterator

An iterator visiting all faces.

fn fixed_inner_faces(&self) -> FixedInnerFaceIterator

An iterator visiting all inner faces of the triangulation.

fn all_vertices_on_line(&self) -> bool

Returns true if all vertices lie on a single line.

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

Returns an iterator over all convex hull edges.

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.