空间划分

Rust 中的空间划分算法。一个正在进行中的项目。

实现的算法

四叉树

将 2D 空间划分为四个段的树。交集测试仅使用轴对齐的边界框实现。目前该树仅使用 i32 类型以加快交集测试；因此需要适当的预缩放浮点数据。

示例展示了使用 f32 实现的 2D 射线与盒子的测试。它可以启动使用

$ cargo run --release --example quadtree

区间树

参见维基百科上的 区间树。

$ cargo run --example interval_tree

使用示例

use space_partitioning::interval_tree::{IntervalTree, Interval, IntervalType};

#[derive(Debug, PartialOrd, PartialEq, Copy, Clone, Default)]
struct Vec2d {
    pub x: f64,
    pub y: f64,
}

impl IntervalType for Vec2d {}

fn main() {
    let tree = IntervalTree::from_iter([
        (
            Interval::new(Vec2d { x: 1., y: 2. }, Vec2d { x: 10., y: 10. }),
            "Any data (A)",
        ),
        (
            Interval::new(Vec2d { x: -5., y: -5. }, Vec2d { x: 5., y: 5. }),
            "Any data (B)",
        ),
        (
            Interval::new(Vec2d { x: -10., y: -10. }, Vec2d { x: -7., y: -7. }),
            "Any data (C)",
        ),
    ]);

    let test = Interval::new(Vec2d::default(), Vec2d::default());
    let result = tree.overlap_search(test).unwrap();

    assert_eq!(result.data, "Any data (B)")
}