3D区间KD树

• 下载源代码 - 3.44 KB

引言

一个用于轻松存储3D轴对齐边界盒的C# KD-树。KD-树 是一种高效的方法，用于在3D空间中查找边界框，相比于遍历所有边界框并评估它们与搜索体积的相交情况。附件下载中包含两个文件。一个包含实现，另一个包含单元测试用例。您可以直接将它们复制到您的项目中。 

背景

似乎缺乏针对C#的简单开源KD-树实现。此KD-树实现是为元宇宙交换协议（MXP）参考实现而创建的。您可以在http://www.bubblecloud.org/的源代码部分找到改进版本。

使用代码

KD-树的使用方式与字典类似。

IntervalKDTree<string> tree = 
  new IntervalKDTree<string>(100, 10);

IList<TestBox> testBoxes = new List<TestBox>();
for (double i = -100; i < 100; i += 0.3)
{
    TestBox box = new TestBox();
    box.minX = i;
    box.minY = i;
    box.minZ = i;
    box.maxX = i + 1;
    box.maxY = i + 2;
    box.maxZ = i + 3;
    box.value = "test" + i;
    testBoxes.Add(box);
    tree.Put(box.minX, box.minY, box.minZ, box.maxX, 
             box.maxY, box.maxZ, box.value);
}

HashSet<string> foundValues;
foundValues = tree.GetValues(-10, -10, -10, 10, 10, 10, 
              new HashSet<string>());

关注点

KD-树似乎可以用相对较少的代码实现。请通过提供错误修复和改进建议来帮助我进一步改进它。也欢迎提交补丁。

历史

初始版本和单元测试用例于2009年5月底实现。