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

use alloc::vec::Vec;

use num_traits::Signed;

use super::{is_triangle_convex, point_in_triangle};

#[inline]
pub fn triangulate<T>(points: &[[T; 2]]) -> Vec<usize>
where
    T: Copy + Signed + PartialOrd,
{
    let len = points.len();
    let mut tgs = Vec::new();

    if len < 3 {
        tgs
    } else {
        let mut avl = (0..len).collect::<Vec<_>>();

        let mut i = 0;
        let mut al = len;
        while al > 3 {
            let i0 = avl[i % al];
            let i1 = avl[(i + 1) % al];
            let i2 = avl[(i + 2) % al];

            let a = &points[i0];
            let b = &points[i1];
            let c = &points[i2];

            let mut ear_found = false;
            if is_triangle_convex(a, b, c) {
                ear_found = true;

                for j in 0..al {
                    let vi = avl[j];

                    if vi != i0 && vi != i1 && vi != i2 {
                        if point_in_triangle(&points[vi], a, b, c) {
                            ear_found = false;
                            break;
                        }
                    }
                }
            }

            if ear_found {
                tgs.push(i0);
                tgs.push(i1);
                tgs.push(i2);
                avl.remove((i + 1) % al);
                al -= 1;
                i = 0;
            } else if i > 3 * al {
                break;
            } else {
                i += 1;
            }
        }

        tgs.push(avl[0]);
        tgs.push(avl[1]);
        tgs.push(avl[2]);

        tgs
    }
}

#[test]
fn test_triangulate() {
    let points = [[1, -1], [1, 1], [-1, 1], [-1, -1]];
    let tgs = triangulate(&points);
    assert_eq!(tgs, [0, 1, 2, 0, 2, 3]);
}