查找另一个点的一定半径内的所有点

萨拉夫

我正在做一个简单的游戏,偶然发现了这个问题。假设2D空间中有几个点。我想要的是使点彼此靠近,以某种方式进行交互。

为了更好地理解该问题,请在此处输入图片: 问题的形象

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

起初,我大约有10分,我可以简单地检查每个组合,但是正如您已经可以假设的那样,随着点数的增加,这种效率极低。如果我总共有一百万个积分,但它们彼此之间相距甚远怎么办?

我正在尝试寻找合适的数据结构或解决此问题的方法,因此每个点都只能注意其周围而不是整个空间。是否有已知的算法?我不知道该如何命名这个问题,所以我可以用谷歌搜索我想要的东西。

如果您不了解这种已知的算法,那么欢迎所有想法。

adao7000

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

1)您可以通过检查x1 <半径和y1 <半径是否消除来消除明显的点(例如在另一个答案中已经提到的Brent)。

2)除了计算距离之外,您还可以计算距离的平方并将其与允许半径的平方进行比较。这样可以避免执行昂贵的平方根计算。

这可能是您将获得的最佳性能。

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

我如何计算另一个表格中的所有点赞?

如何计算一个点与另一个点有一定距离的纬度?

查找距给定点一定半径内的点的最有效方法

查找给定半径内的所有点

找出一个圆的所有点

围绕一个点绘制/绘制一个具有一定半径的圆(matplotlib)

在另一个带有点参数和默认值的函数中调用带有点参数和默认值的函数

给定点的坐标,找到彼此之间存在一定距离的所有点对?

如何找到一个数据框中每个点相对于另一个数据框中所有点的最小距离?

SQL几何查找半径中的所有点

用于检查列表中的一个项目是否在另一个项目列表中的Java方法(有点像excel中的VLOOKUP)?

Canavs并未绘制所有点。只有一个出现

查找另一个锚点的位置,而不是已经使用的锚点

所有点到第一个点的距离

创建一个没有点的元组

球上到另一个点的最近点

围绕另一个任意点旋转点

在R中,删除字符串中除最后一个点外的所有点

检查多边形点是否在传单中的另一个点内

为什么PostGIS将所有点都堆叠在一起?(使用ST_DWithin查找半径1000m以内的所有结果)

有效地找到另一个点的最近点

一定范围内所有 GPS 点的平均测量值

Pine Script 没有贯穿所有点,只有一个入口,没有出口

如果点降落到另一个点的某个邻近范围内,如何生成“排斥”点的数据?

查找矩形内所有点的快速算法

有没有比for循环和if语句更快的方法来查找python中另一个点的最近点?

确定一个半径是否在另一个半径内的公式

如何检查一个点是否在同一个圆内另一个点的公差范围内

GAE需要模型属性,如果另一个具有一定的价值?