1

我有一个 2D 表面（ Grid ），在不同位置有 50 个元素。我需要确定最接近给定点的 10 个元素。

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

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

谢谢。

4

2 回答 2

1

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

当您计算 10 个最近点时，还要存储它们相对于您当前位置的角度方向。然后，当你移动时，你可以计算你移动的方向。将您的搜索重点放在对您开放的空间上（想想围绕 A 点的一个圆圈和围绕 B 点的另一个圆圈。B 中的空间而不是 A 中的空间是您想要集中搜索的地方）。

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

于 2010-01-10T08:42:10.973 回答
0

所以，我将把所有的尝试都放在我的实现上，希望你能找到适合你项目的最佳方法。

我正在从事与您提到的有点相似的项目。但在我的情况下，一旦我找到给定距离阈值内的点，我需要做额外的循环。我尝试了几次迭代，首先我从创建距离网格开始。请记住，我不是在 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 名成员。

希望这会有所帮助，祝你好运。

于 2009-11-08T17:04:03.813 回答