geometry_rs/
lib.rs

1#![doc = include_str!("../README.md")]
2
3mod next_after;
4
5use crate::next_after::NextAfter;
6
7#[derive(Copy, Clone, Debug)]
8pub struct Point {
9    pub x: f64,
10    pub y: f64,
11}
12
13#[derive(Copy, Clone, Debug)]
14pub struct Rect {
15    pub min: Point,
16    pub max: Point,
17}
18
19impl Rect {
20    pub fn contains_point(&self, p: Point) -> bool {
21        return p.x >= self.min.x && p.x <= self.max.x && p.y >= self.min.y && p.y <= self.max.y;
22    }
23
24    pub fn intersects_rect(&self, other: Rect) -> bool {
25        if self.min.y > other.max.y || self.max.y < other.min.y {
26            return false;
27        }
28        if self.min.x > other.max.x || self.max.x < other.min.x {
29            return false;
30        }
31        return true;
32    }
33
34    pub fn nw(&self) -> Point {
35        Point {
36            x: self.min.x,
37            y: self.max.y,
38        }
39    }
40
41    pub fn sw(&self) -> Point {
42        Point {
43            x: self.min.x,
44            y: self.min.y,
45        }
46    }
47
48    pub fn se(&self) -> Point {
49        Point {
50            x: self.max.x,
51            y: self.min.y,
52        }
53    }
54
55    pub fn ne(&self) -> Point {
56        Point {
57            x: self.max.x,
58            y: self.max.y,
59        }
60    }
61
62    pub fn south(&self) -> Segment {
63        Segment {
64            a: self.sw(),
65            b: self.se(),
66        }
67    }
68
69    pub fn east(&self) -> Segment {
70        Segment {
71            a: self.se(),
72            b: self.ne(),
73        }
74    }
75
76    pub fn north(&self) -> Segment {
77        Segment {
78            a: self.ne(),
79            b: self.nw(),
80        }
81    }
82
83    pub fn west(&self) -> Segment {
84        Segment {
85            a: self.nw(),
86            b: self.sw(),
87        }
88    }
89
90    pub fn segment_at(&self, index: i64) -> Segment {
91        match index {
92            0 => return self.south(),
93            1 => return self.east(),
94            2 => return self.north(),
95            3 => return self.west(),
96            _ => return self.south(), // TODO(ringsaturn): raise err
97        }
98    }
99}
100
101fn segment_at_for_vec_point(exterior: &Vec<Point>, index: i64) -> Segment {
102    let seg_a: Point = exterior[index as usize];
103    let mut seg_b_index = index;
104    if seg_b_index == (exterior.len() - 1) as i64 {
105        seg_b_index = 0
106    } else {
107        seg_b_index += 1
108    }
109    let seg_b: Point = exterior[seg_b_index as usize];
110    return Segment { a: seg_a, b: seg_b };
111}
112
113fn rings_contains_point(ring: &Vec<Point>, point: Point, allow_on_edge: bool) -> bool {
114    let rect = Rect {
115        min: Point {
116            x: std::f64::NEG_INFINITY,
117            y: point.y,
118        },
119        max: Point {
120            x: std::f64::INFINITY,
121            y: point.y,
122        },
123    };
124    let mut inside: bool = false;
125    let n: i64 = (ring.len() - 1) as i64;
126    for i in 0..n {
127        let seg: Segment = segment_at_for_vec_point(&ring, i);
128
129        if seg.rect().intersects_rect(rect) {
130            let res: RaycastResult = raycast(&seg, point);
131            // print!("res= inside:{:?} on:{:?}\n", res.inside, res.on);
132            if res.on {
133                inside = allow_on_edge;
134                break;
135            }
136            if res.inside {
137                inside = !inside;
138            }
139        }
140    }
141    return inside;
142}
143
144pub struct Polygon {
145    pub exterior: Vec<Point>,
146    pub holes: Vec<Vec<Point>>,
147    pub rect: Rect,
148}
149
150impl Polygon {
151    /// Point-In-Polygon check, the normal way.
152    /// It's most used algorithm implementation, port from Go's [geojson]
153    ///
154    /// [geojson]: https://github.com/tidwall/geojson
155    fn contains_point_normal(&self, p: Point) -> bool {
156        if !rings_contains_point(&self.exterior, p, false) {
157            return false;
158        }
159        let mut contains: bool = true;
160        for hole in self.holes.iter() {
161            if rings_contains_point(&hole, p, false) {
162                contains = false;
163                break;
164            }
165        }
166        return contains;
167    }
168
169    /// Do point-in-polygon search.
170    pub fn contains_point(&self, p: Point) -> bool {
171        if !self.rect.contains_point(p) {
172            return false;
173        }
174
175        return self.contains_point_normal(p);
176    }
177
178    /// Create a new Polygon instance from exterior and holes.
179    ///
180    /// Example:
181    ///
182    /// ```rust
183    /// use std::vec;
184    /// use geometry_rs;
185    /// let poly = geometry_rs::Polygon::new(
186    ///     vec![
187    ///         geometry_rs::Point {
188    ///             x: 90.48826291293898,
189    ///             y: 45.951129815858565,
190    ///         },
191    ///         geometry_rs::Point {
192    ///             x: 90.48826291293898,
193    ///             y: 27.99437617512571,
194    ///         },
195    ///         geometry_rs::Point {
196    ///             x: 122.83201291294,
197    ///             y: 27.99437617512571,
198    ///         },
199    ///         geometry_rs::Point {
200    ///             x: 122.83201291294,
201    ///             y: 45.951129815858565,
202    ///         },
203    ///         geometry_rs::Point {
204    ///             x: 90.48826291293898,
205    ///             y: 45.951129815858565,
206    ///         },
207    ///     ],
208    ///     vec![],
209    /// );
210    ///
211    /// let p_out = geometry_rs::Point {
212    ///     x: 130.74216916294148,
213    ///     y: 37.649011392900306,
214    /// };
215    ///
216    /// print!("{:?}\n", poly.contains_point(p_out));
217    ///
218    /// let p_in = geometry_rs::Point {
219    ///     x: 99.9804504129416,
220    ///     y: 39.70716466970461,
221    /// };
222    /// print!("{:?}\n", poly.contains_point(p_in));
223    /// ```
224    pub fn new(exterior: Vec<Point>, holes: Vec<Vec<Point>>) -> Polygon {
225        return Polygon::default_new(exterior, holes);
226    }
227
228    fn default_new(exterior: Vec<Point>, holes: Vec<Vec<Point>>) -> Polygon {
229        let mut minx: f64 = exterior.get(0).unwrap().x;
230        let mut miny: f64 = exterior.get(0).unwrap().y;
231        let mut maxx: f64 = exterior.get(0).unwrap().x;
232        let mut maxy: f64 = exterior.get(0).unwrap().y;
233
234        // for p in exterior.iter() {
235        for i in 0..exterior.len() - 1 {
236            let p = exterior[i];
237            if p.x < minx {
238                minx = p.x;
239            }
240            if p.y < miny {
241                miny = p.y;
242            }
243            if p.x > maxx {
244                maxx = p.x;
245            }
246            if p.y > maxy {
247                maxy = p.y;
248            }
249        }
250
251        let rect = Rect {
252            min: Point { x: minx, y: miny },
253            max: Point { x: maxx, y: maxy },
254        };
255
256        return Polygon {
257            exterior,
258            holes,
259            rect,
260        };
261    }
262}
263
264#[derive(Copy, Clone, Debug)]
265pub struct Segment {
266    pub a: Point,
267    pub b: Point,
268}
269
270impl Segment {
271    pub fn rect(&self) -> Rect {
272        let mut min_x: f64 = self.a.x;
273        let mut min_y: f64 = self.a.y;
274        let mut max_x: f64 = self.b.x;
275        let mut max_y: f64 = self.b.y;
276
277        if min_x > max_x {
278            let actual_min_x = max_x;
279            let actual_max_x = min_x;
280            min_x = actual_min_x;
281            max_x = actual_max_x;
282        }
283
284        if min_y > max_y {
285            let actual_min_y = max_y;
286            let actual_max_y = min_y;
287            min_y = actual_min_y;
288            max_y = actual_max_y;
289        }
290
291        return Rect {
292            min: Point { x: min_x, y: min_y },
293            max: Point { x: max_x, y: max_y },
294        };
295    }
296}
297
298pub struct RaycastResult {
299    inside: bool, // point on the left
300    on: bool,     // point is directly on top of
301}
302
303pub fn raycast(seg: &Segment, point: Point) -> RaycastResult {
304    let mut p = point;
305    let a = seg.a;
306    let b = seg.b;
307
308    // make sure that the point is inside the segment bounds
309    if a.y < b.y && (p.y < a.y || p.y > b.y) {
310        return RaycastResult {
311            inside: false,
312            on: false,
313        };
314    } else if a.y > b.y && (p.y < b.y || p.y > a.y) {
315        return RaycastResult {
316            inside: false,
317            on: false,
318        };
319    }
320
321    // test if point is in on the segment
322    if a.y == b.y {
323        if a.x == b.x {
324            if p.x == a.x && p.y == a.y {
325                return RaycastResult {
326                    inside: false,
327                    on: true,
328                };
329            }
330            return RaycastResult {
331                inside: false,
332                on: false,
333            };
334        }
335        if p.y == b.y {
336            // horizontal segment
337            // check if the point in on the line
338            if a.x < b.x {
339                if p.x >= a.x && p.x <= b.x {
340                    return RaycastResult {
341                        inside: false,
342                        on: true,
343                    };
344                }
345            } else {
346                if p.x >= b.x && p.x <= a.x {
347                    return RaycastResult {
348                        inside: false,
349                        on: true,
350                    };
351                }
352            }
353        }
354    }
355    if a.x == b.x && p.x == b.x {
356        // vertical segment
357        // check if the point in on the line
358        if a.y < b.y {
359            if p.y >= a.y && p.y <= b.y {
360                return RaycastResult {
361                    inside: false,
362                    on: true,
363                };
364            }
365        } else {
366            if p.y >= b.y && p.y <= a.y {
367                return RaycastResult {
368                    inside: false,
369                    on: true,
370                };
371            }
372        }
373    }
374    if (p.x - a.x) / (b.x - a.x) == (p.y - a.y) / (b.y - a.y) {
375        return RaycastResult {
376            inside: false,
377            on: true,
378        };
379    }
380
381    // do the actual raycast here.
382    while p.y == a.y || p.y == b.y {
383        // p.y = NextAfter(p.y, &std::f64::INFINITY)
384        // let next = big_num.next_after(&std::f64::INFINITY);
385        p.y = p.y.next_after(std::f64::INFINITY);
386    }
387
388    if a.y < b.y {
389        if p.y < a.y || p.y > b.y {
390            return RaycastResult {
391                inside: false,
392                on: false,
393            };
394        }
395    } else {
396        if p.y < b.y || p.y > a.y {
397            return RaycastResult {
398                inside: false,
399                on: false,
400            };
401        }
402    }
403    if a.x > b.x {
404        if p.x >= a.x {
405            return RaycastResult {
406                inside: false,
407                on: false,
408            };
409        }
410        if p.x <= b.x {
411            return RaycastResult {
412                inside: true,
413                on: false,
414            };
415        }
416    } else {
417        if p.x >= b.x {
418            return RaycastResult {
419                inside: false,
420                on: false,
421            };
422        }
423        if p.x <= a.x {
424            return RaycastResult {
425                inside: true,
426                on: false,
427            };
428        }
429    }
430    if a.y < b.y {
431        if (p.y - a.y) / (p.x - a.x) >= (b.y - a.y) / (b.x - a.x) {
432            return RaycastResult {
433                inside: true,
434                on: false,
435            };
436        }
437    } else {
438        if (p.y - b.y) / (p.x - b.x) >= (a.y - b.y) / (a.x - b.x) {
439            return RaycastResult {
440                inside: true,
441                on: false,
442            };
443        }
444    }
445    return RaycastResult {
446        inside: false,
447        on: false,
448    };
449}
geometry_rs/lib.rs

geometry_rs/
lib.rs
