0

ポイントの最小距離フィルターを作成します。この関数は、ポイント (x1、y1、x2、y2...) のストリームを取り、対応するものを削除します。

void minDistanceFilter(vector<float> &points, float distance = 0.0)
{
    float p0x, p0y;
    float dx, dy, dsq;
    float mdsq = distance*distance; // minimum distance square

    unsigned i, j, n = points.size();

    for(i=0; i<n; ++i)
    {
        p0x = points[i];
        p0y = points[i+1];

        for(j=0; j<n; j+=2)
        {
            //if (i == j) continue; // discard itself (seems like it slows down the algorithm)

            dx = p0x - points[j];   // delta x (p0x - p1x)
            dy = p0y - points[j+1]; // delta y (p0y - p1y)

            dsq = dx*dx + dy*dy; // distance square

            if (dsq < mdsq)
            {
                auto del = points.begin() + j;
                points.erase(del,del+3);
                n = points.size(); // update n
                j -= 2; // decrement j
            }
        }
    }
}

すべてのポイント (n^2) に対してすべてのポイントをテストするため、非常に遅い唯一の問題です。

どうすれば改善できますか？

4

2 に答える 2

2

en.wikipedia.org/wiki/Range_tree などの範囲ツリーを検索します。この構造を使用して 2 次元の点を格納し、クエリの四角形内にあるすべての点を非常に迅速に見つけることができます。ポイント（a、b）から特定の距離d内のポイントを見つけたいので、クエリの長​​方形は[ad、a + d] x [bd、b + d]である必要があり、内部で見つかったポイントをテストしますそれらが実際に (a,b) の距離 d 内にあることを確認するための四角形。範囲ツリーは O(n log n) 時間と空間で構築でき、範囲クエリは O(log n + k) 時間かかります。ここで、k は四角形で見つかったポイントの数です。あなたの問題に最適なようです。

于 2013-07-20T22:26:49.527 に答える
2

kd-trees または range trees を問題に使用できます。ただし、ゼロからコーディングして、より単純なものが必要な場合は、ハッシュ テーブル構造を使用できます。各ポイント (a,b) について、キー (round(a/d),round(b/d)) を使用してハッシュし、同じキーを持つすべてのポイントをリストに格納します。次に、ハッシュ テーブルの各キー (m,n) について、リスト内のすべてのポイントを、(m',n') の 9 つの選択肢すべてについてキー (m',n') を持つポイントのリストと比較します。 ' = m + (-1 または 0 または 1) および n' = n + (-1 または 0 または 1)。これらは、キー (m,n) を持つポイントの距離 d 内にある唯一のポイントです。kd ツリーまたは範囲ツリーと比較した場合の欠点は、特定の点について、辺の長さが 3*d の正方形内で距離 d 以下の点を効果的に検索していることです。辺の長さが 2*d の正方形内を検索する代わりに、kd ツリーまたは範囲ツリーを使用した場合に得られるものです。ただし、ゼロからコーディングする場合は、コーディングが簡単です。また、kd-trees と range trees は、すべての点について気にかけている普遍的な距離 d が 1 つしかない場合、ちょっとやり過ぎです。

于 2013-07-20T22:57:01.057 に答える