i_triangle 0.45.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
103
104

use core::cmp::Ordering;
use i_overlay::i_float::int::number::int::IntNumber;
use i_overlay::i_float::int::number::wide_int::WideIntNumber;
use i_overlay::i_float::int::point::IntPoint;
use i_overlay::i_float::int::vector::IntVector as FixVec;

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

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

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

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

        let bp = p - self.b;
        let b_cross = bp.cross_product(self.bc);
        if b_cross >= I::Wide::ZERO {
            return false;
        }

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

        c_cross < I::Wide::ZERO
    }

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

        let bp = p - self.b;
        let b_cross = bp.cross_product(self.bc);
        if b_cross >= I::Wide::ZERO {
            return ABCExcludeResult::Outside;
        }

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

        match c_cross.cmp(&I::Wide::ZERO) {
            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<I: IntNumber>(a: IntPoint<I>, b: IntPoint<I>, p: IntPoint<I>) -> bool {
        // a, b, p already on one line
        // not including ends
        let ap = a - p;
        let bp = b - p;

        // must have opposite direction
        ap.dot_product(bp) < I::Wide::ZERO
    }
}