geo/algorithm/relate/geomgraph/intersection_matrix.rs
1use crate::{coordinate_position::CoordPos, dimensions::Dimensions};
2
3/// Models a *Dimensionally Extended Nine-Intersection Model (DE-9IM)* matrix.
4///
5/// DE-9IM matrix values (such as "212FF1FF2") specify the topological relationship between
6/// two [Geometries](struct.Geometry.html).
7///
8/// DE-9IM matrices are 3x3 matrices that represent the topological locations
9/// that occur in a geometry (Interior, Boundary, Exterior).
10///
11/// The indices are provided by the enum cases
12/// [CoordPos::Inside, CoordPos::OnBoundary, CoordPos::Outside](CoordPos).
13///
14/// The matrix entries represent the [Dimensions](enum.Dimension.html) of each intersection.
15///
16/// For a description of the DE-9IM and the spatial predicates derived from it,
17/// see the following references:
18/// - [OGC 99-049 OpenGIS Simple Features Specification for SQL](http://portal.opengeospatial.org/files/?artifact_id=829), Section 2.1.13
19/// - [OGC 06-103r4 OpenGIS Implementation Standard for Geographic information - Simple feature access - Part 1: Common architecture](http://portal.opengeospatial.org/files/?artifact_id=25355), Section 6.1.15 (which provides some further details on certain predicate specifications).
20/// - Wikipedia article on [DE-9IM](https://en.wikipedia.org/wiki/DE-9IM)
21///
22/// This implementation is heavily based on that from the [JTS project](https://github.com/locationtech/jts/blob/master/modules/core/src/main/java/org/locationtech/jts/geom/IntersectionMatrix.java).
23#[derive(PartialEq, Eq, Clone)]
24pub struct IntersectionMatrix(LocationArray<LocationArray<Dimensions>>);
25
26/// Helper struct so we can index IntersectionMatrix by CoordPos
27///
28/// CoordPos enum members are ordered: OnBoundary, Inside, Outside
29/// DE-9IM matrices are ordered: Inside, Boundary, Exterior
30///
31/// So we can't simply `CoordPos as usize` without losing the conventional ordering
32/// of elements, which is useful for debug / interop.
33#[derive(PartialEq, Eq, Clone, Copy)]
34struct LocationArray<T>([T; 3]);
35
36impl<T> LocationArray<T> {
37 fn iter(&self) -> impl Iterator<Item = &T> {
38 self.0.iter()
39 }
40}
41
42impl<T> std::ops::Index<CoordPos> for LocationArray<T> {
43 type Output = T;
44
45 fn index(&self, index: CoordPos) -> &Self::Output {
46 match index {
47 CoordPos::Inside => &self.0[0],
48 CoordPos::OnBoundary => &self.0[1],
49 CoordPos::Outside => &self.0[2],
50 }
51 }
52}
53
54impl<T> std::ops::IndexMut<CoordPos> for LocationArray<T> {
55 fn index_mut(&mut self, index: CoordPos) -> &mut Self::Output {
56 match index {
57 CoordPos::Inside => &mut self.0[0],
58 CoordPos::OnBoundary => &mut self.0[1],
59 CoordPos::Outside => &mut self.0[2],
60 }
61 }
62}
63
64#[derive(Debug)]
65pub struct InvalidInputError {
66 message: String,
67}
68
69impl InvalidInputError {
70 fn new(message: String) -> Self {
71 Self { message }
72 }
73}
74
75impl std::error::Error for InvalidInputError {}
76impl std::fmt::Display for InvalidInputError {
77 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
78 write!(f, "invalid input: {}", self.message)
79 }
80}
81
82impl std::fmt::Debug for IntersectionMatrix {
83 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
84 fn char_for_dim(dim: &Dimensions) -> &'static str {
85 match dim {
86 Dimensions::Empty => "F",
87 Dimensions::ZeroDimensional => "0",
88 Dimensions::OneDimensional => "1",
89 Dimensions::TwoDimensional => "2",
90 }
91 }
92 let text = self
93 .0
94 .iter()
95 .flat_map(|r| r.iter().map(char_for_dim))
96 .collect::<Vec<&str>>()
97 .join("");
98
99 write!(f, "IntersectionMatrix({})", &text)
100 }
101}
102
103impl IntersectionMatrix {
104 pub fn empty() -> Self {
105 IntersectionMatrix(LocationArray([LocationArray([Dimensions::Empty; 3]); 3]))
106 }
107
108 /// Set `dimensions` of the cell specified by the positions.
109 ///
110 /// `position_a`: which position `dimensions` applies to within the first geometry
111 /// `position_b`: which position `dimensions` applies to within the second geometry
112 /// `dimensions`: the dimension of the incident
113 pub(crate) fn set(
114 &mut self,
115 position_a: CoordPos,
116 position_b: CoordPos,
117 dimensions: Dimensions,
118 ) {
119 self.0[position_a][position_b] = dimensions;
120 }
121
122 /// Reports an incident of `dimensions`, which updates the IntersectionMatrix if it's greater
123 /// than what has been reported so far.
124 ///
125 /// `position_a`: which position `minimum_dimensions` applies to within the first geometry
126 /// `position_b`: which position `minimum_dimensions` applies to within the second geometry
127 /// `minimum_dimensions`: the dimension of the incident
128 pub(crate) fn set_at_least(
129 &mut self,
130 position_a: CoordPos,
131 position_b: CoordPos,
132 minimum_dimensions: Dimensions,
133 ) {
134 if self.0[position_a][position_b] < minimum_dimensions {
135 self.0[position_a][position_b] = minimum_dimensions;
136 }
137 }
138
139 /// If both geometries have `Some` position, then changes the specified element to at
140 /// least `minimum_dimensions`.
141 ///
142 /// Else, if either is none, do nothing.
143 ///
144 /// `position_a`: which position `minimum_dimensions` applies to within the first geometry, or
145 /// `None` if the dimension was not incident with the first geometry.
146 /// `position_b`: which position `minimum_dimensions` applies to within the second geometry, or
147 /// `None` if the dimension was not incident with the second geometry.
148 /// `minimum_dimensions`: the dimension of the incident
149 pub(crate) fn set_at_least_if_in_both(
150 &mut self,
151 position_a: Option<CoordPos>,
152 position_b: Option<CoordPos>,
153 minimum_dimensions: Dimensions,
154 ) {
155 if let (Some(position_a), Some(position_b)) = (position_a, position_b) {
156 self.set_at_least(position_a, position_b, minimum_dimensions);
157 }
158 }
159
160 pub(crate) fn set_at_least_from_string(
161 &mut self,
162 dimensions: &str,
163 ) -> Result<(), InvalidInputError> {
164 if dimensions.len() != 9 {
165 let message = format!("Expected dimensions length 9, found: {}", dimensions.len());
166 return Err(InvalidInputError::new(message));
167 }
168
169 let mut chars = dimensions.chars();
170 for a in &[CoordPos::Inside, CoordPos::OnBoundary, CoordPos::Outside] {
171 for b in &[CoordPos::Inside, CoordPos::OnBoundary, CoordPos::Outside] {
172 match chars.next().expect("already validated length is 9") {
173 '0' => self.0[*a][*b] = self.0[*a][*b].max(Dimensions::ZeroDimensional),
174 '1' => self.0[*a][*b] = self.0[*a][*b].max(Dimensions::OneDimensional),
175 '2' => self.0[*a][*b] = self.0[*a][*b].max(Dimensions::TwoDimensional),
176 'F' => {}
177 other => {
178 let message = format!("expected '0', '1', '2', or 'F'. Found: {other}");
179 return Err(InvalidInputError::new(message));
180 }
181 }
182 }
183 }
184
185 Ok(())
186 }
187
188 /// Tests if this matrix matches `[FF*FF****]`.
189 ///
190 /// returns `true` if the two geometries related by this matrix are disjoint
191 pub fn is_disjoint(&self) -> bool {
192 self.0[CoordPos::Inside][CoordPos::Inside] == Dimensions::Empty
193 && self.0[CoordPos::Inside][CoordPos::OnBoundary] == Dimensions::Empty
194 && self.0[CoordPos::OnBoundary][CoordPos::Inside] == Dimensions::Empty
195 && self.0[CoordPos::OnBoundary][CoordPos::OnBoundary] == Dimensions::Empty
196 }
197
198 /// Tests if `is_disjoint` returns false.
199 ///
200 /// returns `true` if the two geometries related by this matrix intersect.
201 pub fn is_intersects(&self) -> bool {
202 !self.is_disjoint()
203 }
204
205 /// Tests whether this matrix matches `[T*F**F***]`.
206 ///
207 /// returns `true` if the first geometry is within the second.
208 pub fn is_within(&self) -> bool {
209 self.0[CoordPos::Inside][CoordPos::Inside] != Dimensions::Empty
210 && self.0[CoordPos::Inside][CoordPos::Outside] == Dimensions::Empty
211 && self.0[CoordPos::OnBoundary][CoordPos::Outside] == Dimensions::Empty
212 }
213
214 /// Tests whether this matrix matches `[T*****FF*]`.
215 ///
216 /// returns `true` if the first geometry contains the second.
217 pub fn is_contains(&self) -> bool {
218 self.0[CoordPos::Inside][CoordPos::Inside] != Dimensions::Empty
219 && self.0[CoordPos::Outside][CoordPos::Inside] == Dimensions::Empty
220 && self.0[CoordPos::Outside][CoordPos::OnBoundary] == Dimensions::Empty
221 }
222
223 /// Directly accesses this matrix
224 ///
225 /// ```
226 /// use geo_types::{LineString, Rect, line_string};
227 /// use geo::{coordinate_position::CoordPos, dimensions::Dimensions, relate::Relate};
228 ///
229 /// let line_string: LineString = line_string![(x: 0.0, y: 0.0), (x: 10.0, y: 0.0), (x: 5.0, y: 5.0)];
230 /// let rect = Rect::new((0.0, 0.0), (5.0, 5.0));
231 ///
232 /// let intersection = line_string.relate(&rect);
233 ///
234 /// // The intersection of the two interiors is empty, because no part of the string is inside the rect
235 /// assert_eq!(intersection.get(CoordPos::Inside, CoordPos::Inside), Dimensions::Empty);
236 ///
237 /// // The intersection of the line string's interior with the rect's boundary is one-dimensional, because part of the first line overlaps one of the rect's edges
238 /// assert_eq!(intersection.get(CoordPos::Inside, CoordPos::OnBoundary), Dimensions::OneDimensional);
239 ///
240 /// // The intersection of the line string's interior with the rect's exterior is one-dimensional, because part of the string is outside the rect
241 /// assert_eq!(intersection.get(CoordPos::Inside, CoordPos::Outside), Dimensions::OneDimensional);
242 ///
243 /// // The intersection of the line string's boundary with the rect's interior is empty, because neither of its end points are inside the rect
244 /// assert_eq!(intersection.get(CoordPos::OnBoundary, CoordPos::Inside), Dimensions::Empty);
245 ///
246 /// // The intersection of the line string's boundary with the rect's boundary is zero-dimensional, because the string's start and end points are on the rect's edges
247 /// assert_eq!(intersection.get(CoordPos::OnBoundary, CoordPos::OnBoundary), Dimensions::ZeroDimensional);
248 ///
249 /// // The intersection of the line string's boundary with the rect's exterior is empty, because neither of its end points are outside the rect
250 /// assert_eq!(intersection.get(CoordPos::OnBoundary, CoordPos::Outside), Dimensions::Empty);
251 ///
252 /// // The intersection of the the line's exterior with the rect's interior is two-dimensional, because it's simply the rect's interior
253 /// assert_eq!(intersection.get(CoordPos::Outside, CoordPos::Inside), Dimensions::TwoDimensional);
254 ///
255 /// // The intersection of the line's exterior with the rect's boundary is one-dimensional, because it's the rect's edges (minus where the string overlaps it)
256 /// assert_eq!(intersection.get(CoordPos::Outside, CoordPos::OnBoundary), Dimensions::OneDimensional);
257 ///
258 /// // The intersection of the two exteriors is two-dimensional, because it's the whole plane around the two shapes
259 /// assert_eq!(intersection.get(CoordPos::Outside, CoordPos::Outside), Dimensions::TwoDimensional);
260 /// ```
261 pub fn get(&self, lhs: CoordPos, rhs: CoordPos) -> Dimensions {
262 self.0[lhs][rhs]
263 }
264}
265
266impl std::str::FromStr for IntersectionMatrix {
267 type Err = InvalidInputError;
268 fn from_str(str: &str) -> Result<Self, Self::Err> {
269 let mut im = IntersectionMatrix::empty();
270 im.set_at_least_from_string(str)?;
271 Ok(im)
272 }
273}