在另一个点的一定半径内找到所有点 [英] Finding all points in certain radius of another point

问题描述

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

I am making a simple game and stumbled upon this problem. Assume several points in 2D space. What I want is to make points close to each other interact in some way.

为了更好地理解问题，让我在这里拍张照片:

Let me throw a picture here for better understanding of the problem:

现在，问题与计算距离无关.我知道该怎么做.

Now, the problem isn't about computing the distance. I know how to do that.

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

At first I had around 10 points and I could simply check every combination, but as you can already assume, this is extremely inefficient with increasing number of points. What if I had a million of points in total, but all of them would be very distant to each other?

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

I'm trying to find a suitable data structure or a way to look at this problem, so every point can only mind their surrounding and not whole space. Are there any known algorithms for this? I don't exactly know how to name this problem so I can google exactly what I want.

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

If you don't know of such known algorighm, all ideas are very welcome.

推荐答案

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

You're still going to have to iterate through every point, but there are two optimizations you can perform:

1)您可以通过检查x1< 1来消除明显的点.半径，如果y1<半径(就像布伦特在另一个答案中已经提到的).

1) You can eliminate obvious points by checking if x1 < radius and if y1 < radius (like Brent already mentioned in another answer).

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

2) Instead of calculating the distance, you can calculate the square of the distance and compare it to the square of the allowed radius. This saves you from performing expensive square root calculations.

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

This is probably the best performance you're gonna get.

这篇关于在另一个点的一定半径内找到所有点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！