algorithm - 检索有限范围内的 k-最近球体

Question

我想知道我是否遗漏了任何旨在检索范围内的 k 最近球体的加速结构。

我的问题的上下文是分子可视化，具体来说，我需要检索到一个点的 k 个最近的球体以生成一个函数，该函数将用于指导球体追踪 步长。为简化起见，可以将搜索范围限制在要测试的点。

我在文章中看到的所有内容都处理到一个点的 k 个最近点，但我的情况不同，因为我想使用最接近一个点的球体。似乎可以调整 kd 树，将点的测试更改为球体，但我相信这会影响性能。所以我想知道是否有更好的结构或者我是否应该使用和调整 kd-trees。

目前，我正在使用混合边界体积层次结构，但我认为使用其他结构搜索性能可能会更好，因为由于分子的性质，我有很大的边界体积重叠。

PS:我不太关心施工时间。我想要好的搜索性能和体面的内存占用。

Answer 1

您可以使用三步法:

1. 使用球体的中心点找到最近的邻居。
2. 对于这个最近的邻居，您减去它的半径并加上最大半径。然后您使用新距离执行球面范围查询。这将返回可能最接近原始球体的所有球体中心点。
3. 然后您使用每个球体的实际半径手动计算其实际距离。

假设球体的半径不会比它们的平均距离大很多，这应该是相当有效的。