polygon2 0.3.0

polygon 2d functions
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101

use core::ops::{Add, Div, Mul, Neg, Sub};
use num_traits::Signed;

#[inline]
pub fn contains_point<T>(points: &[[T; 2]], p: &[T; 2]) -> bool
where
    T: Clone + Signed + PartialOrd,
    for<'a, 'b> &'a T: Div<&'b T, Output = T>
        + Sub<&'b T, Output = T>
        + Add<&'b T, Output = T>
        + Mul<&'b T, Output = T>
        + Neg<Output = T>,
{
    let n = points.len();
    let px = &p[0];
    let py = &p[1];

    let a = points[n - 1].clone();
    let mut b = points[n - 2].clone();
    let mut ax;
    let mut ay = &a[1] - &py;
    let mut bx = &b[0] - &px;
    let mut by = &b[1] - &py;

    let mut lup = &by > &ay;
    for i in 0..n {
        // ax = bx;
        ay = by;
        b = points[i].clone();
        bx = &b[0] - &px;
        by = &b[1] - &py;

        if ay == by {
            continue;
        }
        lup = by > ay;
    }

    let mut depth = 0;
    for i in 0..n {
        ax = bx;
        ay = by;
        let b = &points[i];
        bx = &b[0] - &px;
        by = &b[1] - &py;

        if &ay < &T::zero() && &by < &T::zero() {
            // both "up" or both "down"
            continue;
        }
        if &ay > &T::zero() && &by > &T::zero() {
            // both "up" or both "down"
            continue;
        }
        if &ax < &T::zero() && &bx < &T::zero() {
            // both points on the left
            continue;
        }

        if &ay == &by && (if &ax < &bx {
            ax.clone()
        } else {
            bx.clone()
        }) <= T::zero()
        {
            return true;
        }
        if &ay == &by {
            continue;
        }

        let lx = &ax + &(&(&(&bx - &ax) * &-&ay) / &(&by - &ay));
        if &lx == &T::zero() {
            // point on edge
            return true;
        }
        if &lx > &T::zero() {
            depth += 1;
        }
        if &ay == &T::zero() && lup && &by > &ay {
            // hit vertex, both up
            depth -= 1;
        }
        if &ay == &T::zero() && !lup && &by < &ay {
            // hit vertex, both down
            depth -= 1;
        }

        lup = &by > &ay;
    }

    return (depth & 1) == 1;
}

#[test]
fn test_contains_point() {
    let points = [[1, -1], [1, 1], [-1, 1], [-1, -1]];
    assert!(contains_point(&points, &[0, 0]));
    assert!(contains_point(&points, &[1, 0]));
    assert!(!contains_point(&points, &[2, 0]));
}