i_triangle 0.44.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
105
106
107
108

use alloc::vec::Vec;
use i_overlay::i_float::float::compatible::FloatPointCompatible;
use i_overlay::i_float::float::number::FloatNumber;
use i_overlay::{i_float::adapter::FloatPointAdapter, i_shape::float::adapter::PathToInt};

use crate::int::locator::IntPointInTriangulationLocator;
use crate::{
    float::triangulation::Triangulation, int::triangulation::IndexType,
    location::PointLocationInTriangulation,
};

pub trait PointInTriangulationLocator<P> {
    fn locate_points<T>(&self, points: &[P]) -> Vec<PointLocationInTriangulation>
    where
        P: FloatPointCompatible<Scalar = T>,
        T: FloatNumber;
}

impl<P, I: IndexType> Triangulation<P, I> {
    pub fn locate_points<T: FloatNumber>(&self, points: &[P]) -> Vec<PointLocationInTriangulation>
    where
        P: FloatPointCompatible<Scalar = T>,
    {
        let adapter = FloatPointAdapter::with_iter(self.points.iter().chain(points.iter()));

        let int_points = points.to_int(&adapter);

        let triangles = self.indices.chunks_exact(3).map(|triangle| {
            let a = adapter.float_to_int(&self.points[triangle[0].into_usize()]);
            let b = adapter.float_to_int(&self.points[triangle[1].into_usize()]);
            let c = adapter.float_to_int(&self.points[triangle[2].into_usize()]);
            [a, b, c]
        });

        triangles.locate_points(&int_points)
    }
}

impl<P, I: IndexType> PointInTriangulationLocator<P> for Triangulation<P, I> {
    #[inline]
    fn locate_points<T>(&self, points: &[P]) -> Vec<PointLocationInTriangulation>
    where
        P: FloatPointCompatible<Scalar = T>,
        T: FloatNumber,
    {
        Triangulation::locate_points::<T>(self, points)
    }
}

#[cfg(test)]
mod tests {
    use alloc::vec;

    use crate::{
        float::triangulation::Triangulation,
        location::{PointLocationInTriangulation, TriangleIndex},
    };

    fn square_triangulation() -> Triangulation<[f64; 2], u16> {
        Triangulation {
            points: vec![[0.0, 0.0], [4.0, 0.0], [4.0, 4.0], [0.0, 4.0]],
            indices: vec![0, 1, 2, 0, 2, 3],
        }
    }

    #[test]
    fn test_locate_points() {
        let triangulation = square_triangulation();
        let points_to_locate = vec![
            [3.0, 1.0],
            [1.0, 3.0],
            [2.0, 2.0],
            [2.0, 0.0],
            [0.0, 0.0],
            [5.0, 1.0],
        ];

        let locations = triangulation.locate_points::<f64>(&points_to_locate);

        assert!(matches!(
            locations[0],
            PointLocationInTriangulation::InsideTriangle(t) if t == TriangleIndex::new(0)
        ));
        assert!(matches!(
            locations[1],
            PointLocationInTriangulation::InsideTriangle(t) if t == TriangleIndex::new(1)
        ));
        assert!(matches!(
            locations[2],
            PointLocationInTriangulation::OnInteriorEdge(a, b)
                if a == TriangleIndex::new(0) && b == TriangleIndex::new(1)
        ));
        assert!(matches!(
            locations[3],
            PointLocationInTriangulation::OnExteriorEdge(t)
                if t == TriangleIndex::new(0)
        ));
        assert!(matches!(
            &locations[4],
            PointLocationInTriangulation::OnVertex(triangles)
                if triangles.as_slice() == [TriangleIndex::new(0), TriangleIndex::new(1)]
        ));
        assert!(matches!(
            locations[5],
            PointLocationInTriangulation::Outside
        ));
    }
}