packed_spatial_index 0.21.1

Packed static spatial index (Hilbert R-tree) for 2D/3D AABBs — SIMD range, kNN, raycast, and spatial-join queries, with zero-copy and streaming serialization.
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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129

//! A 2D convex polygon query region (the half-plane generalization of
//! [`Triangle2D`](crate::Triangle2D)): N vertices, exact box-vs-polygon SAT.

use crate::geometry::{Box2D, Overlaps2D};

/// A convex polygon in 2D, given as vertices in order (CW or CCW). The query
/// predicates assume convexity; a non-convex polygon yields unspecified results.
#[derive(Clone, Debug, PartialEq)]
pub struct ConvexPolygon2D {
    verts: Vec<[f64; 2]>,
}

impl ConvexPolygon2D {
    /// Build from vertices in boundary order (CW or CCW).
    pub fn new(verts: Vec<[f64; 2]>) -> Self {
        Self { verts }
    }

    /// The vertices.
    pub fn vertices(&self) -> &[[f64; 2]] {
        &self.verts
    }

    /// Twice the signed area (shoelace); zero ⇒ degenerate (collinear/empty).
    fn signed_area2(&self) -> f64 {
        let v = &self.verts;
        let mut a = 0.0;
        for i in 0..v.len() {
            let p = v[i];
            let q = v[(i + 1) % v.len()];
            a += p[0] * q[1] - q[0] * p[1];
        }
        a
    }

    /// Whether this polygon's filled area overlaps the axis-aligned box `bx`
    /// (exact separating-axis test: the box's two axes plus each edge normal).
    pub fn overlaps_box(&self, bx: Box2D) -> bool {
        let v = &self.verts;
        if v.len() < 3 {
            return false;
        }
        // Box axes.
        let (mut lox, mut hix) = (f64::INFINITY, f64::NEG_INFINITY);
        let (mut loy, mut hiy) = (f64::INFINITY, f64::NEG_INFINITY);
        for w in v {
            lox = lox.min(w[0]);
            hix = hix.max(w[0]);
            loy = loy.min(w[1]);
            hiy = hiy.max(w[1]);
        }
        if hix < bx.min_x || lox > bx.max_x || hiy < bx.min_y || loy > bx.max_y {
            return false;
        }
        // Polygon edge normals.
        let corners = [
            [bx.min_x, bx.min_y],
            [bx.max_x, bx.min_y],
            [bx.min_x, bx.max_y],
            [bx.max_x, bx.max_y],
        ];
        for i in 0..v.len() {
            let p = v[i];
            let q = v[(i + 1) % v.len()];
            let (ax, ay) = (-(q[1] - p[1]), q[0] - p[0]);
            let mut tlo = f64::INFINITY;
            let mut thi = f64::NEG_INFINITY;
            for w in v {
                let d = w[0] * ax + w[1] * ay;
                tlo = tlo.min(d);
                thi = thi.max(d);
            }
            let mut blo = f64::INFINITY;
            let mut bhi = f64::NEG_INFINITY;
            for c in &corners {
                let d = c[0] * ax + c[1] * ay;
                blo = blo.min(d);
                bhi = bhi.max(d);
            }
            if thi < blo || tlo > bhi {
                return false;
            }
        }
        true
    }

    /// Whether the box `bx` lies entirely inside the polygon (all four corners
    /// inside). Always `false` for a degenerate (zero-area) polygon.
    pub fn contains_box(&self, bx: Box2D) -> bool {
        if self.verts.len() < 3 || self.signed_area2() == 0.0 {
            return false;
        }
        self.contains_point([bx.min_x, bx.min_y])
            && self.contains_point([bx.max_x, bx.min_y])
            && self.contains_point([bx.min_x, bx.max_y])
            && self.contains_point([bx.max_x, bx.max_y])
    }

    fn contains_point(&self, p: [f64; 2]) -> bool {
        let v = &self.verts;
        let (mut has_neg, mut has_pos) = (false, false);
        for i in 0..v.len() {
            let a = v[i];
            let b = v[(i + 1) % v.len()];
            let cross = (b[0] - a[0]) * (p[1] - a[1]) - (b[1] - a[1]) * (p[0] - a[0]);
            if cross < 0.0 {
                has_neg = true;
            } else if cross > 0.0 {
                has_pos = true;
            }
            if has_neg && has_pos {
                return false;
            }
        }
        true
    }
}

impl Overlaps2D for ConvexPolygon2D {
    #[inline]
    fn overlaps_box(&self, bx: Box2D) -> bool {
        self.overlaps_box(bx)
    }

    #[inline]
    fn contains_box(&self, bx: Box2D) -> bool {
        self.contains_box(bx)
    }
}