packed_spatial_index 0.18.0

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

use crate::persistence::{ParsedTree, read_f32_le_unchecked, read_u64_le_unchecked};

pub(crate) struct F32Columns2D {
    pub(crate) node_size: usize,
    pub(crate) num_items: usize,
    pub(crate) level_bounds: Vec<usize>,
    pub(crate) min_xs: Vec<f32>,
    pub(crate) min_ys: Vec<f32>,
    pub(crate) max_xs: Vec<f32>,
    pub(crate) max_ys: Vec<f32>,
    pub(crate) indices: Vec<usize>,
}

pub(crate) struct F32Columns3D {
    pub(crate) node_size: usize,
    pub(crate) num_items: usize,
    pub(crate) level_bounds: Vec<usize>,
    pub(crate) min_xs: Vec<f32>,
    pub(crate) min_ys: Vec<f32>,
    pub(crate) min_zs: Vec<f32>,
    pub(crate) max_xs: Vec<f32>,
    pub(crate) max_ys: Vec<f32>,
    pub(crate) max_zs: Vec<f32>,
    pub(crate) indices: Vec<usize>,
}

pub(crate) struct F32ColumnRefs2D<'a> {
    pub(crate) node_size: usize,
    pub(crate) num_items: usize,
    pub(crate) min_xs: &'a [f32],
    pub(crate) min_ys: &'a [f32],
    pub(crate) max_xs: &'a [f32],
    pub(crate) max_ys: &'a [f32],
    pub(crate) indices: &'a [usize],
}

pub(crate) struct F32ColumnRefs3D<'a> {
    pub(crate) node_size: usize,
    pub(crate) num_items: usize,
    pub(crate) min_xs: &'a [f32],
    pub(crate) min_ys: &'a [f32],
    pub(crate) min_zs: &'a [f32],
    pub(crate) max_xs: &'a [f32],
    pub(crate) max_ys: &'a [f32],
    pub(crate) max_zs: &'a [f32],
    pub(crate) indices: &'a [usize],
}

/// Materialize 2D SoA f32 columns from a parsed `f32` TREE chunk.
pub(crate) fn columns2d_from_parsed(parsed: &ParsedTree) -> F32Columns2D {
    let num_nodes = parsed.num_nodes;
    let mut min_xs = Vec::with_capacity(num_nodes);
    let mut min_ys = Vec::with_capacity(num_nodes);
    let mut max_xs = Vec::with_capacity(num_nodes);
    let mut max_ys = Vec::with_capacity(num_nodes);
    let mut indices = Vec::with_capacity(num_nodes);
    for i in 0..num_nodes {
        let off = i * 16; // four f32 per 2D box record
        min_xs.push(read_f32_le_unchecked(parsed.entries, off));
        min_ys.push(read_f32_le_unchecked(parsed.entries, off + 4));
        max_xs.push(read_f32_le_unchecked(parsed.entries, off + 8));
        max_ys.push(read_f32_le_unchecked(parsed.entries, off + 12));
        indices.push(read_u64_le_unchecked(parsed.indices, i * 8) as usize);
    }
    F32Columns2D {
        node_size: parsed.node_size,
        num_items: parsed.num_items,
        level_bounds: parsed.level_bounds.clone(),
        min_xs,
        min_ys,
        max_xs,
        max_ys,
        indices,
    }
}

/// Materialize 3D SoA f32 columns from a parsed `f32` TREE chunk.
pub(crate) fn columns3d_from_parsed(parsed: &ParsedTree) -> F32Columns3D {
    let num_nodes = parsed.num_nodes;
    let mut min_xs = Vec::with_capacity(num_nodes);
    let mut min_ys = Vec::with_capacity(num_nodes);
    let mut min_zs = Vec::with_capacity(num_nodes);
    let mut max_xs = Vec::with_capacity(num_nodes);
    let mut max_ys = Vec::with_capacity(num_nodes);
    let mut max_zs = Vec::with_capacity(num_nodes);
    let mut indices = Vec::with_capacity(num_nodes);
    for i in 0..num_nodes {
        let off = i * 24; // six f32 per 3D box record
        min_xs.push(read_f32_le_unchecked(parsed.entries, off));
        min_ys.push(read_f32_le_unchecked(parsed.entries, off + 4));
        min_zs.push(read_f32_le_unchecked(parsed.entries, off + 8));
        max_xs.push(read_f32_le_unchecked(parsed.entries, off + 12));
        max_ys.push(read_f32_le_unchecked(parsed.entries, off + 16));
        max_zs.push(read_f32_le_unchecked(parsed.entries, off + 20));
        indices.push(read_u64_le_unchecked(parsed.indices, i * 8) as usize);
    }
    F32Columns3D {
        node_size: parsed.node_size,
        num_items: parsed.num_items,
        level_bounds: parsed.level_bounds.clone(),
        min_xs,
        min_ys,
        min_zs,
        max_xs,
        max_ys,
        max_zs,
        indices,
    }
}