spatial_join/
structs.rs

1use std::convert::TryInto;
2
3use geo::{Geometry, Line, LineString, Point, Polygon, Rect, Triangle};
4use thiserror::Error;
5
6#[cfg(feature = "parallel")]
7use rayon::prelude::*;
8
9#[derive(Error, Debug, PartialEq, Clone)]
10pub enum Error {
11    #[error("Inifinite or NaN coordinate value in geo at index {0:?}: {1:?}")]
12    BadCoordinateValue(usize, Geometry<f64>),
13
14    #[error("max_distance must be finite and greater than or equal to zero: {0:?}")]
15    BadMaxDistance(f64),
16
17    #[error("LineString at index {0:?} must have at least two points")]
18    LineStringTooSmall(usize),
19
20    #[error("Polygon at index {0:?} must have an exterior with at least three points")]
21    PolygonExteriorTooSmall(usize),
22}
23
24#[derive(Clone, Copy, Debug, PartialEq, Eq)]
25pub enum Interaction {
26    Intersects,
27    Within,
28    Contains,
29}
30
31#[derive(Clone, Copy, Default, Debug, PartialEq)]
32pub struct Config {
33    pub max_distance: f64,
34}
35
36impl Config {
37    pub fn new() -> Config {
38        Default::default()
39    }
40
41    #[allow(clippy::needless_update)]
42    pub fn max_distance(self, value: f64) -> Config {
43        Config {
44            max_distance: value,
45            ..self
46        }
47    }
48
49    pub fn validate(&self) -> Option<Error> {
50        if !(self.max_distance.is_finite() && self.max_distance >= 0.) {
51            return Some(Error::BadMaxDistance(self.max_distance));
52        }
53
54        None
55    }
56
57    pub fn serial<T, U>(self, small: T) -> Result<super::SpatialIndex, Error>
58    where
59        T: TryInto<SplitGeoSeq, Error = U>,
60        U: std::any::Any,
61    {
62        if let Some(error) = self.validate() {
63            return Err(error);
64        }
65        super::SpatialIndex::new(small, self)
66    }
67
68    #[cfg(feature = "parallel")]
69    pub fn parallel<T, U>(self, small: T) -> Result<super::ParSpatialIndex, Error>
70    where
71        T: TryInto<Par<SplitGeoSeq>, Error = U>,
72        U: std::any::Any,
73    {
74        if let Some(error) = self.validate() {
75            return Err(error);
76        }
77        super::ParSpatialIndex::new(small, self)
78    }
79}
80
81pub struct Par<T>(pub T);
82
83#[derive(Default, PartialEq, Debug, Clone)]
84pub(crate) struct SplitGeo {
85    pub points: Vec<Point<f64>>,
86    pub lines: Vec<Line<f64>>,
87    pub polys: Vec<Polygon<f64>>,
88    pub line_strings: Vec<LineString<f64>>,
89    pub rects: Vec<Rect<f64>>,
90    pub tris: Vec<Triangle<f64>>,
91}
92
93impl SplitGeoSeq {
94    pub fn merge(mut a: SplitGeoSeq, mut b: SplitGeoSeq) -> SplitGeoSeq {
95        a.geos.points.append(&mut b.geos.points);
96        a.geos.lines.append(&mut b.geos.lines);
97        a.geos.polys.append(&mut b.geos.polys);
98        a.geos.line_strings.append(&mut b.geos.line_strings);
99        a.geos.rects.append(&mut b.geos.rects);
100        a.geos.tris.append(&mut b.geos.tris);
101
102        a.indexes.points = a.indexes.points.merge(b.indexes.points);
103        a.indexes.lines = a.indexes.lines.merge(b.indexes.lines);
104        a.indexes.line_strings = a.indexes.line_strings.merge(b.indexes.line_strings);
105        a.indexes.polys = a.indexes.polys.merge(b.indexes.polys);
106        a.indexes.rects = a.indexes.rects.merge(b.indexes.rects);
107        a.indexes.tris = a.indexes.tris.merge(b.indexes.tris);
108
109        a
110    }
111}
112
113lazy_static::lazy_static! {
114    static ref EMPTY_VEC: Vec<usize> = vec![];
115}
116
117// Sigh...maybe we should just replace this with IDLBitRange
118#[derive(PartialEq, Debug, Clone)]
119pub(crate) enum Indexes {
120    Explicit(Vec<usize>),
121    Range(std::ops::Range<usize>),
122}
123
124impl Default for Indexes {
125    fn default() -> Self {
126        Indexes::Range(0..0)
127    }
128}
129impl Indexes {
130    pub fn push(&mut self, index: usize) {
131        match self {
132            Indexes::Explicit(v) => {
133                if let Some(last) = v.last() {
134                    assert!(*last <= index);
135                }
136                v.push(index);
137            }
138            Indexes::Range(r) => {
139                if r.end == index {
140                    r.end = index + 1;
141                } else {
142                    let mut v: Vec<usize> = r.collect();
143                    v.push(index);
144                    *self = Indexes::Explicit(v);
145                }
146            }
147        }
148    }
149
150    fn range(&self) -> std::ops::Range<usize> {
151        match self {
152            Indexes::Range(r) => r.clone(),
153            _ => std::ops::Range {
154                start: 0 as usize,
155                end: 0 as usize,
156            },
157        }
158    }
159
160    // The one user for this method is test code but it would be a
161    // pain to extract it to live with the rest of the test code.
162    #[allow(dead_code)]
163    pub fn iter(&self) -> impl Iterator<Item = usize> + '_ {
164        self.range().chain(match self {
165            Indexes::Range(_) => EMPTY_VEC.iter().copied(),
166            Indexes::Explicit(v) => v.iter().copied(),
167        })
168    }
169
170    pub fn into_iter(self) -> impl Iterator<Item = usize> {
171        self.range().chain(match self {
172            Indexes::Range(_) => vec![].into_iter(),
173            Indexes::Explicit(v) => v.into_iter(),
174        })
175    }
176
177    #[cfg(feature = "parallel")]
178    pub fn into_par_iter(self) -> impl rayon::iter::IndexedParallelIterator<Item = usize> {
179        self.range().into_par_iter().chain(match self {
180            Indexes::Range(_) => vec![].into_par_iter(),
181            Indexes::Explicit(v) => v.into_par_iter(),
182        })
183    }
184
185    pub fn get(&self, index: usize) -> usize {
186        match self {
187            Indexes::Range(r) => index + r.start,
188            Indexes::Explicit(v) => v[index],
189        }
190    }
191
192    #[cfg(feature = "parallel")]
193    pub fn add_offset(&mut self, offset: usize) {
194        let new = match self {
195            Indexes::Range(r) => Indexes::Range(if r.start == r.end {
196                r.clone()
197            } else {
198                std::ops::Range {
199                    start: r.start + offset,
200                    end: r.end + offset,
201                }
202            }),
203            Indexes::Explicit(v) => {
204                Indexes::Explicit(v.iter().map(|value| value + offset).collect())
205            }
206        };
207        *self = new;
208    }
209
210    pub fn canonicalize(&mut self) {
211        if let Indexes::Explicit(v) = self {
212            if v.is_empty() {
213                *self = Indexes::Range(0..0);
214            } else {
215                let is_contiguous = v.windows(2).all(|slice| (slice[1] - slice[0]) == 1);
216                if is_contiguous {
217                    *self = Indexes::Range(v[0]..(v[v.len() - 1] + 1));
218                }
219            }
220        }
221    }
222
223    pub fn merge(mut self, mut other: Indexes) -> Indexes {
224        // This is more complicated than it should be because rayon's
225        // reduce makes no guarantees about order.
226
227        fn is_empty(r: &std::ops::Range<usize>) -> bool {
228            // not in stable yet, sigh
229            r.start == r.end
230        }
231
232        fn join_ranges(a: std::ops::Range<usize>, b: std::ops::Range<usize>) -> Indexes {
233            if is_empty(&a) {
234                return Indexes::Range(b);
235            };
236            if is_empty(&b) {
237                return Indexes::Range(a);
238            };
239
240            if a.end == b.start {
241                Indexes::Range(a.start..b.end)
242            } else if b.end == a.start {
243                Indexes::Range(b.start..a.end)
244            } else {
245                let (a, b) = if a.end < b.start { (a, b) } else { (b, a) };
246                Indexes::Explicit(a.chain(b).collect())
247            }
248        }
249
250        fn join_vec(mut a: Vec<usize>, mut b: Vec<usize>) -> Indexes {
251            if a.is_empty() {
252                return Indexes::Explicit(b);
253            }
254            if b.is_empty() {
255                return Indexes::Explicit(a);
256            }
257
258            Indexes::Explicit(if a[0] <= b[0] {
259                a.append(&mut b);
260                a
261            } else {
262                b.append(&mut a);
263                b
264            })
265        }
266
267        fn join_range_vec(a: std::ops::Range<usize>, b: Vec<usize>) -> Indexes {
268            if b.is_empty() {
269                // Do b first because if they're both empty, we prefer
270                // a Range representation.
271                return Indexes::Range(a);
272            }
273            if is_empty(&a) {
274                return Indexes::Explicit(b);
275            }
276
277            Indexes::Explicit(if a.end <= b[0] {
278                a.chain(b.into_iter()).collect()
279            } else {
280                b.into_iter().chain(a).collect()
281            })
282        }
283
284        self.canonicalize();
285        other.canonicalize();
286        let mut res = match (self, other) {
287            (Indexes::Range(a), Indexes::Range(b)) => join_ranges(a, b),
288            (Indexes::Range(a), Indexes::Explicit(b)) => join_range_vec(a, b),
289            (Indexes::Explicit(a), Indexes::Range(b)) => join_range_vec(b, a),
290            (Indexes::Explicit(a), Indexes::Explicit(b)) => join_vec(a, b),
291        };
292        res.canonicalize();
293        res
294    }
295}
296
297#[derive(Default, PartialEq, Debug, Clone)]
298pub(crate) struct SplitGeoIndexes {
299    pub points: Indexes,
300    pub lines: Indexes,
301    pub polys: Indexes,
302    pub line_strings: Indexes,
303    pub rects: Indexes,
304    pub tris: Indexes,
305}
306
307#[derive(Default, PartialEq, Debug, Clone)]
308pub struct SplitGeoSeq {
309    pub(crate) geos: SplitGeo,
310    pub(crate) indexes: SplitGeoIndexes,
311}
312
313#[derive(Clone, Copy, Debug)]
314pub struct ProxMapRow {
315    pub big_index: usize,
316    pub small_index: usize,
317    pub distance: f64,
318}
319
320impl Eq for ProxMapRow {}
321
322impl PartialEq for ProxMapRow {
323    fn eq(&self, other: &Self) -> bool {
324        (self.big_index, self.small_index) == (other.big_index, other.small_index)
325    }
326}
327
328impl PartialOrd for ProxMapRow {
329    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
330        Some(self.cmp(other))
331    }
332}
333
334impl Ord for ProxMapRow {
335    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
336        (self.big_index, self.small_index).cmp(&(other.big_index, other.small_index))
337    }
338}
339
340#[derive(Clone, Debug)]
341pub struct ProxMapGeoRow {
342    pub big_index: usize,
343    pub small_index: usize,
344    pub big: Geometry<f64>,
345    pub small: Geometry<f64>,
346    pub distance: f64,
347}
348
349impl Eq for ProxMapGeoRow {}
350
351impl PartialEq for ProxMapGeoRow {
352    fn eq(&self, other: &Self) -> bool {
353        (self.big_index, self.small_index) == (other.big_index, other.small_index)
354    }
355}
356
357impl PartialOrd for ProxMapGeoRow {
358    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
359        Some(self.cmp(other))
360    }
361}
362
363impl Ord for ProxMapGeoRow {
364    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
365        (self.big_index, self.small_index).cmp(&(other.big_index, other.small_index))
366    }
367}
368
369#[derive(Clone, Copy, PartialEq, Eq, Debug, PartialOrd, Ord)]
370pub struct SJoinRow {
371    pub big_index: usize,
372    pub small_index: usize,
373}
374
375#[derive(Clone, Debug)]
376pub struct SJoinGeoRow {
377    pub big_index: usize,
378    pub small_index: usize,
379    pub big: Geometry<f64>,
380    pub small: Geometry<f64>,
381}
382
383impl Eq for SJoinGeoRow {}
384
385impl PartialEq for SJoinGeoRow {
386    fn eq(&self, other: &Self) -> bool {
387        (self.big_index, self.small_index) == (other.big_index, other.small_index)
388    }
389}
390
391impl PartialOrd for SJoinGeoRow {
392    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
393        Some(self.cmp(other))
394    }
395}
396
397impl Ord for SJoinGeoRow {
398    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
399        (self.big_index, self.small_index).cmp(&(other.big_index, other.small_index))
400    }
401}
spatial_join/structs.rs

spatial_join/
structs.rs
