algorithm - 查询球体表面近点的快速算法/数据结构是什么？

Question

我想要使用以下方法的数据结构:

insert :: Point3D -> a -> SphereMap a -> SphereMap a
remove :: Point3D -> a -> SphereMap a -> SphereMap a
query :: Float -> Point3D -> SphereMap a -> [a]

其中 insert 和 remove 将 3D 索引值添加到数据结构中，query 接收一个角度和一个点，并返回一个列表点相对于原点 (0,0,0) 的角距离内的所有值。

有哪些类型的数据结构可以满足此类要求？

Answer 1

通常的方法是对 2d 数据使用四叉树或对 3d 数据使用八叉树。四叉树根据 X 和 Y 阈值将关注区域分成 4 个象限。对于每个象限，如果它包含 0 个或 1 个点则结束，否则将象限分割为子象限并重复。这为您提供了一个点树，其中树的几何形状反射(reflect)了邻近的几何形状。然后，您可以编写一个算法来遍历树，找到与搜索半径相交的所有象限。 Oct-trees 在 3 个维度上是相同的，按 X、Y 和 Z 拆分。 参见 http://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space--gamedev-374了解详情。