我正在制作一个简单的游戏，遇到了这个问题。假设二维空间中有几个点。我想让彼此接近的点以某种方式进行交互。
让我放张图片在这里，更好地理解这个问题：
现在，问题不在于计算距离。我知道怎么做。
起初我有大约10个点，我可以简单地检查每个组合，但随着点数的增加，这样做效率极低。如果我总共有一百万个点，但它们都非常远离彼此呢？
我试图找到一种合适的数据结构或方法来解决这个问题，使每个点只关注它周围的区域而不是整个空间。是否有已知的算法可以解决这个问题？我不确定该如何命名这个问题，以便能够精确搜索我想要的内容。
如果您不知道这样已知的算法，欢迎提出所有想法。
这是一个范围搜索问题。更具体地说，是2D圆形区间报告问题。
引用自《通过紧缩 Voronoi 图解决查询检索问题》[Aggarwal, Hansen, Leighton, 1990]：
- 输入：欧几里得平面E²中的n个点集P
- 查询：查找所有包含q为中心，半径为r的E²中的圆盘内的P点。
在《三维空间中的最佳半空间范围报告》[Afshani, Chan, 2009]中获得了最佳结果。他们的方法需要O(n)空间数据结构，支持O(log n + k)最坏情况时间的查询。该结构可以通过运行期望时间为O(n log n)的随机算法进行预处理。(其中n是输入点数，k是输出点数）。
CGAL库支持圆形范围搜索查询。请参见此处。
x坐标排序，另一个按y坐标排序）来很好地利用优化1。当点移动时，堆排序调用应该非常便宜，因为这些坐标每次迭代只会稍微改变一点。我会玩弄一下这个想法后再回来（无意引用电影台词）。 - Saraph空间划分是你想要的... https://zh.wikipedia.org/wiki/四叉树
如果您可以按x和y值对这些点进行排序，那么您可以快速挑选出那些在中心点的矩形框内的点（二分查找？）：x +- r，y +- r。一旦您拥有了这些子集点，那么您就可以使用距离公式来判断它们是否在半径范围内。
[(0,0), (1, 999), (2,0)]的数组。(我猜您可以按参考点的欧几里得距离排序，但是这样您就回到了O(n)运行时间的起点)。因此，您可以将搜索范围缩小到具有附近x坐标或y坐标的点，但不能同时具有两者。 - Kevinx，另一个用于y，然后找到两者的交集（就像SQL中的JOIN子句）。即使有一百万个点，那也只是几兆字节的存储空间。 - Brent Washburne我假设您有最小和最大的X和Y坐标？如果是这样，那么怎么样呢。
将我们的半径R、Xmax-Xmin X和Ymax-Ymin Y称为二维矩阵[X/R，Y/R]的双向链表。将每个点结构放在正确的链接列表上。
要查找需要交互的点，您只需要检查您的单元格以及您的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个邻居。
当点移动时（听起来它们会移动？），您只需取消链接它们（使用双链接列表快速轻松）并在其新位置重新链接。移动任何一个点的时间复杂度为O(1)。将它们全部移动的时间复杂度为O(n)。
如果该数组大小给出了太多单元格，您可以使用相同的算法和可能相同的代码制作更大的单元格；只需准备好实际上靠近的候选点较少即可。例如，如果R=1且地图是百万倍的R乘以百万倍的R，则无法制作如此大的2D数组。最好让每个单元格宽1000个单位？只要密度低，之前的代码应该仍然适用：仅针对此单元格及其相邻的8个单元格中的其他点检查每个点。只需准备好更多的候选点未能在R内。
如果某些单元格将有很多点，每个单元格都有一个链接列表，也许该单元格应该有一个由X坐标索引的红黑树？即使在同一个单元格中，绝大多数其他单元格成员也会离得太远，因此只需从X-R到X+R遍历树。与其循环遍历所有点并深入每个点的树中，不妨通过迭代树来寻找R内的X坐标，如果/当您找到它们时计算距离。当您从低到高X遍历一个单元格的树时，在前R个条目中，您只需要检查左侧单元格的相邻树。