interior_point/
verify_interior_point.rs

1//! Verifies a computed interior point against the geometry it came from.
2//!
3//! `interior_point` claims its result lies on or in its input, and nothing else
4//! in this crate lets a caller confirm that. This module answers it for one
5//! result, through the point-in-polygon locator — an independent code path that
6//! shares nothing with the scanline that produced the point.
7//!
8//! This is not a geometry-validity check. An input whose rings self-intersect or
9//! whose hole lies outside its shell can still yield a point that verifies; the
10//! two properties are unrelated and neither substitutes for the other.
11//!
12//! @jts-adapter InteriorPoint — an original surface with no JTS counterpart:
13//!   JTS ships no result-verification API, and nothing here is ported.
14
15use std::fmt;
16
17use geo_types::{Coord, Geometry};
18
19use crate::algorithm::interior_point::dimension_non_empty;
20use crate::algorithm::locate::simple_point_in_area_locator::locate;
21use crate::geom::location::{BOUNDARY, INTERIOR};
22use crate::geometry_adapter::coordinates_at_dimension;
23
24/// Where a computed interior point sits relative to its geometry.
25///
26/// `Interior` and `OnGeometry` are both passes and are not the same fact:
27/// an areal point that lands exactly on the boundary is what
28/// `InteriorPoint`'s own contract falls back to when an exact interior point
29/// cannot be calculated. `Unverifiable` is the absence of an answer rather than
30/// a failed one, which is why the command line treats `OffGeometry` alone as a
31/// failure.
32#[derive(Clone, Copy, Debug, PartialEq, Eq)]
33pub enum Verification {
34    /// The point lies in the interior of an areal geometry.
35    Interior,
36    /// The point lies on the boundary of an areal geometry, or equals a
37    /// coordinate of a dimension 0 or 1 geometry.
38    OnGeometry,
39    /// The point lies outside the geometry.
40    OffGeometry,
41    /// No point, no geometry, or a geometry whose every element is empty.
42    Unverifiable,
43}
44
45/// The four spellings are what reach a caller's output, so they are fixed here
46/// rather than derived from the variant names: the TypeScript port prints the
47/// same four strings, and the two command lines are held to byte-for-byte
48/// agreement.
49impl fmt::Display for Verification {
50    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
51        f.write_str(match self {
52            Self::Interior => "interior",
53            Self::OnGeometry => "on-geometry",
54            Self::OffGeometry => "off-geometry",
55            Self::Unverifiable => "unverifiable",
56        })
57    }
58}
59
60/// Reports where `point` sits relative to `geometry`.
61///
62/// Both arguments are optional because both callers already hold optionals:
63/// `interior_point` returns `None` for an empty input, and a GeoJSON Feature may
64/// carry a null geometry. Either `None` is `Unverifiable`.
65///
66/// Dispatch is on `dimension_non_empty`, the same function `interior_point`
67/// dispatches on, and not on the adapter's `dimension`. The two disagree when a
68/// collection holds an empty element of higher dimension than its non-empty
69/// ones — `GEOMETRYCOLLECTION (POINT (5 5), LINESTRING EMPTY)` is dimension 1
70/// and non-empty dimension 0 — and following `dimension` there would contradict
71/// the point that was actually computed.
72pub fn verify_interior_point(
73    point: Option<Coord<f64>>,
74    geometry: Option<&Geometry<f64>>,
75) -> Verification {
76    let (Some(point), Some(geometry)) = (point, geometry) else {
77        return Verification::Unverifiable;
78    };
79    let dim = dimension_non_empty(geometry);
80    if dim < 0 {
81        return Verification::Unverifiable;
82    }
83    if dim == 2 {
84        let location = locate(point, geometry);
85        if location == INTERIOR {
86            return Verification::Interior;
87        }
88        if location == BOUNDARY {
89            return Verification::OnGeometry;
90        }
91        return Verification::OffGeometry;
92    }
93    // Dimension 0 and 1 have no interior for the locator to find: a ray cast at
94    // a LineString's own vertex still counts zero crossings. What the algorithm
95    // guarantees there is that the point is one of the coordinates of the
96    // non-empty elements of that dimension, compared ordinate by ordinate.
97    // `interior_point_line` and `interior_point_point` both copy the coordinate
98    // they choose, so identity comparison would never hold; the exact ordinate
99    // comparison is the intended one and must not be loosened to an epsilon.
100    if coordinates_at_dimension(geometry, dim)
101        .iter()
102        .any(|c| c.x == point.x && c.y == point.y)
103    {
104        Verification::OnGeometry
105    } else {
106        Verification::OffGeometry
107    }
108}
109
110#[cfg(test)]
111mod tests {
112    use super::{Verification, verify_interior_point};
113    use crate::interior_point;
114    use geo_types::{
115        Coord, Geometry, GeometryCollection, LineString, MultiLineString, MultiPoint, Point,
116        Polygon,
117    };
118
119    fn polygon(ring: &[(f64, f64)]) -> Geometry<f64> {
120        Geometry::Polygon(Polygon::new(LineString::from(ring.to_vec()), vec![]))
121    }
122
123    /// Verifies the point the algorithm actually returned for `geometry`.
124    fn verify_computed(geometry: &Geometry<f64>) -> Verification {
125        verify_interior_point(interior_point(geometry), Some(geometry))
126    }
127
128    #[test]
129    fn reports_interior_for_a_point_inside_an_areal_geometry() {
130        let square = polygon(&[
131            (0.0, 0.0),
132            (10.0, 0.0),
133            (10.0, 10.0),
134            (0.0, 10.0),
135            (0.0, 0.0),
136        ]);
137        assert_eq!(interior_point(&square), Some(Coord { x: 5.0, y: 5.0 }));
138        assert_eq!(verify_computed(&square), Verification::Interior);
139    }
140
141    #[test]
142    fn reports_on_geometry_for_a_zero_area_polygon() {
143        let collapsed = polygon(&[(10.0, 10.0), (10.0, 10.0), (10.0, 10.0), (10.0, 10.0)]);
144        assert_eq!(verify_computed(&collapsed), Verification::OnGeometry);
145    }
146
147    #[test]
148    fn reports_on_geometry_for_a_polygon_collapsed_to_a_segment() {
149        let collapsed = polygon(&[(0.0, 0.0), (10.0, 0.0), (0.0, 0.0)]);
150        assert_eq!(verify_computed(&collapsed), Verification::OnGeometry);
151    }
152
153    #[test]
154    fn reports_on_geometry_for_a_point() {
155        let point = Geometry::Point(Point::new(5.0, 5.0));
156        assert_eq!(verify_computed(&point), Verification::OnGeometry);
157    }
158
159    #[test]
160    fn reports_on_geometry_for_a_line_string() {
161        let line = Geometry::LineString(LineString::from(vec![(0.0, 0.0), (10.0, 10.0)]));
162        assert_eq!(interior_point(&line), Some(Coord { x: 0.0, y: 0.0 }));
163        assert_eq!(verify_computed(&line), Verification::OnGeometry);
164    }
165
166    #[test]
167    fn reports_on_geometry_for_a_multi_point() {
168        let points = Geometry::MultiPoint(MultiPoint(vec![
169            Point::new(0.0, 0.0),
170            Point::new(10.0, 10.0),
171        ]));
172        assert_eq!(verify_computed(&points), Verification::OnGeometry);
173    }
174
175    #[test]
176    fn reports_on_geometry_for_a_collection_of_a_point_and_a_line() {
177        let collection = Geometry::GeometryCollection(GeometryCollection(vec![
178            Geometry::Point(Point::new(5.0, 5.0)),
179            Geometry::LineString(LineString::from(vec![(0.0, 0.0), (10.0, 10.0)])),
180        ]));
181        assert_eq!(verify_computed(&collection), Verification::OnGeometry);
182    }
183
184    /// The dispatch is on the non-empty dimension, not the adapter's dimension.
185    /// This collection is dimension 1 and non-empty dimension 0, so the point
186    /// comes from the Point and the vertex comparison must run against the
187    /// dimension 0 elements. Dispatching on the plain dimension would look for
188    /// vertices in the empty LineString and answer off-geometry for a correct
189    /// point.
190    #[test]
191    fn follows_the_non_empty_dimension_for_a_collection_holding_an_empty_line() {
192        let collection = Geometry::GeometryCollection(GeometryCollection(vec![
193            Geometry::Point(Point::new(5.0, 5.0)),
194            Geometry::LineString(LineString(vec![])),
195        ]));
196        assert_eq!(interior_point(&collection), Some(Coord { x: 5.0, y: 5.0 }));
197        assert_eq!(verify_computed(&collection), Verification::OnGeometry);
198    }
199
200    /// The algorithm never produces one, so the only way here is a fabricated
201    /// point — which is why the point is a parameter rather than something this
202    /// function recomputes.
203    #[test]
204    fn reports_off_geometry_for_a_fabricated_point_outside_an_areal_geometry() {
205        let square = polygon(&[(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0), (0.0, 0.0)]);
206        assert_eq!(
207            verify_interior_point(Some(Coord { x: 100.0, y: 100.0 }), Some(&square)),
208            Verification::OffGeometry
209        );
210    }
211
212    #[test]
213    fn reports_off_geometry_for_a_fabricated_point_off_a_line_string() {
214        let line = Geometry::LineString(LineString::from(vec![(0.0, 0.0), (10.0, 10.0)]));
215        assert_eq!(
216            verify_interior_point(Some(Coord { x: 100.0, y: 100.0 }), Some(&line)),
217            Verification::OffGeometry
218        );
219    }
220
221    #[test]
222    fn reports_unverifiable_for_an_empty_geometry() {
223        let empty = Geometry::Polygon(Polygon::new(LineString(vec![]), vec![]));
224        assert_eq!(interior_point(&empty), None);
225        assert_eq!(verify_computed(&empty), Verification::Unverifiable);
226    }
227
228    #[test]
229    fn reports_unverifiable_for_a_multi_line_string_of_one_empty_line() {
230        let empty = Geometry::MultiLineString(MultiLineString::new(vec![LineString(vec![])]));
231        assert_eq!(verify_computed(&empty), Verification::Unverifiable);
232    }
233
234    #[test]
235    fn reports_unverifiable_when_either_argument_is_absent() {
236        let square = polygon(&[(0.0, 0.0), (1.0, 0.0), (1.0, 1.0), (0.0, 1.0), (0.0, 0.0)]);
237        assert_eq!(
238            verify_interior_point(None, Some(&square)),
239            Verification::Unverifiable
240        );
241        assert_eq!(
242            verify_interior_point(Some(Coord { x: 0.0, y: 0.0 }), None),
243            Verification::Unverifiable
244        );
245        assert_eq!(
246            verify_interior_point(None, None),
247            Verification::Unverifiable
248        );
249    }
250
251    #[test]
252    fn prints_the_four_outcome_words() {
253        assert_eq!(Verification::Interior.to_string(), "interior");
254        assert_eq!(Verification::OnGeometry.to_string(), "on-geometry");
255        assert_eq!(Verification::OffGeometry.to_string(), "off-geometry");
256        assert_eq!(Verification::Unverifiable.to_string(), "unverifiable");
257    }
258}
interior_point/verify_interior_point.rs

interior_point/
verify_interior_point.rs
