问C语言中的空间数据结构

EN

如何更好地解决您的问题取决于您尚未描述的几个因素：-是否将相同的超球排列用于许多粒子碰撞计算？-超球体的大小是否一致？-粒子的运动(例如直线/曲线)是什么，该运动是否受球体的影响？-您认为粒子的体积为零吗？

我假设粒子没有简单的直线运动，因为这将是查找直线和点之间最近点的相对较快的计算，这可能与查找直线与哪个盒子相交的速度相同(以确定n-tree中的何处进行检查)。

如果您的超球体位置对于大量粒子碰撞是固定的，那么计算voronoi decomposition/Dirichlet tessellation将为您提供一种快速的方法，以便稍后准确查找空间中任何给定点的哪个球体最接近您的粒子。

然而，为了回答您最初关于八叉树/四元树/2^n-树的问题，在n维中，您可以从一个(超)-cube开始，它包含您感兴趣的空间区域。如果您认为内容太复杂，则会将其细分为2^n个超立方体。这会递归地继续下去，直到叶节点中只有简单的元素(例如，一个超球体质心)。现在已经构建了n-tree，您可以通过获取粒子的路径并将其与外部超立方体相交来将其用于碰撞检测。交集位置将告诉您下一层树中的哪个超立方体要访问，您可以确定与该级别的所有2^n个超立方体的交集位置，向下直到到达一个叶节点。到达叶子后，可以检查粒子路径与存储在该叶子中的超球体之间的相互作用。如果有碰撞，则已完成，否则必须从当前超立方体叶子中找到粒子路径的出口点，并确定它移动到下一个超立方体。继续，直到找到碰撞或完全离开整个边界超立方体。

在退出超立方体时有效地找到相邻的超立方体是该方法最具挑战性的部分之一。对于2^n树，可以采用Samet的方法{1，2}。对于kd树(二叉树)，在{3}第4.3.3节中建议了一种方法。

有效的实现可以像存储从每个超立方体到其子超立方体的8个指针的列表一样简单，并且如果超立方体是叶，则以特殊方式标记该超立方体(例如，使所有指针为空)。

可以在Klinger & Dyer {4}中找到划分空间以创建四元树(您可以将其推广到n-树)的描述

正如其他人提到的，kd- tree可能比2^n-tree更适合，因为扩展到任意数量的维度更直接，但是它们将导致更深的树。使用kd-tree调整分割位置以匹配超球体的几何形状也更容易。上面对2^n树中的冲突检测的描述同样适用于kd树。

{1} Connected Component Labeling, Hanan Samet, Using Quadtrees Journal of the ACM Volume 28 , Issue 3 (July 1981)

{2} Neighbor finding in images represented by octrees, Hanan Samet, Computer Vision, Graphics, and Image Processing Volume 46 , Issue 3 (June 1989)

{3} Convex hull generation, connected component labelling, and minimum distance calculation for set-theoretically defined models, Dan Pidcock, 2000

{4}使用规则分解的图片表示实验，Klinger，A.，和Dyer，C.R.E，Comptr。图形和图像处理5 (1976)，68-105。

听起来你想要实现一个kd-tree,，它可以让你更快地搜索N维空间。这里有更多信息和the Stony Brook Algorithm Repository.上的实现链接

由于您的字段是静态的(我假设您的意思是超球体不会移动)，那么我所知道的最快的解决方案是Kdtree。

你可以自己做，也可以用别人的，就像这样：http://libkdtree.alioth.debian.org/