我有一个问题，我需要一种非常有效的方法来查找给定体积内的对象。可以想象，对象被表示为具有 X-min、Y-min、Z-min 和 X-max、Y-max、Z-max 值的框。太空中可能有数百万个这样的对象，问题是在任意给定的用户提供的体积内找到对象。用户输入框的 X、Y 和 Z 值的最小值、最大值。
目前，我在 Oracle 数据库表中拥有所有这些对象，这些对象为 X、Y 和 Z 值的范围索引。任何查找对象的查询都涉及将给定的 X、Y 和 Z 值与对象值的比较。我发现性能并不令人满意，并且正在考虑使用内存算法来解决这个问题。此外，还需要找到完全进入、部分进入的对象。
谢谢艾
有一种相对快速的方法可以确定您的轴对齐边界框是否在指定的边界体积之内、部分之内或之外。基本上，您可以为绑定比较的值分配一个位掩码，并通过对位掩码进行与运算来确定边界框的交集。这正是你想要的，而且是一种非常有效的方法；我记得很多年前看过它（说真的，就像 15 年前一样）；当我找到它时，我会发布有关该方法的参考和更多数据。
更新：好的，我认为我记得的原始方法不适用于这种精确的情况，但这有一个相对快速的解决方案。以单维情况为例（您可以从中概括其他维度），如果该维度中框的两个点都小于框最小值或它们都大于框，则您希望对象被取消资格最大限度。对每个维度重复，这会给你你想要的。
不是一个非常优雅的解决方案，但我希望它是有效的。
它有一个需要一些时间的初始化部分，但它应该得到回报，查询有望很快。
首先创建一个空间划分数据结构，通过它可以在被查询的容器中搜索点，这样就可以找到框了。
这将是一棵树，每个节点有 8 个子节点。还有其他的选择，看看kd trees
找到包含所有盒子的最小封闭容器。
将此容器分成 8 个大小相同的容器。
对于集合中的每个点，找到它所属的容器。
对其中包含多个点的每个容器重复此过程。
您最终会得到具有单点的叶容器。
使用这种结构说你想在一个被查询的容器中找到所有的点。
从树的顶部开始，遍历所有与被查询容器相交的分支/容器。
将有 3 种情况：
1) 一个容器完全封闭在被查询的容器内 => 这个子树中的所有点都在被查询的容器中。
2）一个容器在查询的容器之外=>你不遍历它。（这是你应该获得效率的地方）
3）一个容器与查询的容器相交=>你必须为它的所有孩子重复这个过程。
您必须弄清楚一些边缘情况。
要找到这些框，您必须将它们的 8 个角中的每一个都放入该数据结构中。
角落应该链接回盒子。所以当你找到一个角落时，你就会知道它属于哪个盒子。
要查找哪些盒子完全包含在查询的容器中，您必须测试每个找到的盒子