查找另一个点的特定半径内的所有点
Finding all points in certain radius of another point
我正在制作一个简单的游戏并偶然发现了这个问题。假设 2D space 中的几个点。我想要的是让彼此接近的点以某种方式相互作用。
为了更好地理解问题，我在这里放一张图：
现在，问题不在于计算距离。我知道怎么做。
起初我有大约 10 个点，我可以简单地检查每个组合，但正如您已经假设的那样，随着点数的增加，这是非常低效的。如果我总共有 100 万个点，但它们之间的距离会很远怎么办？
我正在尝试寻找合适的数据结构或方法来看待这个问题，所以每个点都只能关注周围而不是整体space。有没有已知的算法？我不知道如何命名这个问题，所以我可以 google 正是我想要的。
如果你不知道这样的已知算法，欢迎大家提出想法。
如果您可以让这些点按 x 和 y 值排序，那么您可以快速挑选出中心点框内的那些点（二进制搜索？）：x +- r, y + - 河一旦你有了点的子集，你就可以使用距离公式来查看它们是否在半径内。
这看起来像是最近邻问题。您应该使用 kd 树来存储点。
您仍然需要遍历每个点，但是您可以执行两个优化：
1) 您可以通过检查 x1 < radius 和 y1 < radius 来消除明显的点（就像另一个答案中已经提到的 Brent）。
2) 可以不计算距离，而是计算距离的平方并将其与允许半径的平方进行比较。这使您免于执行昂贵的平方根计算。
这可能是您将获得的最佳性能。
Space分区就是你想要的..https://en.wikipedia.org/wiki/Quadtree
这是一个range searching问题。更具体地说 - 二维循环范围报告问题。
引用自"Solving Query-Retrieval Problems by Compacting Voronoi Diagrams" [Aggarwal, Hansen, Leighton, 1990]：
- Input: A set P of n points in the Euclidean plane E²
- Query: Find all points of P contained in a disk in E² with radius r centered at q.
最好的结果出现在"Optimal Halfspace Range Reporting in Three Dimensions" [Afshani, Chan, 2009]。他们的方法需要 O(n) space 支持 O(log n + k) 最坏情况时间查询的数据结构。该结构可以通过在 O(n log n) 预期时间内运行的随机算法进行预处理。 （n为输入点数，k为输出点数）
CGAL 库支持循环范围搜索查询。参见 here。
我假设您有最小和最大 X 和 Y 坐标？如果是这样怎么样。
称我们的半径为 R，Xmax-Xmin X，Ymax-Ymin Y。
具有 [X/R、Y/R] 的 double-linked 列表的二维矩阵。将每个点结构放在正确的 linked 列表中。
要找到你需要与之交互的点，你只需要检查你的小区和你的 8 个邻居。
示例：如果 X 和 Y 各为 100，R 为 1，则在单元格 [43,77] 的 43.2、77.1 处打一个点。您将检查单元格 [42,76] [43,76] [44,76] [42,77] [43,77] [44,77] [42,78] [43,78] [44,78]对于比赛。请注意，并非您自己的框中的所有单元格都会匹配（例如 43.9、77.9 在同一个列表中但距离超过 1 个单位），并且您始终需要检查所有 8 个邻居。
随着点的移动（听起来它们会移动？），您只需取消link它们（使用 double-link 列表即可快速轻松）并重新link他们的新位置。移动任何点都是 O(1)。全部移动它们是 O(n).
如果该数组大小提供了太多单元格，您可以使用相同的算法和可能相同的代码来制作更大的单元格；只是准备好更少的候选点实际上足够接近。例如，如果 R=1 并且地图是 R 的一百万倍乘以 R 的一百万倍，那么您将无法制作那么大的二维数组。也许每个单元格的宽度为 1000 个单位更好？只要密度低，与以前相同的代码可能会起作用：只检查每个点与该单元格中的其他点以及相邻的 8 个单元格。只是为更多未能在 R 内的候选人做好准备。
如果一些单元格有很多点，每个单元格都有一个 linked 列表，也许该单元格应该有一个 red-black 由 X 坐标索引的树？即使在同一个单元格中，绝大多数其他单元格成员也会离得太远，所以只需遍历树从 X-R 到 X+R。与其遍历所有点并深入研究每个点，不如遍历树以查找 R 中的 X 坐标，然后 if/when 发现它们计算距离。当你从低 X 到高 X 遍历一个单元格的树时，你只需要在前 R 个条目中检查左边树的相邻单元格。
您也可以转到小于 R 的单元格。您将有更少的候选人不够接近。例如，对于 R/2，您将检查 25 个 link 列表而不是 9 个，但平均（如果随机分布）要检查的点数为 25/36。这可能是一个小收获。
我正在制作一个简单的游戏并偶然发现了这个问题。假设 2D space 中的几个点。我想要的是让彼此接近的点以某种方式相互作用。
为了更好地理解问题，我在这里放一张图：
现在，问题不在于计算距离。我知道怎么做。
起初我有大约 10 个点，我可以简单地检查每个组合，但正如您已经假设的那样，随着点数的增加，这是非常低效的。如果我总共有 100 万个点，但它们之间的距离会很远怎么办？
我正在尝试寻找合适的数据结构或方法来看待这个问题，所以每个点都只能关注周围而不是整体space。有没有已知的算法？我不知道如何命名这个问题，所以我可以 google 正是我想要的。
如果你不知道这样的已知算法，欢迎大家提出想法。
如果您可以让这些点按 x 和 y 值排序，那么您可以快速挑选出中心点框内的那些点（二进制搜索？）：x +- r, y + - 河一旦你有了点的子集，你就可以使用距离公式来查看它们是否在半径内。
这看起来像是最近邻问题。您应该使用 kd 树来存储点。
您仍然需要遍历每个点，但是您可以执行两个优化：
1) 您可以通过检查 x1 < radius 和 y1 < radius 来消除明显的点（就像另一个答案中已经提到的 Brent）。
2) 可以不计算距离，而是计算距离的平方并将其与允许半径的平方进行比较。这使您免于执行昂贵的平方根计算。
这可能是您将获得的最佳性能。
Space分区就是你想要的..https://en.wikipedia.org/wiki/Quadtree
这是一个range searching问题。更具体地说 - 二维循环范围报告问题。
引用自"Solving Query-Retrieval Problems by Compacting Voronoi Diagrams" [Aggarwal, Hansen, Leighton, 1990]：
- Input: A set P of n points in the Euclidean plane E²
- Query: Find all points of P contained in a disk in E² with radius r centered at q.
最好的结果出现在"Optimal Halfspace Range Reporting in Three Dimensions" [Afshani, Chan, 2009]。他们的方法需要 O(n) space 支持 O(log n + k) 最坏情况时间查询的数据结构。该结构可以通过在 O(n log n) 预期时间内运行的随机算法进行预处理。 （n为输入点数，k为输出点数）
CGAL 库支持循环范围搜索查询。参见 here。
我假设您有最小和最大 X 和 Y 坐标？如果是这样怎么样。
称我们的半径为 R，Xmax-Xmin X，Ymax-Ymin Y。
具有 [X/R、Y/R] 的 double-linked 列表的二维矩阵。将每个点结构放在正确的 linked 列表中。
要找到你需要与之交互的点，你只需要检查你的小区和你的 8 个邻居。
示例：如果 X 和 Y 各为 100，R 为 1，则在单元格 [43,77] 的 43.2、77.1 处打一个点。您将检查单元格 [42,76] [43,76] [44,76] [42,77] [43,77] [44,77] [42,78] [43,78] [44,78]对于比赛。请注意，并非您自己的框中的所有单元格都会匹配（例如 43.9、77.9 在同一个列表中但距离超过 1 个单位），并且您始终需要检查所有 8 个邻居。
随着点的移动（听起来它们会移动？），您只需取消link它们（使用 double-link 列表即可快速轻松）并重新link他们的新位置。移动任何点都是 O(1)。全部移动它们是 O(n).
如果该数组大小提供了太多单元格，您可以使用相同的算法和可能相同的代码来制作更大的单元格；只是准备好更少的候选点实际上足够接近。例如，如果 R=1 并且地图是 R 的一百万倍乘以 R 的一百万倍，那么您将无法制作那么大的二维数组。也许每个单元格的宽度为 1000 个单位更好？只要密度低，与以前相同的代码可能会起作用：只检查每个点与该单元格中的其他点以及相邻的 8 个单元格。只是为更多未能在 R 内的候选人做好准备。
如果一些单元格有很多点，每个单元格都有一个 linked 列表，也许该单元格应该有一个 red-black 由 X 坐标索引的树？即使在同一个单元格中，绝大多数其他单元格成员也会离得太远，所以只需遍历树从 X-R 到 X+R。与其遍历所有点并深入研究每个点，不如遍历树以查找 R 中的 X 坐标，然后 if/when 发现它们计算距离。当你从低 X 到高 X 遍历一个单元格的树时，你只需要在前 R 个条目中检查左边树的相邻单元格。
您也可以转到小于 R 的单元格。您将有更少的候选人不够接近。例如，对于 R/2，您将检查 25 个 link 列表而不是 9 个，但平均（如果随机分布）要检查的点数为 25/36。这可能是一个小收获。