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

问题描述

我正在制作一个简单的游戏并偶然发现了这个问题.假设二维空间中有几个点.我想要的是让彼此靠近的点以某种方式进行交互.

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 <来消除明显的点.半径并且如果 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屋！