动态最近元素

发布于 2024-08-10 05:54:49 字数 148 浏览 4 评论 0原文

我有一个 2D 表面(网格),在不同位置有 50 个元素。 我需要确定距离给定点最近的 10 个元素。

此外,给定点不断移动,我需要对每次移动进行计算。

我知道我可以计算每个动作到每个点的欧几里德距离,但我想要一种更快的方法。

谢谢。

I have a 2D surface ( Grid ) with 50 elements at different locations.
I need to decide which are the 10 closest elements to a given point.

In addition, the given point is constantly moving and i need to do the calculation on each movement.

I know I can calculate the Euclidean distance to each point on each movement, but I want a faster way.

Thanks.

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

挽容 2024-08-17 05:54:49

听起来您正在尝试想出一种方法,可以在时间 t 处获取 10 个最近的点,并使用这些点来帮助您找出在时间 t+1 处最接近的 10 个点。这是一个需要考虑的想法。

当您计算 10 个最近的点时,还要存储它们相对于您当前位置的角度方向。然后,当您移动时,您可以计算出您移动的方向。将搜索集中在向您开放的空间上(想象一下围绕 A 点的一个圆,另一个围绕 B 点的圆。B 中但不是 A 中的空间是您要集中搜索的位置)。

当然,要做到这一点,您需要有某种方法在网格的特定区域中进行搜索,而不是通过点数组进行线性搜索来查找靠近您的点。我建议为此研究 BSP 树。如果您还没有这样做,那么使用 BSP 树而不是线性搜索可能就是您所寻求的性能提升。

It sounds like you're trying to come up with a way where you can take the 10 closest points at time t and use those to help you figure out the 10 closest at time t+1. Here's an idea to consider.

When you calculate the 10 closest points, also store the angular direction of where they are relative to your current location. Then, when you move you can calculate the direction in which you moved. Focus your search on the space that's opened up to you (think of a circle around point A and another around point B. The space in B but not in A is where you want to focus your search).

Of course, to do this you need to have some way of searching in a particular area of the grid instead of doing a linear search through an array of points to find those close to you. I'd recommend looking into BSP trees for that. If you're not doing it already, using BSP trees instead of linear search might alone be the performance boost you're looking for.

私野 2024-08-17 05:54:49

因此,我将进行所有尝试来找出我的实现,希望您能够找到适合您项目的最佳方法。

我正在从事与您提到的有些类似的项目。但就我而言,一旦找到给定距离阈值内的点,我就需要进行额外的循环。我尝试了几次迭代,首先我从创建距离网格开始。请记住,我不是在 2D 表面上工作,但我认为将其更改为 2D 不需要太多工作。

这是我开发距离网格的方法(它是如此简单,即使是穴居人也能做到,我取笑自己),还要记住我没有继续使用网格来完成我的实现。

public double[][] distanceGrid() {
    double[] gridSize = combineArrays(generateClusters(1, 3), generateClusters(12, 15));
    double [][] pointsDistanceGrid = new double[gridSize.length][gridSize.length];
    for (int i = 0; i < pointsDistanceGrid.length; i++) {
        for (int j = 0; j < pointsDistanceGrid[i].length; j++) {
            pointsDistanceGrid[i][j] = Math.abs(gridSize[i] - gridSize[j] );
            System.out.print(" " + pointsDistanceGrid[i][j]);
        }
        System.out.println("");
    }

    return pointsDistanceGrid;
}

正如我提到的,我没有使用它。

由于我必须处理距离阈值,并且我决定在找到“最近的”之前我想查看与我正在查看的特定点更接近的所有点,因此我实现了此方法。

/**
 * Given a point method returns an array with point that are within the limit of threshold.
 * @param point
 * @return
 */
public double[] pointsWithinThreshold(double point) {
    double[] neighbors = new double[bigCluster.length];
    for (int i = 0; i < bigCluster.length; i++) {
        if (bigCluster[i] != point) {
            double distance = 0;
            distance = Math.abs(point - bigCluster[i]);
            if (distance <= getDistanceThreshold()) {
                neighbors[i] = bigCluster[i];
            }
        }
    }
    return neighbors;
}

在此之后,我意识到我并不真正关心所有最近的点是什么,所以我最终不使用这个并将其中一些功能折射到一个方法中,在该方法中我获得最接近的成员并执行递归DFS。

如果您想查看,请告诉我,我没有把它放在这里,因为我认为您只需要知道最近的 10 个成员。

希望这有帮助,祝你好运。

So, I am going to put all the attempts that I went over to figure out my implementation and hopefully you will be able to figure out the best approach for you project.

I am working on somewhat similar project to what you have mentioned. But in my case I need to do extra cycles once I found the points within a given distance threshold. I have tried few iterations, first I started by creating a distance grid. Keep in mind, I am not working on 2D surface but I don't think changing this to 2D will take much work.

Here is how I developed my distance grid (its so simple even a cave man can do it, I making fun of myself) , Also keep in mind I didn't continue using the grid to finish up my implementation.

public double[][] distanceGrid() {
    double[] gridSize = combineArrays(generateClusters(1, 3), generateClusters(12, 15));
    double [][] pointsDistanceGrid = new double[gridSize.length][gridSize.length];
    for (int i = 0; i < pointsDistanceGrid.length; i++) {
        for (int j = 0; j < pointsDistanceGrid[i].length; j++) {
            pointsDistanceGrid[i][j] = Math.abs(gridSize[i] - gridSize[j] );
            System.out.print(" " + pointsDistanceGrid[i][j]);
        }
        System.out.println("");
    }

    return pointsDistanceGrid;
}

As I mentioned I didn't use it.

Since I had to deal with a distance threshold, and I decided before finding "The Nearest" i wanted to see all the points that are closer to the particular point that I am looking at, so I implemented this method.

/**
 * Given a point method returns an array with point that are within the limit of threshold.
 * @param point
 * @return
 */
public double[] pointsWithinThreshold(double point) {
    double[] neighbors = new double[bigCluster.length];
    for (int i = 0; i < bigCluster.length; i++) {
        if (bigCluster[i] != point) {
            double distance = 0;
            distance = Math.abs(point - bigCluster[i]);
            if (distance <= getDistanceThreshold()) {
                neighbors[i] = bigCluster[i];
            }
        }
    }
    return neighbors;
}

After this I realize I don't really care what are all the closest points so I end up not using this and refractor some of this functionalities to a method where I get the closest member and do recursive DFS.

Let me know if you would like to see that, I didn't put it here coz I thought you only need to know the closest 10 member.

Hope this helps and good luck.

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文