在一个立方体盒子里,我有一个很大的 R^3 集合点。我想找到每个点的 k 个最近邻。通常我会考虑使用 k-d 树之类的东西,但在这种情况下我有周期性边界条件。据我了解,k-d 树的工作原理是将空间切割成一维较少的超平面,即在 3D 中,我们将通过绘制 2D 平面来分割空间。对于任何给定的点,它要么在平面上,要么在平面上,要么在平面下。然而,当您使用周期性边界条件分割空间时,可以认为一个点位于任一侧!
在 R^3 中查找和维护具有周期性边界条件的最近邻居列表的最有效方法是什么?
近似值是不够的,并且一次只能移动一个点(认为蒙特卡罗而不是 N 体模拟)。
即使在欧几里得的情况下,一个点和它最近的邻居也可能位于超平面的相对两侧。 k-d 树中最近邻搜索的核心是确定点与框之间距离的原语;您的情况唯一需要的修改是考虑回绕的可能性。
或者,您可以实现适用于任何指标的覆盖树。
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)