我的数学很糟糕，但我有一种情况需要在 3D 空间中找到所有点，这些点任意接近通过同一空间投影的 vector 。这些点可以以算法要求的任何方式存储，但我想不出任何对它们特别有利的排序。
这个专长是否有任何现有的 C++ 算法？如果是(或不是)，它包含或将包含什么样的数学概念，因为我很想尝试理解它并将我的大脑绑在椒盐脆饼上。
( 这个算法会在一个大概有 100,000 个点的空间上运行，它需要测试大约 1,000,000 个 vector ，并且需要在 1/30 秒内完成这些 vector 。我当然怀疑是否有任何算法可以执行此壮举，但看看这是不是真的很有趣。)
最佳答案
您可能希望将您的点存储在某种空间数据结构中。想到的是:
它们的属性略有不同。八叉树将整个世界分成 8 个大小相同的立方体，这些立方体组织起来形成一个更大的立方体。然后将这些立方体中的每一个依次分成 8 个大小均匀的立方体。您不断拆分立方体，直到立方体中的点数少于一定数量。使用这种树结构，您可以很容易地遍历树，提取所有可能与给定立方体相交的点。一旦你有了这个点列表，你就可以一次一个地测试它们。由于您的测试几何体是一个球体(与一个点的距离)，您将围绕球体外接一个立方体并获得可能与其相交的点。作为一种优化，您还可以在您的圈子中插入一个立方体，并且任何肯定与它相交的东西，您都可以立即简单地包含在您的命中集中。
BSP 树是一棵二进制空间划分树。它是 3 维空间中的一棵平面树，形成一棵二叉树。使用它来解决你的问题的主要问题是你可能需要在遍历它时做很多平方根，才能找到到平面的距离。不过原理是一样的，一旦你的点数少于一定数量，你就会用这些点形成一片叶子。 BSP 树中的所有叶子都是凸多边形(沿着周边的叶子除外，它们将是无限大的多边形)。在构建 BSP 时，您希望将每一步的点分成两半，以真正获得 O(log n) 搜索。
kd-tree 是 BSP 的一个特例，其中所有平面都是轴对齐的。这通常会显着加快针对它们的测试速度，但也不允许您根据您的点集优化平面。
我不知道有任何 C++ 库实现了这些，但我确信有很多。这些是视频游戏中使用的相当普遍的技术，因此您可能想看看游戏引擎。
关于c++ - 在 3D 空间中搜索靠近 vector 的点，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7136581/