axiolid_overlay/free_faces/
locate.rs

1//! Which face a point is in.
2//!
3//! Every decision is an exact orientation of the point against binary64
4//! ring edges (`orient_doubles`), so the answer is exact for the rings as
5//! returned. A point within the snap displacement of a boundary may be
6//! answered as either neighbour (ADR 0100). The scan is linear in the
7//! number of ring edges, with a box test per ring; no performance claim.
8//!
9//! The answer is the first that holds:
10//!
11//! 1. On a ring edge of a face: scanning faces, outer ring then holes, edges
12//!    in output order.
13//! 2. Inside a face: inside its outer ring and in none of its holes. A point
14//!    on a dangling barrier or bridge is inside, since the piece bounds
15//!    nothing there.
16//! 3. In or on a closed gap, likewise.
17//! 4. In or on an obstacle: the closed outer ring, not strictly inside a
18//!    hole; the lowest index.
19//! 5. Otherwise unbounded.
20
21use axiolid_core::Point2;
22use axiolid_guarantees::Sign;
23
24use super::{FaceLocation, FreeFace, FreeFaces, FreeFacesError};
25use crate::exact_arc::orient_doubles;
26
27/// The box of a ring contains the point, edges included.
28fn in_box(ring: &[Point2], at: Point2) -> bool {
29    let (mut low, mut high) = (ring[0], ring[0]);
30    for point in ring {
31        low = Point2::new(low.x.min(point.x), low.y.min(point.y));
32        high = Point2::new(high.x.max(point.x), high.y.max(point.y));
33    }
34    low.x <= at.x && at.x <= high.x && low.y <= at.y && at.y <= high.y
35}
36
37/// The first edge of `ring` the point lies on.
38fn on_edge(ring: &[Point2], at: Point2) -> Option<usize> {
39    if !in_box(ring, at) {
40        return None;
41    }
42    (0..ring.len()).find(|&index| {
43        let (a, b) = (ring[index], ring[(index + 1) % ring.len()]);
44        orient_doubles(a, b, at) == Sign::Zero
45            && a.x.min(b.x) <= at.x
46            && at.x <= a.x.max(b.x)
47            && a.y.min(b.y) <= at.y
48            && at.y <= a.y.max(b.y)
49    })
50}
51
52/// Whether the winding number of the closed `ring` about a point that is
53/// not on it is not zero.
54fn encloses(ring: &[Point2], at: Point2) -> bool {
55    if !in_box(ring, at) {
56        return false;
57    }
58    let mut winding = 0i32;
59    for index in 0..ring.len() {
60        let (a, b) = (ring[index], ring[(index + 1) % ring.len()]);
61        let side = orient_doubles(a, b, at);
62        if a.y <= at.y {
63            if b.y > at.y && side == Sign::Positive {
64                winding += 1;
65            }
66        } else if b.y <= at.y && side == Sign::Negative {
67            winding -= 1;
68        }
69    }
70    winding != 0
71}
72
73/// Whether `at`, on no ring edge of `face`, is inside it.
74fn inside(face: &FreeFace, at: Point2) -> bool {
75    encloses(&face.outer.points, at) && !face.holes.iter().any(|hole| encloses(&hole.points, at))
76}
77
78impl FreeFaces {
79    /// Where `point` lies: in a face, on a ring edge, in a closed gap, in an
80    /// obstacle, or in none of them.
81    ///
82    /// # Errors
83    ///
84    /// [`FreeFacesError::NonFinitePoint`] for a point with a non-finite
85    /// coordinate.
86    pub fn locate(&self, point: Point2) -> Result<FaceLocation, FreeFacesError> {
87        if !point.is_finite() {
88            return Err(FreeFacesError::NonFinitePoint);
89        }
90        for (face, found) in self.faces.iter().enumerate() {
91            let rings = std::iter::once(&found.outer).chain(&found.holes);
92            for (ring, found) in rings.enumerate() {
93                if let Some(edge) = on_edge(&found.points, point) {
94                    return Ok(FaceLocation::OnBoundary { face, ring, edge });
95                }
96            }
97        }
98        if let Some(face) = self.faces.iter().position(|face| inside(face, point)) {
99            return Ok(FaceLocation::Inside(face));
100        }
101        let in_gap = |gap: &FreeFace| {
102            std::iter::once(&gap.outer)
103                .chain(&gap.holes)
104                .any(|ring| on_edge(&ring.points, point).is_some())
105                || inside(gap, point)
106        };
107        if let Some(gap) = self.closed_gaps.iter().position(in_gap) {
108            return Ok(FaceLocation::InClosedGap(gap));
109        }
110        let in_obstacle = |polygon: &crate::Polygon| {
111            let rings = std::iter::once(&polygon.outer).chain(&polygon.holes);
112            rings
113                .clone()
114                .any(|ring| on_edge(&ring.points, point).is_some())
115                || (encloses(&polygon.outer.points, point)
116                    && !polygon
117                        .holes
118                        .iter()
119                        .any(|hole| encloses(&hole.points, point)))
120        };
121        if let Some(obstacle) = self.obstacles.iter().position(in_obstacle) {
122            return Ok(FaceLocation::InObstacle(obstacle));
123        }
124        Ok(FaceLocation::Unbounded)
125    }
126}
axiolid_overlay/free_faces/locate.rs

axiolid_overlay/free_faces/
locate.rs
