我正在做一个简单的游戏,偶然发现了这个问题。假设2D空间中有几个点。我想要的是使点彼此靠近,以某种方式进行交互。
为了更好地理解该问题,请在此处输入图片:
现在,问题不在于计算距离。我知道该怎么做。
起初,我大约有10分,我可以简单地检查每个组合,但是正如您已经可以假设的那样,随着点数的增加,这种效率极低。如果我总共有一百万个积分,但它们彼此之间相距甚远怎么办?
我正在尝试寻找合适的数据结构或解决此问题的方法,因此每个点都只能注意其周围而不是整个空间。是否有已知的算法?我不知道该如何命名这个问题,所以我可以用谷歌搜索我想要的东西。
如果您不了解这种已知的算法,那么欢迎所有想法。
您仍然需要遍历每一个点,但是您可以执行两种优化:
1)您可以通过检查x1 <半径和y1 <半径是否消除来消除明显的点(例如在另一个答案中已经提到的Brent)。
2)除了计算距离之外,您还可以计算距离的平方并将其与允许半径的平方进行比较。这样可以避免执行昂贵的平方根计算。
这可能是您将获得的最佳性能。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句