i_triangle 0.42.0

Polygon Triangulation Library: Efficient Delaunay Triangulation for Complex Shapes.
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
102

use core::cmp::Ordering;
use i_overlay::i_float::fix_vec::FixVec;
use i_overlay::i_float::int::point::IntPoint;

#[derive(PartialEq, Eq)]
pub(super) enum ABCExcludeResult {
    Inside,
    Outside,
    OutsideEdge,
}

// a, b, c - counter clock wised points
pub(super) struct Abc {
    a: IntPoint,
    b: IntPoint,
    c: IntPoint,
    ab: FixVec,
    bc: FixVec,
    ca: FixVec,
}

impl Abc {
    #[inline(always)]
    pub(super) fn new(a: IntPoint, b: IntPoint, c: IntPoint) -> Self {
        let ab = b.subtract(a);
        let bc = c.subtract(b);
        let ca = a.subtract(c);
        Self {
            a,
            b,
            c,
            ab,
            bc,
            ca,
        }
    }

    #[inline(always)]
    pub(super) fn contains(&self, p: IntPoint) -> bool {
        let ap = p.subtract(self.a);
        let a_cross = ap.cross_product(self.ab);
        if a_cross >= 0 {
            return false;
        }

        let bp = p.subtract(self.b);
        let b_cross = bp.cross_product(self.bc);
        if b_cross >= 0 {
            return false;
        }

        let cp = p.subtract(self.c);
        let c_cross = cp.cross_product(self.ca);

        c_cross < 0
    }

    #[inline(always)]
    pub(super) fn contains_exclude_ca(&self, p: IntPoint) -> ABCExcludeResult {
        let ap = p.subtract(self.a);
        let a_cross = ap.cross_product(self.ab);
        if a_cross >= 0 {
            return ABCExcludeResult::Outside;
        }

        let bp = p.subtract(self.b);
        let b_cross = bp.cross_product(self.bc);
        if b_cross >= 0 {
            return ABCExcludeResult::Outside;
        }

        let cp = p.subtract(self.c);
        let c_cross = cp.cross_product(self.ca);

        match c_cross.cmp(&0) {
            Ordering::Less => ABCExcludeResult::Inside,
            Ordering::Equal => {
                if AB::contains(self.a, self.c, p) {
                    ABCExcludeResult::Inside
                } else {
                    ABCExcludeResult::OutsideEdge
                }
            }
            Ordering::Greater => ABCExcludeResult::OutsideEdge,
        }
    }
}

pub(super) struct AB;

impl AB {
    #[inline(always)]
    pub(super) fn contains(a: IntPoint, b: IntPoint, p: IntPoint) -> bool {
        // a, b, p already on one line
        // not including ends
        let ap = a.subtract(p);
        let bp = b.subtract(p);

        // must have opposite direction
        ap.dot_product(bp) < 0
    }
}