我正在制作一个简单的游戏，并且偶然发现了这个问题。假设2D空间中有几个点。我想要的是让点彼此靠近以某种方式相互作用。找到另一点的某个半径内的所有点
让我扔的图片在这里为更好地理解这一问题： 
现在，问题不是关于计算距离。我知道该怎么做。
起初我有大约10分，我可以简单地检查每一个组合，但正如你可以假设的那样，随着积分数量的增加，这是非常低效的。如果我总共有一百万分，但所有这些分数彼此之间会很疏远呢？
我试图找到一个合适的数据结构或一种方法来看待这个问题，所以每个点只能介意他们的周围而不是整个空间。有没有已知的算法？我不完全知道如何命名这个问题，所以我可以谷歌到我想要的。
如果你不知道这种已知的algorighm，所有的想法都非常受欢迎。
你还是得通过每个环节的重复，但有两个优化，可以执行：
1）您可以通过检查X1 <半径，如果消除明显的要点y1 <半径（就像布伦特已经在另一个答案中提到的那样）。
2）不计算距离，您可以计算距离的平方并将其与允许半径的平方进行比较。这样可以避免执行昂贵的平方根计算。
这可能是您要获得的最佳表现。
我认为我可以通过保持2堆来非常好地利用优化编号1：一个按'x'排序，另一个按'y'协调排序。当分数移动时，heapsort调用应该非常便宜，因为这些协调只会在每次迭代时略微改变。在玩完这一点之后，我会回来的（没有电影引用的意图）。 – Saraph
如果您可以通过x和y值对这些点进行排序，那么您可以快速选出位于中心点框内的那些点（二进制搜索？）：x + - r，y + - 河一旦你有了这个点的子集，那么你可以使用距离公式来看它们是否在半径范围内。
实际上，这种方法可能有效......但如果这个盒子里有一百万分之多呢？您将使用距离公式检查的点数最小化，但运行时没有保证范围或改进 – adao7000
我不认为有任何方法可以对保存每个点的二维点进行排序靠近邻居。例如，如果你按x排序然后用y排序，你可能会得到一个类似'[（0,0），（1，999），（2,0）]''的数组。 （我想你可以根据参考点的欧氏距离进行排序，但是随后你又回到了以O（n）运行时间开始的位置）。因此，您可以将搜索范围缩小到带有附近x坐标或y坐标的点，但不能同时包含这两个点。 – Kevin
@Kevin你可以有两个索引，一个用于'x'和一个用于'y'，然后找到两者的交集（就像SQL中的JOIN子句）。即使有一百万分，那也只是几兆字节的存储空间。 –
这看起来像是一个最近邻居问题。你应该使用kd树来存储点。
空间分割是你想要的.. https://en.wikipedia.org/wiki/Quadtree
这是一个range searching问题。更具体地说 - 二维圆形范围报告的问题。
从"Solving Query-Retrieval Problems by Compacting Voronoi Diagrams" [Aggarwal, Hansen, Leighton, 1990]报价：
- 输入：在欧几里得平面E 2的n个点A组的P
- 查询：查找包含在E 2盘与P的所有点半径r以q为中心。
最好的结果在"Optimal Halfspace Range Reporting in Three Dimensions" [Afshani, Chan, 2009]获得。他们的方法需要O（n）空间数据结构，它支持O（log n + k）最差情况下的查询。该结构可以通过在O（n log n）期望时间内运行的随机算法进行预处理。 （n是输入点的数量，k是输出点的数量）。
CGAL库支持循环范围搜索查询。见here。
我不知道如果是最好的主意，但它总比没有好。将二维空间存储在此结构中：array（array（bool）），如果有一个点，则为true;如果没有，则为false。因此，当你想在半径内找到点时，你不必评估整个矩阵，只需评估半径范围内的位置 –
https://en.wikipedia.org/wiki/K-d_tree – amit
@pablito。这实际上是我的第一个想法之一。仍然不太喜欢检查你周围的每个像素的想法。 – Saraph