spade/delaunay_core/handles/
handle_impls.rs

1use super::super::dcel::EdgeEntry;
2use super::super::math;
3use super::handle_defs::*;
4use super::iterators::CircularIterator;
5use super::iterators::NextBackFn;
6use super::public_handles::*;
7use crate::CdtEdge;
8use crate::{HasPosition, LineSideInfo, Point2};
9use core::cmp::Ordering;
10use core::fmt::Debug;
11use core::hash::{Hash, Hasher};
12use num_traits::{Float, One};
13
14// Debug implementations
15impl<V, DE, UE, F> Debug for VertexHandle<'_, V, DE, UE, F> {
16    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
17        write!(f, "VertexHandle({:?})", self.handle.index())
18    }
19}
20
21impl<V, DE, UE, F> Debug for DirectedEdgeHandle<'_, V, DE, UE, F> {
22    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
23        write!(
24            f,
25            "DirectedEdgeHandle - id: {:?} ({:?} -> {:?})",
26            self.handle.index(),
27            self.from().fix(),
28            self.to().fix()
29        )
30    }
31}
32
33impl<V, DE, UE, F> Debug for UndirectedEdgeHandle<'_, V, DE, UE, F> {
34    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
35        let [v0, v1] = self.vertices();
36        write!(
37            f,
38            "UndirectedEdgeHandle - id: {:?} ({:?} <-> {:?})",
39            self.handle.index(),
40            v0.fix(),
41            v1.fix(),
42        )
43    }
44}
45
46impl<V, DE, UE, F> Debug for FaceHandle<'_, PossiblyOuterTag, V, DE, UE, F> {
47    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
48        if let Some(inner) = self.as_inner() {
49            inner.fmt(f)
50        } else {
51            write!(f, "OuterFace")
52        }
53    }
54}
55
56impl<V, DE, UE, F> Debug for FaceHandle<'_, InnerTag, V, DE, UE, F> {
57    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
58        let [v0, v1, v2] = self.vertices();
59        write!(
60            f,
61            "FaceHandle - id: {:?} ({:?}, {:?}, {:?})",
62            self.handle.index(),
63            v0.fix().index(),
64            v1.fix().index(),
65            v2.fix().index(),
66        )
67    }
68}
69
70impl FixedDirectedEdgeHandle {
71    #[inline]
72    pub(in super::super) fn new_normalized(index: usize) -> Self {
73        Self::new(index << 1)
74    }
75
76    /// Returns if this edge is the normalized edge of a directed edge pair.
77    ///
78    /// For every directed edge pair, one edge is marked as the normalized edge. This information
79    /// is used to hook up a directed edge handle with its correct half edge storage.
80    #[inline]
81    pub(in super::super) fn is_normalized(self) -> bool {
82        // Use the last bit to store if this edge is normalized
83        self.index() & 0x1 == 0x0
84    }
85
86    #[inline]
87    pub(in super::super) fn normalize_index(self) -> usize {
88        self.index() & 0x1
89    }
90
91    /// Returns this edge with its direction reversed.
92    ///
93    /// If this edge points from `v0` to `v1`, the returned edge would point from `v1` to `v0`.
94    /// Calling `rev` twice will always return the original vertex.
95    #[inline]
96    pub fn rev(self) -> Self {
97        // Flip the last bit
98        Self::new(self.index() ^ 0x1)
99    }
100
101    /// Converts this directed edge handle into an undirected edge handle.
102    ///
103    /// *See also the [handles](crate::handles) module for more information.*
104    #[inline]
105    pub fn as_undirected(self) -> FixedUndirectedEdgeHandle {
106        FixedHandleImpl::new(self.index() >> 1)
107    }
108}
109
110impl<V, DE, UE, F, Type: Copy, InnerOuter: InnerOuterMarker> Clone
111    for DynamicHandleImpl<'_, V, DE, UE, F, Type, InnerOuter>
112{
113    fn clone(&self) -> Self {
114        *self
115    }
116}
117
118impl<V, DE, UE, F, Type: Copy, InnerOuter: InnerOuterMarker> Copy
119    for DynamicHandleImpl<'_, V, DE, UE, F, Type, InnerOuter>
120{
121}
122
123impl<V, DE, UE, F, Type: PartialEq, InnerOuter: InnerOuterMarker> PartialEq
124    for DynamicHandleImpl<'_, V, DE, UE, F, Type, InnerOuter>
125{
126    fn eq(&self, other: &Self) -> bool {
127        self.handle == other.handle
128    }
129}
130
131impl<V, DE, UE, F, Type: Eq, InnerOuter: InnerOuterMarker> Eq
132    for DynamicHandleImpl<'_, V, DE, UE, F, Type, InnerOuter>
133{
134}
135
136impl<V, DE, UE, F, Type: Hash, InnerOuter: InnerOuterMarker> Hash
137    for DynamicHandleImpl<'_, V, DE, UE, F, Type, InnerOuter>
138{
139    fn hash<HA: Hasher>(&self, state: &mut HA) {
140        self.handle.hash(state);
141    }
142}
143
144impl<V, DE, UE, F, Type: Ord, InnerOuter: InnerOuterMarker> Ord
145    for DynamicHandleImpl<'_, V, DE, UE, F, Type, InnerOuter>
146{
147    fn cmp(&self, other: &Self) -> Ordering {
148        self.handle.cmp(&other.handle)
149    }
150}
151
152impl<V, DE, UE, F, Type: PartialOrd, InnerOuter: InnerOuterMarker> PartialOrd
153    for DynamicHandleImpl<'_, V, DE, UE, F, Type, InnerOuter>
154{
155    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
156        self.handle.partial_cmp(&other.handle)
157    }
158}
159
160impl<V, DE, UE, F, Type: Copy + Default, InnerOuter: InnerOuterMarker>
161    DynamicHandleImpl<'_, V, DE, UE, F, Type, InnerOuter>
162{
163    /// Converts this dynamic handle to its fixed variant.
164    ///
165    /// *See also the [handles module](crate::handles)*
166    pub fn fix(&self) -> FixedHandleImpl<Type, InnerOuter> {
167        self.handle
168    }
169
170    /// Returns the internal index of this element.
171    ///
172    /// Indices of the same handle type are guaranteed to be unique (e.g. different vertices will
173    /// have different indices from each other).
174    ///
175    /// Indices will always be in the interval `0` .. `number_of_elements` (e.g. the number of
176    /// directed edges).
177    ///
178    /// Adding vertices will not change any indices. Vertex removal does affect indices -
179    /// the index of elements may change to swap-fill any gaps that were created.
180    pub fn index(&self) -> usize {
181        self.handle.index()
182    }
183}
184
185impl FixedFaceHandle<PossiblyOuterTag> {
186    /// Returns `true` if this face is the single outer face.
187    #[inline]
188    pub fn is_outer(&self) -> bool {
189        *self == super::super::dcel_operations::OUTER_FACE_HANDLE
190    }
191
192    /// Converts this face handle to an inner face.
193    ///
194    /// Returns `None` if this handle refers to the single outer face.
195    pub fn as_inner(&self) -> Option<FixedFaceHandle<InnerTag>> {
196        if self.is_outer() {
197            None
198        } else {
199            Some(self.adjust_inner_outer())
200        }
201    }
202}
203
204impl<V, DE, UE, F> AsRef<DE> for DirectedEdgeHandle<'_, V, DE, UE, F> {
205    fn as_ref(&self) -> &DE {
206        self.data()
207    }
208}
209
210impl<'a, V, DE, UE, F> DirectedEdgeHandle<'a, V, DE, UE, F> {
211    /// Returns the edge's two vertices.
212    ///
213    /// The first vertex is `self.from()`, the second vertex is `self.to()`.
214    pub fn vertices(&self) -> [VertexHandle<'a, V, DE, UE, F>; 2] {
215        [self.from(), self.to()]
216    }
217
218    /// Returns the edge's origin vertex.
219    pub fn from(&self) -> VertexHandle<'a, V, DE, UE, F> {
220        let entry = self.dcel.half_edge(self.handle);
221        DynamicHandleImpl::new(self.dcel, entry.origin.adjust_inner_outer())
222    }
223
224    /// Returns the edge's destination vertex.
225    pub fn to(&self) -> VertexHandle<'a, V, DE, UE, F> {
226        self.rev().from()
227    }
228
229    /// Returns this edge in reversed direction.
230    #[inline]
231    pub fn rev(&self) -> Self {
232        DirectedEdgeHandle::new(self.dcel, self.handle.rev())
233    }
234
235    /// Returns the vertex which lies opposite of this edge.
236    ///
237    /// This is equal to calling `self.prev().from()` or `self.next().to()`.
238    /// Returns `None` if this edge is part of the convex hull.
239    pub fn opposite_vertex(&self) -> Option<VertexHandle<'a, V, DE, UE, F>> {
240        if self.is_outer_edge() {
241            None
242        } else {
243            Some(self.prev().from())
244        }
245    }
246
247    /// Returns the oriented next edge.
248    ///
249    /// The oriented next edge shares the same face as this edge.
250    /// When traversing the face's edges in oriented order,
251    /// this edge is the predecessor of the oriented next edge.
252    /// "Oriented" means counterclockwise for right-handed
253    /// coordinate systems.
254    pub fn next(&self) -> DirectedEdgeHandle<'a, V, DE, UE, F> {
255        let entry = self.dcel.half_edge(self.handle);
256        DirectedEdgeHandle::new(self.dcel, entry.next)
257    }
258
259    /// Returns the oriented previous edge.
260    ///
261    /// The oriented previous edge shares the same face as this edge.
262    /// When traversing the face's edges in oriented order,
263    /// this edge is the successor of the oriented previous edge.
264    /// "Oriented" means counterclockwise for right-handed
265    /// coordinate systems.
266    pub fn prev(&self) -> DirectedEdgeHandle<'a, V, DE, UE, F> {
267        let entry = self.dcel.half_edge(self.handle);
268        DirectedEdgeHandle::new(self.dcel, entry.prev)
269    }
270
271    /// Returns the face located to the left of this edge.
272    pub fn face(&self) -> FaceHandle<'a, PossiblyOuterTag, V, DE, UE, F> {
273        let entry = self.dcel.half_edge(self.handle);
274        self.dcel.face(entry.face)
275    }
276
277    /// Returns the next edge in clockwise direction.
278    ///
279    /// Note that this assumes that you use a right-handed coordinate system,
280    /// otherwise the sense of orientation is inverted.
281    pub fn cw(&self) -> DirectedEdgeHandle<'a, V, DE, UE, F> {
282        self.rev().next()
283    }
284
285    /// Returns the next edge in counterclockwise direction.
286    ///
287    /// Note that this assumes that you use a right-handed coordinate system,
288    /// otherwise the sense of orientation is inverted.
289    pub fn ccw(&self) -> DirectedEdgeHandle<'a, V, DE, UE, F> {
290        self.prev().rev()
291    }
292
293    /// Returns a reference to the data associated with this directed edge.
294    ///
295    /// Use [Triangulation::directed_edge_data_mut](crate::Triangulation::directed_edge_data_mut)
296    /// to modify the edge data.
297    pub fn data(&self) -> &'a DE {
298        self.entry().get_directed_data(self.handle)
299    }
300
301    fn entry(&self) -> &'a EdgeEntry<DE, UE> {
302        self.dcel.edge_entry(self.handle.as_undirected())
303    }
304
305    /// Converts this directed edge handle into an undirected edge handle.
306    ///
307    /// *See also the [handles](crate::handles) module.*
308    #[inline]
309    pub fn as_undirected(self) -> UndirectedEdgeHandle<'a, V, DE, UE, F> {
310        DynamicHandleImpl::new(self.dcel, self.handle.as_undirected())
311    }
312
313    /// Returns `true` if this edge is adjacent to the outer face.
314    pub fn is_outer_edge(&self) -> bool {
315        self.face().is_outer()
316    }
317
318    /// Returns `true` if either this edge or its reversed edge is adjacent to the outer face.
319    pub fn is_part_of_convex_hull(&self) -> bool {
320        self.is_outer_edge() || self.rev().is_outer_edge()
321    }
322
323    /// Converts this edge into its dual voronoi edge.
324    ///
325    /// See also [as_delaunay_edge](DirectedVoronoiEdge::as_delaunay_edge).
326    pub fn as_voronoi_edge(&self) -> DirectedVoronoiEdge<'a, V, DE, UE, F> {
327        DirectedVoronoiEdge::new(self.dcel, FixedHandleImpl::new(self.handle.index()))
328    }
329}
330
331impl<V, DE, UE, F> DirectedEdgeHandle<'_, V, DE, UE, F>
332where
333    V: HasPosition,
334{
335    /// Returns the start and end position of this edge.
336    ///
337    /// The first returned position is `self.from().position()`, the second is
338    ///  `self.to().position()`.
339    pub fn positions(&self) -> [Point2<<V as HasPosition>::Scalar>; 2] {
340        [self.from().position(), self.to().position()]
341    }
342
343    /// Returns the position of the vertex opposite of this edge.
344    ///
345    /// See also [opposite_vertex()](Self::opposite_vertex()).
346    /// Returns `None` if this edge is an outer edge.
347    #[inline]
348    pub fn opposite_position(&self) -> Option<Point2<V::Scalar>> {
349        self.opposite_vertex().map(|v| v.position())
350    }
351
352    /// Returns the squared length of this edge.
353    pub fn length_2(&self) -> V::Scalar {
354        self.as_undirected().length_2()
355    }
356
357    #[inline]
358    /// Identifies on which side of this edge a point lies.
359    pub fn side_query(&self, query_point: Point2<V::Scalar>) -> LineSideInfo {
360        let (p1, p2) = (self.from().position(), self.to().position());
361        math::side_query(p1, p2, query_point)
362    }
363
364    /// Indicates the position of a point being projected onto this edge.
365    ///
366    /// A point's projection can either come _before_, _on_ or _behind_ this edge.
367    /// Note that this method may return inaccurate results due to rounding issues.
368    ///
369    #[doc = include_str!("../../../images/project_point.svg")]
370    ///
371    /// *An image displaying differently colored areas which would result in different point projections*
372    ///
373    /// # Example
374    /// ```
375    /// # fn main() -> Result<(), spade::InsertionError> {
376    /// use spade::{Point2, Triangulation, DelaunayTriangulation};
377    ///
378    /// let from = Point2::new(0.0, 0.0);
379    /// let to = Point2::new(2.0, 0.0);
380    ///
381    /// let mut triangulation: DelaunayTriangulation<_> = Default::default();
382    /// let v0 = triangulation.insert(from)?;
383    /// let v1 = triangulation.insert(to)?;
384    /// // This edge goes from "from" to "to"
385    /// let edge = triangulation.get_edge_from_neighbors(v0, v1).unwrap();
386    ///
387    /// // These vertices are all projected before the edge
388    /// assert!(edge.project_point(Point2::new(-0.2, 0.0)).is_before_edge());
389    /// assert!(edge.project_point(Point2::new(-1002.0, -12.0)).is_before_edge());
390    ///
391    /// // These vertices are all projected onto the edge
392    /// assert!(edge.project_point(Point2::new(1.0, 5.0)).is_on_edge());
393    /// assert!(edge.project_point(Point2::new(0.5, -2.0)).is_on_edge());
394    /// assert!(edge.project_point(Point2::new(1.0, 0.0)).is_on_edge());
395    ///
396    /// // These vertices are all projected behind the edge
397    /// assert!(edge.project_point(Point2::new(4.000001, 0.0)).is_behind_edge());
398    /// assert!(edge.project_point(Point2::new(5.0, -12.0)).is_behind_edge());
399    /// # Ok (()) }
400    /// ```
401    pub fn project_point(
402        &self,
403        query_point: Point2<V::Scalar>,
404    ) -> math::PointProjection<V::Scalar> {
405        let (p1, p2) = (self.from().position(), self.to().position());
406        math::project_point(p1, p2, query_point)
407    }
408
409    pub(crate) fn intersects_edge_non_collinear(
410        &self,
411        other_from: Point2<V::Scalar>,
412        other_to: Point2<V::Scalar>,
413    ) -> bool {
414        let other_from_query = self.side_query(other_from);
415        let other_to_query = self.side_query(other_to);
416        let self_from_query = math::side_query(other_from, other_to, self.from().position());
417        let self_to_query = math::side_query(other_from, other_to, self.to().position());
418
419        assert!(
420            ![
421                &other_from_query,
422                &other_to_query,
423                &self_from_query,
424                &self_to_query
425            ]
426            .iter()
427            .all(|q| q.is_on_line()),
428            "intersects_edge_non_collinear: Given edge is collinear."
429        );
430
431        other_from_query != other_to_query && self_from_query != self_to_query
432    }
433}
434
435impl<V, DE, UE, F> DirectedEdgeHandle<'_, V, DE, CdtEdge<UE>, F> {
436    /// Returns `true` if this edge is a constraint edge.
437    pub fn is_constraint_edge(self) -> bool {
438        self.as_undirected().is_constraint_edge()
439    }
440}
441
442impl FixedUndirectedEdgeHandle {
443    /// Converts this directed edge into an undirected edge handle.
444    ///
445    /// Any of the two directed edges may be returned.
446    ///
447    /// See also [FixedDirectedEdgeHandle::as_undirected]
448    #[inline]
449    pub fn as_directed(&self) -> FixedDirectedEdgeHandle {
450        FixedDirectedEdgeHandle::new_normalized(self.index())
451    }
452
453    /// Returns the two directed edges of this undirected edge in any order.
454    pub fn directed_edges(&self) -> [FixedDirectedEdgeHandle; 2] {
455        [self.as_directed(), self.as_directed().rev()]
456    }
457
458    #[inline]
459    pub(in super::super) fn normalized(&self) -> FixedDirectedEdgeHandle {
460        self.as_directed()
461    }
462
463    #[inline]
464    pub(in super::super) fn not_normalized(&self) -> FixedDirectedEdgeHandle {
465        self.as_directed().rev()
466    }
467}
468
469impl<'a, V, DE, UE, F> UndirectedVoronoiEdge<'a, V, DE, UE, F> {
470    /// Returns the edge's two vertices.
471    ///
472    /// The vertices are returned in any order.
473    pub fn vertices(&self) -> [VoronoiVertex<'a, V, DE, UE, F>; 2] {
474        [self.as_directed().from(), self.as_directed().to()]
475    }
476
477    /// Converts this undirected handle into a directed edge handle.
478    pub fn as_directed(&self) -> DirectedVoronoiEdge<'a, V, DE, UE, F> {
479        self.as_delaunay_edge().as_directed().as_voronoi_edge()
480    }
481
482    /// Returns the dual edge of the Delaunay triangulation.
483    pub fn as_delaunay_edge(&self) -> UndirectedEdgeHandle<'a, V, DE, UE, F> {
484        UndirectedEdgeHandle::new(
485            self.dcel,
486            FixedUndirectedEdgeHandle::new(self.handle.index()),
487        )
488    }
489}
490
491impl<V, DE, UE, F> AsRef<UE> for UndirectedEdgeHandle<'_, V, DE, UE, F> {
492    fn as_ref(&self) -> &UE {
493        self.data()
494    }
495}
496
497impl<'a, V, DE, UE, F> UndirectedEdgeHandle<'a, V, DE, UE, F> {
498    /// Returns the edge's two vertices.
499    ///
500    /// The vertices are returned in any order.
501    pub fn vertices(&self) -> [VertexHandle<'a, V, DE, UE, F>; 2] {
502        [self.as_directed().from(), self.as_directed().to()]
503    }
504
505    /// Converts this directed edge into an undirected edge handle.
506    #[inline]
507    pub fn as_directed(&self) -> DirectedEdgeHandle<'a, V, DE, UE, F> {
508        DirectedEdgeHandle::new(self.dcel, self.handle.as_directed())
509    }
510
511    /// Returns the dual edge in the Voronoi diagram.
512    pub fn as_voronoi_edge(&self) -> UndirectedVoronoiEdge<'a, V, DE, UE, F> {
513        UndirectedVoronoiEdge::new(self.dcel, FixedHandleImpl::new(self.handle.index()))
514    }
515
516    /// Returns a reference to the data associated with this directed edge.
517    ///
518    /// Use [Triangulation::undirected_edge_data_mut](crate::Triangulation::undirected_edge_data_mut)
519    /// to modify the edge data.
520    pub fn data(&self) -> &UE {
521        self.dcel.undirected_edge_data(self.handle)
522    }
523
524    /// Returns `true` if the outer face is adjacent to any side of this undirected edge.
525    pub fn is_part_of_convex_hull(&self) -> bool {
526        self.as_directed().is_part_of_convex_hull()
527    }
528}
529
530impl<V, DE, UE, F> UndirectedEdgeHandle<'_, V, DE, UE, F>
531where
532    V: HasPosition,
533{
534    /// Returns the end positions of this edge.
535    ///
536    /// The positions are returned in any order.
537    pub fn positions(&self) -> [Point2<V::Scalar>; 2] {
538        let [v0, v1] = self.vertices();
539        [v0.position(), v1.position()]
540    }
541
542    /// Returns the squared length of this edge
543    pub fn length_2(&self) -> V::Scalar {
544        let [p0, p1] = self.positions();
545        p0.sub(p1).length2()
546    }
547}
548
549impl<V, DE, UE, F> UndirectedEdgeHandle<'_, V, DE, UE, F>
550where
551    V: HasPosition,
552    V::Scalar: Float,
553{
554    /// Returns the squared distance of a point to this edge.
555    pub fn distance_2(&self, query_point: Point2<V::Scalar>) -> V::Scalar {
556        let [p1, p2] = self.positions();
557        math::distance_2(p1, p2, query_point)
558    }
559
560    /// Yields the nearest point on this edge.
561    pub fn nearest_point(&self, query_point: Point2<V::Scalar>) -> Point2<V::Scalar> {
562        let [v0, v1] = self.positions();
563        math::nearest_point(v0, v1, query_point)
564    }
565
566    /// Returns the center of this edge.
567    pub fn center(&self) -> Point2<V::Scalar> {
568        let [v0, v1] = self.positions();
569        v0.add(v1).mul(0.5.into())
570    }
571}
572
573impl<V, DE, UE, F> UndirectedEdgeHandle<'_, V, DE, CdtEdge<UE>, F> {
574    /// Returns `true` if this edge is a constraint edge.
575    pub fn is_constraint_edge(self) -> bool {
576        self.data().is_constraint_edge()
577    }
578}
579
580impl<V, DE, UE, InnerOuter, F> AsRef<F> for FaceHandle<'_, InnerOuter, V, DE, UE, F>
581where
582    InnerOuter: InnerOuterMarker,
583{
584    fn as_ref(&self) -> &F {
585        self.data()
586    }
587}
588
589impl<'a, V, DE, UE, F> FaceHandle<'a, InnerTag, V, DE, UE, F> {
590    /// Returns the three inner edges adjacent to this face.
591    ///
592    #[doc = include_str!("../../../images/face_adjacent_edges.svg")]
593    ///
594    /// The edges are returned in counterclockwise order.
595    pub fn adjacent_edges(&self) -> [DirectedEdgeHandle<'a, V, DE, UE, F>; 3] {
596        let e1 = self.adjacent_edge();
597        let e0 = e1.prev();
598        let e2 = e1.next();
599        [e0, e1, e2]
600    }
601
602    /// Returns an edge that is adjacent to this face.
603    ///
604    /// If this face has multiple adjacent edges, any of them is returned.
605    pub fn adjacent_edge(&self) -> DirectedEdgeHandle<'a, V, DE, UE, F> {
606        // unwrap is okay since every inner face has an adjacent edge
607        let handle = self.dcel.face_adjacent_edge(self.handle).unwrap();
608        DynamicHandleImpl::new(self.dcel, handle)
609    }
610
611    /// Returns the face's three vertices.
612    ///
613    /// The vertices are returned in counterclockwise order.
614    pub fn vertices(&self) -> [VertexHandle<'a, V, DE, UE, F>; 3] {
615        let [e0, e1, e2] = self.adjacent_edges();
616        [e0.from(), e1.from(), e2.from()]
617    }
618}
619
620impl<V, DE, UE, F> FaceHandle<'_, InnerTag, V, DE, UE, F>
621where
622    V: HasPosition,
623{
624    /// Returns the positions of the face's vertices
625    ///
626    /// The positions are returned in counterclockwise order.
627    pub fn positions(&self) -> [Point2<V::Scalar>; 3] {
628        let [v0, v1, v2] = self.vertices();
629        [v0.position(), v1.position(), v2.position()]
630    }
631
632    /// Returns the triangle's area.
633    pub fn area(&self) -> V::Scalar {
634        math::triangle_area(self.positions())
635    }
636}
637
638impl<'a, V, DE, UE, F> FaceHandle<'a, InnerTag, V, DE, UE, F>
639where
640    V: HasPosition,
641    V::Scalar: Float,
642{
643    /// Returns the squared distance of a point to this triangle.
644    ///
645    /// The distance of a point inside the triangle is zero.
646    pub fn distance_2(&self, query_point: Point2<V::Scalar>) -> V::Scalar {
647        math::distance_2_triangle(self.positions(), query_point)
648    }
649
650    /// Returns the face's center point.
651    ///
652    /// The center point is the average position of its vertices.
653    pub fn center(&self) -> Point2<V::Scalar> {
654        let [v0, v1, v2] = self.positions();
655        let one = V::Scalar::one();
656        let three = one + one + one;
657        v0.add(v1.add(v2)).mul(one / three)
658    }
659
660    /// Returns the face's circumcircle center and the **squared** radius of the circumcircle.
661    ///
662    /// The circumcircle is the unique circle that intersects all three vertices of the face.
663    pub fn circumcircle(&self) -> (Point2<V::Scalar>, V::Scalar) {
664        math::circumcenter(self.positions())
665    }
666
667    /// Returns the face's circumcenter.
668    ///
669    /// The circumcenter is the center of the circumcircle.
670    pub fn circumcenter(&self) -> Point2<V::Scalar> {
671        self.circumcircle().0
672    }
673
674    /// Returns the barycentric coordinates of a point relative to this face.
675    ///
676    /// The returned coordinates will sum up to 1.
677    pub fn barycentric_interpolation(&self, coordinate: Point2<V::Scalar>) -> [V::Scalar; 3] {
678        let [v1, v2, v3] = self.vertices();
679        let [v1, v2, v3] = [v1.position(), v2.position(), v3.position()];
680        let (x, y) = (coordinate.x, coordinate.y);
681        let (x1, x2, x3) = (v1.x, v2.x, v3.x);
682        let (y1, y2, y3) = (v1.y, v2.y, v3.y);
683        let det = (y2 - y3) * (x1 - x3) + (x3 - x2) * (y1 - y3);
684        let lambda1 = ((y2 - y3) * (x - x3) + (x3 - x2) * (y - y3)) / det;
685        let lambda2 = ((y3 - y1) * (x - x3) + (x1 - x3) * (y - y3)) / det;
686        let lambda3 = V::Scalar::one() - lambda1 - lambda2;
687        [lambda1, lambda2, lambda3]
688    }
689
690    pub(crate) fn shortest_edge(&self) -> (DirectedEdgeHandle<'a, V, DE, UE, F>, V::Scalar) {
691        let [e0, e1, e2] = self.adjacent_edges();
692        let [l0, l1, l2] = [e0.length_2(), e1.length_2(), e2.length_2()];
693        if l0 < l1 && l0 < l2 {
694            (e0, l0)
695        } else if l1 < l2 {
696            (e1, l1)
697        } else {
698            (e2, l2)
699        }
700    }
701}
702
703impl<V, DE, UE, F> AsRef<V> for VertexHandle<'_, V, DE, UE, F> {
704    fn as_ref(&self) -> &V {
705        self.data()
706    }
707}
708
709impl<V, DE, UE, F> VertexHandle<'_, V, DE, UE, F>
710where
711    V: HasPosition,
712{
713    /// Returns the position of this vertex.
714    pub fn position(&self) -> Point2<V::Scalar> {
715        self.dcel.vertex_data(self.handle).position()
716    }
717}
718
719pub struct CCWEdgesNextBackFn;
720
721impl NextBackFn for CCWEdgesNextBackFn {
722    fn next<V, DE, UE, F>(
723        edge_handle: DirectedEdgeHandle<V, DE, UE, F>,
724    ) -> DirectedEdgeHandle<V, DE, UE, F> {
725        edge_handle.ccw()
726    }
727
728    fn next_back<V, DE, UE, F>(
729        edge_handle: DirectedEdgeHandle<V, DE, UE, F>,
730    ) -> DirectedEdgeHandle<V, DE, UE, F> {
731        edge_handle.cw()
732    }
733}
734
735impl<'a, V, DE, UE, F> VertexHandle<'a, V, DE, UE, F> {
736    /// Returns all directed edges going out of this vertex.
737    ///
738    /// The edges are returned in counterclockwise order, beginning at an arbitrary
739    /// edge.
740    ///
741    #[doc = include_str!("../../../images/circular_iterator.svg")]
742    ///
743    /// *A possible iteration order of `v.out_edges()`*
744    ///
745    /// *Note*: The returned iterator implements `DoubleEndedIterator`, allowing traversal in
746    /// clockwise order.
747    pub fn out_edges(&self) -> CircularIterator<'a, V, DE, UE, F, CCWEdgesNextBackFn> {
748        if let Some(edge) = self.out_edge() {
749            CircularIterator::new(edge)
750        } else {
751            CircularIterator::new_empty(DirectedEdgeHandle::new(
752                self.dcel,
753                FixedDirectedEdgeHandle::new(0),
754            ))
755        }
756    }
757
758    /// Returns an outgoing edge of this vertex.
759    ///
760    /// If the vertex has multiple outgoing edges, any of them is returned.
761    pub fn out_edge(&self) -> Option<DirectedEdgeHandle<'a, V, DE, UE, F>> {
762        self.dcel
763            .vertex_out_edge(self.handle)
764            .map(|handle| DirectedEdgeHandle::new(self.dcel, handle))
765    }
766
767    /// Returns the data associated with this vertex.
768    pub fn data(&self) -> &V {
769        self.dcel.vertex_data(self.handle)
770    }
771
772    /// Returns the voronoi face that corresponds to this vertex of the Delaunay triangulation.
773    pub fn as_voronoi_face(&self) -> VoronoiFace<'a, V, DE, UE, F> {
774        VoronoiFace::new(self.dcel, FixedHandleImpl::new(self.handle.index()))
775    }
776}
777
778impl<V, DE, UE, F> DirectedEdgeHandle<'_, V, DE, UE, F>
779where
780    V: HasPosition,
781    V::Scalar: Float,
782{
783    /// Returns the squared distance of a point to this edge.
784    pub fn distance_2(&self, query_point: Point2<V::Scalar>) -> V::Scalar {
785        self.as_undirected().distance_2(query_point)
786    }
787
788    /// Yields the nearest point on this edge.
789    pub fn nearest_point(&self, query_point: Point2<V::Scalar>) -> Point2<V::Scalar> {
790        self.as_undirected().nearest_point(query_point)
791    }
792
793    /// Returns the center of this edge
794    pub fn center(&self) -> Point2<V::Scalar> {
795        self.as_undirected().center()
796    }
797}
798
799impl<V, DE, UE, F, InnerOuter: InnerOuterMarker> FaceHandle<'_, InnerOuter, V, DE, UE, F> {
800    /// Returns a reference to the data associated with this face.
801    pub fn data(&self) -> &F {
802        self.dcel.face_data(self.handle)
803    }
804}
805
806impl<'a, V, DE, UE, F> FaceHandle<'a, PossiblyOuterTag, V, DE, UE, F> {
807    /// Returns `true` if this handle refers to the single outer face.
808    #[inline]
809    pub fn is_outer(&self) -> bool {
810        self.handle.is_outer()
811    }
812
813    /// Converts this possibly outer face handle into an inner face handle.
814    ///
815    /// Returns `None` if this handle refers to the outer face.
816    pub fn as_inner(&self) -> Option<FaceHandle<'a, InnerTag, V, DE, UE, F>> {
817        if self.is_outer() {
818            None
819        } else {
820            Some(FaceHandle::new(self.dcel, self.handle.adjust_inner_outer()))
821        }
822    }
823
824    /// Returns an edge that is adjacent to this face.
825    ///
826    /// The returned edge has this face on its left side.
827    /// Returns `None` if the triangulation has only one or no vertices.
828    pub fn adjacent_edge(&self) -> Option<DirectedEdgeHandle<'a, V, DE, UE, F>> {
829        self.dcel
830            .face_adjacent_edge(self.handle)
831            .map(|handle| DirectedEdgeHandle::new(self.dcel, handle))
832    }
833}
834
835#[cfg(test)]
836mod test {
837    use super::FixedDirectedEdgeHandle;
838
839    #[test]
840    fn test_new_normalized_and_index_and_sym() {
841        for index in 0..10 {
842            let handle: FixedDirectedEdgeHandle = FixedDirectedEdgeHandle::new_normalized(index);
843            let rev = handle.rev();
844            assert_eq!(handle.as_undirected().index(), index);
845            assert!(handle.is_normalized());
846
847            assert_ne!(handle, handle.rev());
848            assert!(!rev.is_normalized());
849            assert_eq!(rev.rev(), handle);
850        }
851    }
852}
spade/delaunay_core/handles/handle_impls.rs

spade/delaunay_core/handles/
handle_impls.rs
