体积内的对象
我有一个问题，我需要一种非常有效的方法来查找给定体积内的对象。人们可以想象，对象被表示为具有 X-min、Y-min、Z-min 和 X-max、Y-max、Z-max 值的框。太空中可能有数百万个这样的物体，问题是在任意给定的用户提供的体积内找到这些物体。用户输入框的 X、Y 和 Z 值的最小值、最大值。
目前，我在 Oracle 数据库表中拥有所有这些对象，这些对象是针对 X、Y 和 Z 值进行范围索引的。任何要查找对象的查询都会涉及给定 X、Y 和 & 的比较。 Z 值与对象值的 Z 值。我发现性能并不令人满意，并考虑使用内存算法来解决这个问题。此外，还需要找到完全进入、部分进入的对象。
谢谢 埃伊
I have a problem, that I need a very efficient way of finding objects inside a given volume. One can imagine, that the objects are represented as boxes with a X-min, Y-min, Z-min and X-max, Y-max, Z-max values. There can be millions of such objects in space, and the problem is to find the objects inside an arbitrarily given user supplied volume. The user inputs min,max of the X,Y and Z values of the box.
Currently, I have all those objects in an Oracle Database table which are range indexed for X, Y, and Z values. Any query, to find the objects then involves comparison of the given X,Y, & Z values with that of the objects values. I find the performance is not satisfactory, and thinking of an in-memory algorithm to solve this. Also, required is to find the objects that are fully-in, partially-in.
Thanks
Ey
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
有一种相对快速的方法可以确定轴对齐的边界框是否落在指定的边界体积内、部分落在指定的边界体积内或不在指定的边界体积内。基本上，您可以为绑定比较的值分配一个位掩码，并通过对位掩码进行“与”操作来确定边界框的交集。这正是你想要的，而且是一种非常有效的方法；我记得很多年前看过它（说真的，大概是 15 年前）；当我找到它时，我会发布有关该方法的参考和更多数据。
更新：好吧，我认为我记得的原始方法并不适合这种精确的情况，但这有一个相对快速的解决方案。以单维情况为例（您可以从中推广其他维度），如果该维度中盒子的两个点都小于盒子最小值或都大于盒子，则您希望该对象被取消资格最大限度。对每个维度重复此操作，即可得到您想要的结果。
There's a relatively rapid way of finding whether your axis-aligned bounding boxes fall within, partially within, or without the specified bounding volume. Basically, you can assign a bitmask for values of bound comparison, and determine the intersection of the bounding boxes by ANDing the bitmasks. It's precisely what you want, and it's a very efficient method; I remember seeing it many years ago (seriously, like 15 years ago); I'll post the reference and more data about the method when I find it.
Update: Okay, I think the original method I remembered wasn't for this precise situation, but this has a relatively quick solution. Taking the single-dimensional case (from which you can generalize the other dimensions), you want the object to be disqualified if both the points of the box in that dimension are less than the box min or if they're both greater than the box max. Repeat for each of the dimensions, and that'll give you what you want.
这不是一个非常优雅的解决方案，但我希望它是有效的。
它有一个初始化部分，需要一些时间，但之后应该会得到回报，查询速度有望很快。
首先创建一个空间分区数据结构，用它可以在查询的容器中搜索点，这样就可以找到盒子。
它将是一棵每个节点有 8 个子节点的树。还有其他替代方案，请查看 kd 树
找到包含所有内容的最小封闭容器盒子。
将此容器分成 8 个大小相等的容器。
对于集合中的每个点，找到它所属的容器。
对其中包含多个点的每个容器重复此过程。
您最终会得到具有单个点的叶容器。
使用此结构假设您想要查找查询容器中的所有点。
从树的顶部开始，遍历与查询的容器相交的所有分支/容器。
会有3种情况：
1) 一个容器完全封闭在所查询的容器内 =>该子树中的所有点都在查询的容器中。
2) 一个容器在查询的容器之外 =>你不遍历它。 （这是你应该获得效率的地方）
3) 一个容器与被查询的容器相交 =>您必须对其所有子项重复此过程。
您必须弄清楚一些边缘情况。
要找到盒子，您必须将它们的 8 个角分别放入该数据结构中。
角落应该链接回盒子。因此，当您找到一个角落时，您就会知道它属于哪个盒子。
要查找哪些盒子完全封闭在所查询的容器中，您必须测试每个找到的盒子
Not a very elegant solutions, but I hope it is efficient.
It has an initialization part that will take some time, but then it should pay off, the queries will hopefully be fast.
First create a space partitioning data structure, with which you can search for points in a queried container, you'll be able to find the boxes this way.
It will be a tree with 8 children per node. There are other alternatives, take a look at k-d trees
Find the smallest enclosing container that contains all the boxes.
Divide this container in 8 equally sized containers.
For each point in your set find the container that it belongs to.
Repeat this process for each container that has more than one point in it.
You'll end up with the leaf containers having a single point.
Using this structure say you want to find all the points in a queried container.
Start from top of the tree and traverse all branches/containers that intersect with the queried container.
There will be 3 cases:
1) a container is completely enclosed within the queried container => all the points in this sub-tree are in the queried container.
2) a container is outside the queried container => you don't traverse it. (this is where you should get the efficiency)
3) a container is intersecting the queried container => you'll have to repeat the process for all it's children.
There are some edge cases you'll have to figure out.
To find the boxes you'll have to put each of their 8 corners in that data structure.
The corners should link back to the boxes. So when you find a corner you'll know which box it belongs to.
To find which boxes are completely enclosed in the queried container you have to test each one of the found boxes