Struct spade::delaunay::ConstrainedDelaunayTriangulation
source · 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 */ }
Expand description
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
sourceimpl<V, K> ConstrainedDelaunayTriangulation<V, K>where
V: HasPosition2D,
K: DelaunayKernel<<V::Point as PointN>::Scalar>,
V::Point: TwoDimensional,
impl<V, K> ConstrainedDelaunayTriangulation<V, K>where
V: HasPosition2D,
K: DelaunayKernel<<V::Point as PointN>::Scalar>,
V::Point: TwoDimensional,
sourcepub fn with_tree_locate() -> ConstrainedDelaunayTriangulation<V, K>
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.
sourcepub fn with_walk_locate(
) -> ConstrainedDelaunayTriangulation<V, K, DelaunayWalkLocate>
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.
sourceimpl<V, K, L> ConstrainedDelaunayTriangulation<V, K, L>where
V: HasPosition2D,
V::Point: TwoDimensional,
K: DelaunayKernel<<V::Point as PointN>::Scalar>,
L: DelaunayLocateStructure<V::Point>,
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>,
sourcepub fn new() -> ConstrainedDelaunayTriangulation<V, K, L>
pub fn new() -> ConstrainedDelaunayTriangulation<V, K, L>
Creates a new constrained Delaunay triangulation.
sourcepub fn vertex(&self, handle: FixedVertexHandle) -> VertexHandle<'_, V, CdtEdge>
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.
sourcepub fn vertex_mut(&mut self, handle: FixedVertexHandle) -> &mut V
pub fn vertex_mut(&mut self, handle: FixedVertexHandle) -> &mut V
Returns a mutable reference to the vertex data referenced by a
FixedVertexHandle
.
sourcepub fn face(&self, handle: FixedFaceHandle) -> FaceHandle<'_, V, CdtEdge>
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.
sourcepub fn edge(&self, handle: FixedEdgeHandle) -> EdgeHandle<'_, V, CdtEdge>
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.
sourcepub fn num_vertices(&self) -> usize
pub fn num_vertices(&self) -> usize
Returns the number of vertices in this triangulation.
sourcepub fn num_faces(&self) -> usize
pub fn num_faces(&self) -> usize
Returns the number of faces in this triangulation.
This count does include the infinite face.
sourcepub fn num_triangles(&self) -> usize
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
.
sourcepub fn triangles(&self) -> FacesIterator<'_, V, CdtEdge>
pub fn triangles(&self) -> FacesIterator<'_, V, CdtEdge>
Returns an iterator over all triangles.
sourcepub fn vertices(&self) -> VerticesIterator<'_, V, CdtEdge>
pub fn vertices(&self) -> VerticesIterator<'_, V, CdtEdge>
Returns an iterator over all vertices.
sourcepub fn infinite_face(&self) -> FaceHandle<'_, V, CdtEdge>
pub fn infinite_face(&self) -> FaceHandle<'_, V, CdtEdge>
Returns a handle to the infinite face.
sourcepub fn is_degenerate(&self) -> bool
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.
sourcepub fn locate(
&self,
point: &V::Point
) -> PositionInTriangulation<VertexHandle<'_, V, CdtEdge>, FaceHandle<'_, V, CdtEdge>, EdgeHandle<'_, V, CdtEdge>>
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.
sourcepub fn locate_vertex(
&self,
point: &V::Point
) -> Option<VertexHandle<'_, V, CdtEdge>>
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.
sourcepub fn get_edge_from_neighbors(
&self,
from: FixedVertexHandle,
to: FixedVertexHandle
) -> Option<EdgeHandle<'_, V, CdtEdge>>
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
.
sourcepub fn locate_with_hint(
&self,
point: &V::Point,
hint: FixedVertexHandle
) -> PositionInTriangulation<VertexHandle<'_, V, CdtEdge>, FaceHandle<'_, V, CdtEdge>, EdgeHandle<'_, V, CdtEdge>>
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.
sourcepub fn insert_with_hint(
&mut self,
t: V,
hint: FixedVertexHandle
) -> FixedVertexHandle
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.
sourcepub fn locate_and_remove(&mut self, point: &V::Point) -> Option<V>
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.
sourcepub fn remove(&mut self, vertex: FixedVertexHandle) -> V
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.
sourcepub fn insert(&mut self, vertex: V) -> FixedVertexHandle
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.
sourcepub fn num_constraints(&self) -> usize
pub fn num_constraints(&self) -> usize
Returns the number of constraint edges.
sourcepub fn is_constraint_edge(&self, edge: FixedEdgeHandle) -> bool
pub fn is_constraint_edge(&self, edge: FixedEdgeHandle) -> bool
Returns true
if a given edge is a constraint edge.
sourcepub fn exists_constraint(
&self,
from: FixedVertexHandle,
to: FixedVertexHandle
) -> bool
pub fn exists_constraint(
&self,
from: FixedVertexHandle,
to: FixedVertexHandle
) -> bool
Checks if two vertices are connected by a constraint edge.
sourcepub fn can_add_constraint(
&self,
from: FixedVertexHandle,
to: FixedVertexHandle
) -> bool
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.
sourcepub fn intersects_constraint(&self, from: &V::Point, to: &V::Point) -> bool
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.
sourcepub fn add_constraint_edge(&mut self, from: V, to: V) -> bool
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.
sourcepub fn add_constraint(
&mut self,
from: FixedVertexHandle,
to: FixedVertexHandle
) -> bool
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.
sourceimpl<V, K> ConstrainedDelaunayTriangulation<V, K, DelaunayTreeLocate<V::Point>>where
V: HasPosition2D,
V::Point: TwoDimensional,
K: DelaunayKernel<<V::Point as PointN>::Scalar>,
impl<V, K> ConstrainedDelaunayTriangulation<V, K, DelaunayTreeLocate<V::Point>>where
V: HasPosition2D,
V::Point: TwoDimensional,
K: DelaunayKernel<<V::Point as PointN>::Scalar>,
sourcepub fn nearest_neighbor(
&self,
position: &V::Point
) -> Option<VertexHandle<'_, V, CdtEdge>>
pub fn nearest_neighbor(
&self,
position: &V::Point
) -> Option<VertexHandle<'_, V, CdtEdge>>
Locates the nearest neighbor for a given point.
Trait Implementations
sourceimpl<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>,
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>,
sourcefn clone(&self) -> ConstrainedDelaunayTriangulation<V, K, L>
fn clone(&self) -> ConstrainedDelaunayTriangulation<V, K, L>
1.0.0 · sourcefn clone_from(&mut self, source: &Self)
fn clone_from(&mut self, source: &Self)
source
. Read moresourceimpl<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>,
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>,
Auto Trait Implementations
impl<V, K, L> RefUnwindSafe for ConstrainedDelaunayTriangulation<V, K, L>where
K: RefUnwindSafe,
L: RefUnwindSafe,
V: RefUnwindSafe,
impl<V, K, L = RTree<VertexEntry<<V as HasPosition>::Point>>> !Send for ConstrainedDelaunayTriangulation<V, K, L>
impl<V, K, L = RTree<VertexEntry<<V as HasPosition>::Point>>> !Sync for ConstrainedDelaunayTriangulation<V, K, L>
impl<V, K, L> Unpin for ConstrainedDelaunayTriangulation<V, K, L>where
L: Unpin,
V: Unpin,
impl<V, K, L> UnwindSafe for ConstrainedDelaunayTriangulation<V, K, L>where
K: RefUnwindSafe,
L: UnwindSafe,
V: UnwindSafe,
Blanket Implementations
sourceimpl<T> BorrowMut<T> for Twhere
T: ?Sized,
impl<T> BorrowMut<T> for Twhere
T: ?Sized,
const: unstable · sourcefn borrow_mut(&mut self) -> &mut T
fn borrow_mut(&mut self) -> &mut T
impl<SS, SP> SupersetOf<SS> for SPwhere
SS: SubsetOf<SP>,
impl<SS, SP> SupersetOf<SS> for SPwhere
SS: SubsetOf<SP>,
fn to_subset(&self) -> Option<SS>
fn to_subset(&self) -> Option<SS>
self
from the equivalent element of its
superset. Read morefn is_in_subset(&self) -> bool
fn is_in_subset(&self) -> bool
self
is actually part of its subset T
(and can be converted to it).unsafe fn to_subset_unchecked(&self) -> SS
unsafe fn to_subset_unchecked(&self) -> SS
self.to_subset
but without any property checks. Always succeeds.fn from_subset(element: &SS) -> SP
fn from_subset(element: &SS) -> SP
self
to the equivalent element of its superset.