找到另一个点的某个半径内的所有点

Question

我正在做一个简单的游戏,偶然发现了这个问题.假设2D空间中的几个点.我想要的是让彼此接近的点以某种方式相互作用.

让我在这里画一张照片,以便更好地理解这个问题:

现在,问题不在于计算距离.我知道该怎么做.

起初我有大约10分,我可以简单地检查每个组合,但正如你已经可以假设的那样,随着点数的增加,这是非常低效的.如果我总共有一百万分,但是所有这些分数彼此相距很远怎么办？

我正试图找到一个合适的数据结构或一种方法来看待这个问题,所以每个点都只能考虑周围而不是整个空间.有没有任何已知的算法？我不知道如何命名这个问题所以我可以谷歌正是我想要的.

如果你不知道这种已知的算法,那么所有的想法都是非常受欢迎的.

Answer 1

这是一个范围搜索问题.更具体地说 - 2-d圆形范围报告问题.

引自"通过压缩Voronoi图解决查询 - 检索问题"[Aggarwal,Hansen,Leighton,1990]:

• 输入:欧几里德平面E²中的n个点的集合P.
• 查询:查找E²中磁盘中包含的P的所有点,半径r以q为中心.

最佳结果来自"三维最佳半空间范围报告"[Afshani,Chan,2009].他们的方法需要O(n)空间数据结构,该结构支持O(log n + k)最坏情况时间的查询.该结构可以通过在O(n log n)预期时间内运行的随机算法进行预处理.(n是输入点的数量,以及输出点数量中的k).

CGAL库支持循环范围搜索查询.看到这里.

Answer 2

您仍然需要遍历每个点,但您可以执行两个优化:

1)你可以通过检查x1 <radius和y1 <radius是否消除了明显的点(就像在另一个答案中已经提到的布伦特一样).

2)您可以计算距离的平方,并将其与允许半径的平方进行比较,而不是计算距离.这样可以避免执行昂贵的平方根计算.

这可能是你将获得的最佳表现.