spade/
intersection_iterator.rs

1use crate::delaunay_core::math;
2use crate::handles::{DirectedEdgeHandle, FixedVertexHandle, VertexHandle};
3use crate::{HasPosition, Point2, Triangulation, TriangulationExt};
4
5/// An iterator over all intersections of a straight line across the triangulation.
6///
7/// This iterator can, for example, be used to detect which edges prevent the insertion
8/// of a new constraint edge.
9///
10/// Three different intersection kinds are possible:
11///  - The line crosses a different edge
12///  - The line goes through a vertex
13///  - The line overlaps with an existing edge
14///
15/// These intersections are defined by the [Intersection] enum. Intersections are always returned in the same
16/// order as the line, i.e. the closest intersection to the starting point is returned first.
17///
18/// # Example
19///
20/// This triangulation is created by the code below:
21///
22#[doc = include_str!("../images/line_intersection_iterator_scenario.svg")]
23///
24/// The line (s -> e) generates 5 intersections (labeled with `0..=4`): two edge intersections,
25/// a vertex intersection, an edge overlap and  a final vertex intersection.
26///
27/// ```
28/// use spade::{LineIntersectionIterator, Point2, DelaunayTriangulation};
29/// # use spade::InsertionError;
30/// # fn main() -> Result<(), InsertionError> {
31/// let vertices = vec![
32///     Point2::new(-30.0, 20.0),  // v0
33///     Point2::new(0.0, -20.0),   // v1
34///     Point2::new(0.0, 20.0),    // v2
35///     Point2::new(14.0, 0.0),    // v3
36///     Point2::new(30.0, 0.0),    // v4
37/// ];
38///
39/// let triangulation = DelaunayTriangulation::<_>::bulk_load_stable(vertices)?;
40/// for intersection in LineIntersectionIterator::new(
41///     &triangulation,
42///     Point2::new(-30.0, 0.0),
43///     Point2::new(40.0, 0.0),
44/// ) {
45///     println!("{:?}", intersection);
46/// }
47/// # Ok(())
48/// # }
49/// ```
50///
51/// Output (simplified):
52/// ```text
53/// EdgeIntersection(DirectedEdgeHandle v0 -> v1)
54/// EdgeIntersection(DirectedEdgeHandle v2 -> v1)
55/// VertexIntersection(VertexHandle(3))
56/// EdgeOverlap(DirectedEdgeHandle v3 -> v4)
57/// VertexIntersection(VertexHandle(4))
58/// ```
59pub struct LineIntersectionIterator<'a, V, DE, UE, F>
60where
61    V: HasPosition,
62    DE: Default,
63    UE: Default,
64    F: Default,
65{
66    cur_intersection: Option<Intersection<'a, V, DE, UE, F>>,
67    line_from: Point2<V::Scalar>,
68    line_to: Point2<V::Scalar>,
69}
70
71/// An intersection that can occur when moving through a triangulation along a straight line.
72///
73/// This is used as return type for [LineIntersectionIterator].
74#[allow(clippy::enum_variant_names)]
75pub enum Intersection<'a, V, DE, UE, F>
76where
77    V: HasPosition,
78{
79    /// Indicates that the line is either crossing or touching an existing edge.
80    /// The line's destination will always be either on the edge or on its left side (in a right-handed coordinate system).
81    EdgeIntersection(DirectedEdgeHandle<'a, V, DE, UE, F>),
82    /// Indicates that the line is touching a vertex.
83    /// A line beginning or starting on a vertex also generates this intersection. A "line" beginning and starting on the same
84    /// vertex will also return this intersection.
85    VertexIntersection(VertexHandle<'a, V, DE, UE, F>),
86    /// Indicates that a line is (partially) overlapping an existing edge.
87    ///
88    /// This implies that the line points in the same direction as the edge and that they share a common line segment.
89    EdgeOverlap(DirectedEdgeHandle<'a, V, DE, UE, F>),
90}
91
92impl<V, DE, UE, F> core::fmt::Debug for Intersection<'_, V, DE, UE, F>
93where
94    V: HasPosition,
95{
96    fn fmt(&self, f: &mut core::fmt::Formatter) -> core::fmt::Result {
97        use self::Intersection::*;
98        match self {
99            EdgeIntersection(handle) => write!(f, "EdgeIntersection({:?})", handle),
100            VertexIntersection(handle) => write!(f, "VertexIntersection({:?})", handle),
101            EdgeOverlap(handle) => write!(f, "EdgeOverlap({:?})", handle),
102        }
103    }
104}
105
106impl<V, DE, UE, F> PartialEq for Intersection<'_, V, DE, UE, F>
107where
108    V: HasPosition,
109{
110    fn eq(&self, other: &Self) -> bool {
111        use self::Intersection::*;
112        match (self, other) {
113            (&EdgeIntersection(h0), &EdgeIntersection(h1)) => h0 == h1,
114            (&VertexIntersection(h0), &VertexIntersection(h1)) => h0 == h1,
115            (&EdgeOverlap(h0), &EdgeOverlap(h1)) => h0 == h1,
116            _ => false,
117        }
118    }
119}
120
121impl<V, DE, UE, F> Copy for Intersection<'_, V, DE, UE, F> where V: HasPosition {}
122
123impl<V, DE, UE, F> Clone for Intersection<'_, V, DE, UE, F>
124where
125    V: HasPosition,
126{
127    fn clone(&self) -> Self {
128        *self
129    }
130}
131
132impl<'a, V, DE, UE, F> Intersection<'a, V, DE, UE, F>
133where
134    V: HasPosition,
135{
136    /// Returns the intersected edge if this is an edge intersection or `None` otherwise.
137    pub fn as_edge_intersection(&self) -> Option<DirectedEdgeHandle<'a, V, DE, UE, F>> {
138        match self {
139            Intersection::EdgeIntersection(ref edge) => Some(*edge),
140            _ => None,
141        }
142    }
143}
144
145impl<'a, V, DE, UE, F> LineIntersectionIterator<'a, V, DE, UE, F>
146where
147    V: HasPosition,
148    DE: Default,
149    UE: Default,
150    F: Default,
151{
152    /// Creates a new `LineIntersectionIterator` covering an arbitrary line.
153    /// See [LineIntersectionIterator] for more information.
154    pub fn new<T>(
155        delaunay: &'a T,
156        line_from: Point2<V::Scalar>,
157        line_to: Point2<V::Scalar>,
158    ) -> LineIntersectionIterator<'a, V, DE, UE, F>
159    where
160        T: Triangulation<Vertex = V, DirectedEdge = DE, UndirectedEdge = UE, Face = F>,
161    {
162        let first_intersection = Self::get_first_intersection(delaunay, line_from, line_to);
163        LineIntersectionIterator {
164            cur_intersection: first_intersection,
165            line_from,
166            line_to,
167        }
168    }
169
170    /// Creates a new line iterator covering the line spanned by two existing vertices.
171    ///
172    /// Both start and end vertex are part of the iteration result.
173    ///
174    /// # Example
175    /// ```
176    /// use spade::{DelaunayTriangulation, Intersection, LineIntersectionIterator, Point2, Triangulation};
177    /// # use spade::InsertionError;
178    /// # fn main() -> Result<(), InsertionError> {
179    ///     let mut triangulation = DelaunayTriangulation::<Point2<f64>>::new();
180    ///     let v0 = triangulation.insert(Point2::new(0.0, 0.0))?;
181    ///     let v1 = triangulation.insert(Point2::new(1.0, 1.0))?;
182    ///
183    ///     let expected_edge_overlap = triangulation.get_edge_from_neighbors(v0, v1).unwrap();
184    ///     let all_intersections = LineIntersectionIterator::new_from_handles(&triangulation, v0, v1).collect::<Vec<_>>();
185    ///     
186    ///     let v0 = triangulation.vertex(v0);
187    ///     let v1 = triangulation.vertex(v1);
188    ///     assert_eq!(all_intersections, vec![
189    ///         Intersection::VertexIntersection(v0),
190    ///         Intersection::EdgeOverlap(expected_edge_overlap),
191    ///         Intersection::VertexIntersection(v1),
192    ///     ]);
193    /// # Ok(())
194    /// # }
195    /// ```
196    pub fn new_from_handles<T>(
197        delaunay: &T,
198        from: FixedVertexHandle,
199        to: FixedVertexHandle,
200    ) -> LineIntersectionIterator<'_, V, DE, UE, F>
201    where
202        T: Triangulation<Vertex = V, DirectedEdge = DE, UndirectedEdge = UE, Face = F>,
203    {
204        let from = delaunay.vertex(from);
205        let line_from = from.position();
206        let to = delaunay.vertex(to);
207        let line_to = to.position();
208
209        LineIntersectionIterator {
210            cur_intersection: Some(Intersection::VertexIntersection(from)),
211            line_from,
212            line_to,
213        }
214    }
215
216    fn get_first_intersection<T>(
217        delaunay: &'a T,
218        line_from: Point2<V::Scalar>,
219        line_to: Point2<V::Scalar>,
220    ) -> Option<Intersection<'a, V, DE, UE, F>>
221    where
222        T: Triangulation<Vertex = V, DirectedEdge = DE, UndirectedEdge = UE, Face = F>,
223    {
224        use crate::PositionInTriangulation::*;
225
226        match delaunay.locate_with_hint_option_core(line_from, None) {
227            OutsideOfConvexHull(edge_handle) => {
228                let mut edge = delaunay.directed_edge(edge_handle);
229                let line_from_query = edge.side_query(line_from);
230
231                loop {
232                    if line_from_query.is_on_line() {
233                        let dist_from = edge.from().position().distance_2(line_from);
234                        let dist_to = edge.to().position().distance_2(line_from);
235                        let vertex = if dist_to < dist_from {
236                            edge.to()
237                        } else {
238                            edge.from()
239                        };
240                        return Some(Intersection::VertexIntersection(vertex));
241                    }
242                    let line_to_query = edge.side_query(line_to);
243
244                    if line_to_query.is_on_left_side() {
245                        return None;
246                    }
247
248                    let edge_from = edge.from().position();
249                    let edge_to = edge.to().position();
250                    let edge_from_query = math::side_query(line_from, line_to, edge_from);
251                    let edge_to_query = math::side_query(line_from, line_to, edge_to);
252
253                    match (
254                        edge_from_query.is_on_left_side(),
255                        edge_to_query.is_on_left_side_or_on_line(),
256                    ) {
257                        (true, true) => edge = edge.prev(),
258                        (false, false) => edge = edge.next(),
259                        (false, true) => {
260                            if edge_to_query.is_on_line() {
261                                return Some(Intersection::VertexIntersection(edge.to()));
262                            }
263                            if edge_from_query.is_on_line() {
264                                return Some(Intersection::VertexIntersection(edge.from()));
265                            }
266                            return Some(Intersection::EdgeIntersection(edge.rev()));
267                        }
268                        (true, false) => panic!("Unexpected edge topology. This is a bug."),
269                    }
270                }
271            }
272            OnFace(face_handle) => get_first_edge_from_edge_ring(
273                delaunay.face(face_handle).adjacent_edges().iter().copied(),
274                line_from,
275                line_to,
276            ),
277            OnVertex(vertex_handle) => Some(Intersection::VertexIntersection(
278                delaunay.vertex(vertex_handle),
279            )),
280            OnEdge(edge) => {
281                let edge = delaunay.directed_edge(edge);
282                let edge_from = edge.from().position();
283                let edge_to = edge.to().position();
284                let from_query = math::side_query(line_from, line_to, edge_from);
285                let to_query = math::side_query(line_from, line_to, edge_to);
286                if from_query.is_on_line() && to_query.is_on_line() {
287                    let dist_to = edge_to.sub(line_to).length2();
288                    let dist_from = edge_from.sub(line_to).length2();
289                    if dist_to < dist_from {
290                        Some(Intersection::EdgeOverlap(edge))
291                    } else {
292                        Some(Intersection::EdgeOverlap(edge.rev()))
293                    }
294                } else {
295                    let edge_query = edge.side_query(line_to);
296                    if edge_query.is_on_left_side() {
297                        Some(Intersection::EdgeIntersection(edge))
298                    } else {
299                        Some(Intersection::EdgeIntersection(edge.rev()))
300                    }
301                }
302            }
303            NoTriangulation => {
304                if let Some(next_vertex) = delaunay.vertices().next() {
305                    let single_vertex = next_vertex.position();
306                    let projection = math::project_point(line_from, line_to, single_vertex);
307                    if projection.is_on_edge() {
308                        let query = math::side_query(line_from, line_to, single_vertex);
309                        if query.is_on_line() {
310                            return Some(Intersection::VertexIntersection(next_vertex));
311                        }
312                    }
313                }
314                None
315            }
316        }
317    }
318
319    fn get_next(&mut self) -> Option<Intersection<'a, V, DE, UE, F>> {
320        use self::Intersection::*;
321        match self.cur_intersection {
322            Some(EdgeIntersection(cur_edge)) => {
323                match trace_direction_out_of_edge(cur_edge, self.line_from, self.line_to) {
324                    EdgeOutDirection::ConvexHull => None,
325                    EdgeOutDirection::VertexIntersection(vertex) => {
326                        Some(VertexIntersection(vertex))
327                    }
328                    EdgeOutDirection::EdgeIntersection(edge) => Some(EdgeIntersection(edge)),
329                    EdgeOutDirection::NoIntersection => None,
330                }
331            }
332            Some(VertexIntersection(vertex)) => {
333                if vertex.position() == self.line_to {
334                    // Target point was reached - the iteration can finish
335                    None
336                } else {
337                    match trace_direction_out_of_vertex(vertex, self.line_to) {
338                        VertexOutDirection::ConvexHull => None,
339                        VertexOutDirection::EdgeOverlap(edge) => Some(EdgeOverlap(edge)),
340                        VertexOutDirection::EdgeIntersection(edge) => {
341                            if edge.side_query(self.line_to).is_on_right_side() {
342                                // The target point was skipped over - the iteration can finish
343                                None
344                            } else {
345                                Some(EdgeIntersection(edge))
346                            }
347                        }
348                    }
349                }
350            }
351            Some(EdgeOverlap(edge)) => {
352                if self.line_from == self.line_to {
353                    None
354                } else if math::project_point(self.line_from, self.line_to, edge.to().position())
355                    .is_on_edge()
356                {
357                    Some(VertexIntersection(edge.to()))
358                } else {
359                    None
360                }
361            }
362            None => None,
363        }
364    }
365}
366
367impl<'a, V, DE, UE, F> Iterator for LineIntersectionIterator<'a, V, DE, UE, F>
368where
369    V: HasPosition,
370    DE: Default,
371    UE: Default,
372    F: Default,
373{
374    type Item = Intersection<'a, V, DE, UE, F>;
375
376    fn next(&mut self) -> Option<Self::Item> {
377        let cur = self.cur_intersection;
378        self.cur_intersection = self.get_next();
379        cur
380    }
381}
382
383fn get_first_edge_from_edge_ring<'a, I, V, DE, UE, F>(
384    ring: I,
385    line_from: Point2<V::Scalar>,
386    line_to: Point2<V::Scalar>,
387) -> Option<Intersection<'a, V, DE, UE, F>>
388where
389    I: IntoIterator<Item = DirectedEdgeHandle<'a, V, DE, UE, F>>,
390    V: HasPosition,
391{
392    use self::Intersection::*;
393    for edge in ring {
394        let cur_from = edge.from().position();
395        let cur_to = edge.to().position();
396
397        debug_assert!(math::side_query(cur_from, cur_to, line_from).is_on_left_side_or_on_line());
398        if math::intersects_edge_non_collinear(line_from, line_to, cur_from, cur_to) {
399            if math::side_query(line_from, line_to, cur_from).is_on_line() {
400                return Some(VertexIntersection(edge.from()));
401            } else if math::side_query(line_from, line_to, cur_to).is_on_line() {
402                return Some(VertexIntersection(edge.to()));
403            }
404            return Some(EdgeIntersection(edge.rev()));
405        }
406    }
407    None
408}
409
410pub(super) enum VertexOutDirection<'a, V, DE, UE, F> {
411    ConvexHull,
412    EdgeOverlap(DirectedEdgeHandle<'a, V, DE, UE, F>),
413    EdgeIntersection(DirectedEdgeHandle<'a, V, DE, UE, F>),
414}
415
416pub(super) fn trace_direction_out_of_vertex<V, DE, UE, F>(
417    vertex: VertexHandle<V, DE, UE, F>,
418    line_to: Point2<V::Scalar>,
419) -> VertexOutDirection<V, DE, UE, F>
420where
421    V: HasPosition,
422{
423    let mut current_edge = match vertex.out_edge() {
424        Some(edge) => edge,
425        None => return VertexOutDirection::ConvexHull,
426    };
427
428    let mut current_query = current_edge.side_query(line_to);
429
430    let iterate_ccw = current_query.is_on_left_side();
431
432    loop {
433        if current_query.is_on_line() && !current_edge.project_point(line_to).is_before_edge() {
434            return VertexOutDirection::EdgeOverlap(current_edge);
435        }
436
437        let next = if iterate_ccw {
438            current_edge.ccw()
439        } else {
440            current_edge.cw()
441        };
442
443        let next_query = next.side_query(line_to);
444        if next_query.is_on_line() && !next.project_point(line_to).is_before_edge() {
445            return VertexOutDirection::EdgeOverlap(next);
446        }
447
448        let face_between_current_and_next = if iterate_ccw {
449            current_edge.face()
450        } else {
451            next.face()
452        };
453        if face_between_current_and_next.is_outer() {
454            return VertexOutDirection::ConvexHull;
455        }
456
457        if iterate_ccw == next_query.is_on_right_side() {
458            let segment_edge = if iterate_ccw {
459                current_edge.next()
460            } else {
461                current_edge.rev().prev()
462            };
463            return VertexOutDirection::EdgeIntersection(segment_edge.rev());
464        }
465
466        current_query = next_query;
467        current_edge = next;
468    }
469}
470
471pub(super) enum EdgeOutDirection<'a, V, DE, UE, F> {
472    ConvexHull,
473    VertexIntersection(VertexHandle<'a, V, DE, UE, F>),
474    EdgeIntersection(DirectedEdgeHandle<'a, V, DE, UE, F>),
475    NoIntersection,
476}
477
478pub(super) fn trace_direction_out_of_edge<V, DE, UE, F>(
479    edge: DirectedEdgeHandle<V, DE, UE, F>,
480    line_from: Point2<V::Scalar>,
481    line_to: Point2<V::Scalar>,
482) -> EdgeOutDirection<V, DE, UE, F>
483where
484    V: HasPosition,
485{
486    debug_assert!(
487        edge.side_query(line_to).is_on_left_side_or_on_line(),
488        "The target must be on the left side of the current edge"
489    );
490
491    let e_prev = if edge.is_outer_edge() {
492        // Iteration reached an edge of the convex hull, we're done.
493        return EdgeOutDirection::ConvexHull;
494    } else {
495        edge.prev()
496    };
497
498    let o_next = edge.next();
499
500    // Find out which edges of the left face intersect the line
501    let e_prev_inter = e_prev.intersects_edge_non_collinear(line_from, line_to);
502    let o_next_inter = o_next.intersects_edge_non_collinear(line_from, line_to);
503
504    match (e_prev_inter, o_next_inter) {
505        (true, false) => EdgeOutDirection::EdgeIntersection(e_prev.rev()),
506        (false, true) => EdgeOutDirection::EdgeIntersection(o_next.rev()),
507        (true, true) => {
508            // Both edges intersect - this means the line is cutting through a common point
509            EdgeOutDirection::VertexIntersection(e_prev.from())
510        }
511        (false, false) => EdgeOutDirection::NoIntersection,
512    }
513}
514
515#[cfg(test)]
516mod test {
517    use self::Intersection::*;
518    use super::*;
519    use crate::{InsertionError, Point2, Triangulation as _};
520
521    use alloc::{vec, vec::Vec};
522
523    type Triangulation = crate::DelaunayTriangulation<Point2<f64>>;
524
525    fn reverse<'a, V, DE, UE, F>(
526        intersection: &Intersection<'a, V, DE, UE, F>,
527    ) -> Intersection<'a, V, DE, UE, F>
528    where
529        V: HasPosition,
530    {
531        match intersection {
532            EdgeIntersection(edge) => EdgeIntersection(edge.rev()),
533            VertexIntersection(vertex) => VertexIntersection(*vertex),
534            EdgeOverlap(edge) => EdgeOverlap(edge.rev()),
535        }
536    }
537
538    fn check(
539        delaunay: &Triangulation,
540        from: Point2<f64>,
541        to: Point2<f64>,
542        mut expected: Vec<Intersection<Point2<f64>, (), (), ()>>,
543    ) {
544        let collected: Vec<_> = LineIntersectionIterator::new(delaunay, from, to).collect();
545        assert_eq!(collected, expected);
546        let mut reversed = Vec::new();
547        let rev_collected: Vec<_> = LineIntersectionIterator::new(delaunay, to, from).collect();
548        for intersection in rev_collected.iter() {
549            reversed.push(reverse(intersection));
550        }
551        expected.reverse();
552        assert_eq!(reversed, expected);
553    }
554
555    fn create_test_triangulation() -> Result<
556        (
557            Triangulation,
558            FixedVertexHandle,
559            FixedVertexHandle,
560            FixedVertexHandle,
561            FixedVertexHandle,
562        ),
563        InsertionError,
564    > {
565        let v0 = Point2::new(-2.0, -2.0);
566        let v1 = Point2::new(2.0, 2.0);
567        let v2 = Point2::new(1.0, -1.0);
568        let v3 = Point2::new(-1.0, 1.0);
569
570        let mut delaunay = Triangulation::new();
571        let v0 = delaunay.insert(v0)?;
572        let v1 = delaunay.insert(v1)?;
573        let v2 = delaunay.insert(v2)?;
574        let v3 = delaunay.insert(v3)?;
575
576        Ok((delaunay, v0, v1, v2, v3))
577    }
578
579    #[test]
580    fn test_single_line_intersection() -> Result<(), InsertionError> {
581        let (delaunay, _, _, v2, v3) = create_test_triangulation()?;
582        let from = Point2::new(-0.5, -0.5);
583        let to = Point2::new(0.5, 0.5);
584        let edge = delaunay.get_edge_from_neighbors(v3, v2).unwrap();
585        check(&delaunay, from, to, vec![EdgeIntersection(edge)]);
586        Ok(())
587    }
588
589    #[test]
590    fn test_empty_inner_intersection() -> Result<(), InsertionError> {
591        let (delaunay, _, _, _, _) = create_test_triangulation()?;
592        let from = Point2::new(-0.5, -0.5);
593        let to = Point2::new(-0.25, -0.25);
594        assert!(LineIntersectionIterator::new(&delaunay, from, to)
595            .next()
596            .is_none());
597
598        assert!(LineIntersectionIterator::new(&delaunay, from, from)
599            .next()
600            .is_none());
601        Ok(())
602    }
603
604    #[test]
605    fn test_between_vertices_intersection() -> Result<(), InsertionError> {
606        let (delaunay, v0, v1, v2, v3) = create_test_triangulation()?;
607        let from = Point2::new(-2.0, -2.0);
608        let to = Point2::new(2.0, 2.0);
609        let edge = delaunay.get_edge_from_neighbors(v3, v2).unwrap();
610        let first = VertexIntersection(delaunay.vertex(v0));
611        let last = VertexIntersection(delaunay.vertex(v1));
612        let edges: Vec<_> = LineIntersectionIterator::new(&delaunay, from, to).collect();
613        assert_eq!(edges, vec![first, EdgeIntersection(edge), last]);
614        Ok(())
615    }
616
617    #[test]
618    fn test_mixed_intersections() -> Result<(), InsertionError> {
619        let (mut delaunay, _, v1, v2, v3) = create_test_triangulation()?;
620        let v4 = delaunay.insert(Point2::new(1.0, 1.0))?;
621        let from = Point2::new(-1.0, -1.0);
622        let to = Point2::new(2.0, 2.0);
623        let intersection_edge = delaunay.get_edge_from_neighbors(v3, v2).unwrap();
624        let overlap_edge = delaunay.get_edge_from_neighbors(v4, v1).unwrap();
625        check(
626            &delaunay,
627            from,
628            to,
629            vec![
630                EdgeIntersection(intersection_edge),
631                VertexIntersection(delaunay.vertex(v4)),
632                EdgeOverlap(overlap_edge),
633                VertexIntersection(delaunay.vertex(v1)),
634            ],
635        );
636        Ok(())
637    }
638
639    #[test]
640    fn test_out_of_hull_intersections() -> Result<(), InsertionError> {
641        let (ref d, v0, v1, v2, v3) = create_test_triangulation()?;
642
643        let edge20 = d.get_edge_from_neighbors(v2, v0).unwrap();
644        let edge20 = EdgeIntersection(edge20);
645        let edge30 = d.get_edge_from_neighbors(v3, v0).unwrap();
646        let edge30 = EdgeIntersection(edge30);
647        let edge12 = d.get_edge_from_neighbors(v1, v2).unwrap();
648        let edge12 = EdgeIntersection(edge12);
649        let edge32 = d.get_edge_from_neighbors(v3, v2).unwrap();
650        let o32 = EdgeOverlap(edge32);
651        let edge32 = EdgeIntersection(edge32);
652
653        let v0 = VertexIntersection(d.vertex(v0));
654        let v2 = VertexIntersection(d.vertex(v2));
655        let v3 = VertexIntersection(d.vertex(v3));
656
657        // No intersection
658        let from = Point2::new(-2.0, 1.0);
659        let to = Point2::new(-2.0, 0.0);
660        check(d, from, to, vec![]);
661        // One intersection
662        let from = Point2::new(-2., 0.);
663        let to = Point2::new(-2., -4.0);
664        check(d, from, to, vec![v0]);
665        let from = Point2::new(-0.5, -0.5);
666        check(d, from, to, vec![edge20]);
667        // Two intersections
668        let from = Point2::new(-2.0, 0.0);
669        let to = Point2::new(0., -2.);
670        check(d, from, to, vec![edge30, edge20]);
671        let from = Point2::new(-3.0, 3.0);
672        let to = Point2::new(3.0, -3.0);
673        check(d, from, to, vec![v3, o32, v2]);
674        // Three intersections
675        let from = Point2::new(-2.0, 0.0);
676        let to = Point2::new(2., -1.);
677        check(d, from, to, vec![edge30, edge32, edge12]);
678        Ok(())
679    }
680
681    #[test]
682    fn test_on_line_intersection() -> Result<(), InsertionError> {
683        let (d, _, v1, v2, v3) = create_test_triangulation()?;
684
685        let edge = d.get_edge_from_neighbors(v2, v3).unwrap();
686        let e32 = EdgeIntersection(edge.rev());
687        let o23 = EdgeOverlap(edge);
688        let o32 = EdgeOverlap(edge.rev());
689
690        let v1 = VertexIntersection(d.vertex(v1));
691        let v2 = VertexIntersection(d.vertex(v2));
692        let v3 = VertexIntersection(d.vertex(v3));
693
694        let from = Point2::new(0.0, 0.0);
695        let to = Point2::new(0.0, 0.0);
696        let collected: Vec<_> = LineIntersectionIterator::new(&d, from, to).collect();
697        assert!(collected == vec![o23] || collected == vec![o32]);
698        let to = Point2::new(0.2, 0.2);
699        check(&d, from, to, vec![e32]);
700        let to = Point2::new(2.0, 2.0);
701        check(&d, from, to, vec![e32, v1]);
702        let to = Point2::new(-30.0, 30.0);
703        check(&d, from, to, vec![o23, v3]);
704        let to = Point2::new(30.0, -30.0);
705        check(&d, from, to, vec![o32, v2]);
706        let from = Point2::new(-30.0, 30.0);
707        check(&d, from, to, vec![v3, o32, v2]);
708        Ok(())
709    }
710
711    #[test]
712    fn test_intersecting_zero_vertices() {
713        let delaunay = Triangulation::new();
714        let mut iterator = LineIntersectionIterator::new(
715            &delaunay,
716            Point2::new(0.5, 1.234),
717            Point2::new(3.223, 42.0),
718        );
719        assert!(iterator.next().is_none());
720    }
721
722    #[test]
723    fn test_intersection_when_passing_equal_line_from_and_line_to() -> Result<(), InsertionError> {
724        let (delaunay, v1, _, v3, v4) = create_test_triangulation()?;
725        let v1_position = delaunay.s().vertex(v1).position();
726        let edge = delaunay.get_edge_from_neighbors(v3, v4).unwrap();
727        let v1 = delaunay.s().vertex(v1);
728
729        check(
730            &delaunay,
731            v1_position,
732            v1_position,
733            vec![VertexIntersection(v1)],
734        );
735        let origin = Point2::new(0.0, 0.0);
736        let intersections: Vec<_> =
737            LineIntersectionIterator::new(&delaunay, origin, origin).collect();
738
739        assert_eq![intersections.len(), 1];
740        assert!(
741            intersections[0] == EdgeOverlap(edge) || intersections[0] == EdgeOverlap(edge.rev())
742        );
743        Ok(())
744    }
745
746    #[test]
747    fn test_intersecting_single_vertex() -> Result<(), InsertionError> {
748        let mut delaunay = Triangulation::new();
749        let pos = Point2::new(0.5, 0.5);
750        let v0 = delaunay.insert(pos)?;
751        let v0 = delaunay.vertex(v0);
752        let from = Point2::new(1.0, 0.0);
753        let to = Point2::new(0.0, 1.0);
754        check(&delaunay, from, to, vec![VertexIntersection(v0)]);
755        check(&delaunay, pos, pos, vec![VertexIntersection(v0)]);
756        let to = Point2::new(1.234, 42.0);
757        check(&delaunay, from, to, vec![]);
758        Ok(())
759    }
760
761    #[test]
762    fn test_intersecting_degenerate_triangulation() -> Result<(), InsertionError> {
763        let mut d = Triangulation::new();
764
765        let v2 = d.insert(Point2::new(0.0, 0.0))?;
766        let v3 = d.insert(Point2::new(1.0, 1.0))?;
767        let v1 = d.insert(Point2::new(-2.0, -2.0))?;
768        let v0 = d.insert(Point2::new(-3.0, -3.0))?;
769
770        let e01 = d.get_edge_from_neighbors(v0, v1).unwrap();
771        let e12 = d.get_edge_from_neighbors(v1, v2).unwrap();
772        let e23 = d.get_edge_from_neighbors(v2, v3).unwrap();
773
774        let v0 = VertexIntersection(d.vertex(v0));
775        let v1 = VertexIntersection(d.vertex(v1));
776        let v2 = VertexIntersection(d.vertex(v2));
777        let v3 = VertexIntersection(d.vertex(v3));
778
779        let intersection_23 = EdgeIntersection(e23);
780        let e01 = EdgeOverlap(e01);
781        let e12 = EdgeOverlap(e12);
782        let e23 = EdgeOverlap(e23);
783
784        let from = Point2::new(-4.0, -4.0);
785        let to = Point2::new(5.0, 5.0);
786        check(&d, from, to, vec![v0, e01, v1, e12, v2, e23, v3]);
787        let to = Point2::new(-2.0, -2.0);
788        check(&d, from, to, vec![v0, e01, v1]);
789        let to = Point2::new(-0.5, -0.5);
790        check(&d, from, to, vec![v0, e01, v1, e12]);
791
792        let from = Point2::new(1.0, -0.0);
793        let to = Point2::new(0.0, 1.0);
794        check(&d, from, to, vec![intersection_23]);
795        let to = Point2::new(0.5, 0.5);
796        check(&d, from, to, vec![intersection_23]);
797
798        let from = Point2::new(0.5, -0.5);
799        let to = Point2::new(-0.5, 0.5);
800        check(&d, from, to, vec![v2]);
801
802        let single_vertex = Point2::new(-2.0, -2.0);
803        check(&d, single_vertex, single_vertex, vec![v1]);
804
805        Ok(())
806    }
807
808    #[test]
809    fn test_intersecting_through_point_ending_on_face() -> Result<(), InsertionError> {
810        let mut d = Triangulation::new();
811
812        let v0 = d.insert(Point2::new(0.0, 0.0))?;
813        let v1 = d.insert(Point2::new(1.0, 1.0))?;
814        let v2 = d.insert(Point2::new(-1.0, 1.0))?;
815        let v3 = d.insert(Point2::new(0.0, 2.0))?;
816        d.insert(Point2::new(-1.0, 3.0))?;
817        d.insert(Point2::new(1.0, 3.0))?;
818
819        let e = d.get_edge_from_neighbors(v2, v1).unwrap();
820
821        let v0 = VertexIntersection(d.vertex(v0));
822        let e = EdgeIntersection(e);
823        let v3 = VertexIntersection(d.vertex(v3));
824
825        let from = Point2::new(0.0, 0.0);
826        let to = Point2::new(0.0, 2.5);
827        check(&d, from, to, vec![v0, e, v3]);
828        Ok(())
829    }
830}
spade/intersection_iterator.rs

spade/
intersection_iterator.rs
