1

異なる場所に 50 個の要素を持つ 2D サーフェス ( Grid ) があります。特定のポイントに最も近い 10 個の要素を決定する必要があります。

さらに、指定されたポイントは常に移動しており、移動ごとに計算を行う必要があります。

各動きの各ポイントまでのユークリッド距離を計算できることはわかっていますが、より高速な方法が必要です。

ありがとう。

4

2 に答える 2

1

時間tで最も近い10個のポイントを取得し、それらを使用して時間t+1で最も近い10個のポイントを見つける方法を考え出そうとしているようです。考慮すべきアイデアがあります。

最も近い10個のポイントを計算するときは、現在の場所を基準にした場所の角度方向も保存します。次に、移動するときに、移動した方向を計算できます。開いているスペースに検索の焦点を合わせます（ポイントAの周りの円とポイントBの周りの別の円を考えてください。AではなくBのスペースが、検索の焦点を合わせたい場所です）。

もちろん、これを行うには、ポイントの配列を線形検索して近くのポイントを見つけるのではなく、グリッドの特定の領域を検索する方法が必要です。そのために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 に答える