geometry_rs/
lib.rs

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

geometry_rs/
lib.rs
