1

私は、C++ で 2 次元 kd ツリー構築アルゴリズムを実装する個人プロジェクトに取り組んでいます。
すでにこれを行っているライブラリがあることは知っていますが、C++ プログラミングの経験を積みたいです
(示す個人的なプロジェクトがある場合は、履歴書に役立ちます)。

入力: ポイントの数、およびポイント自体 (入力はコマンド ラインから読み取ることができます)

これを O(n log n) 時間で実行したいのですが、実行できますか? そうであれば、誰かが私を始めるのに役立つ疑似コードを提供してくれませんか? 事前に感謝します。

4

1 に答える 1

2

最近、kd-trees をいじっています。ここにいくつかの未テストのコードがあります。kd ツリーの構築は 2 段階で行われます。ポイントのリスト O(n) をトラバースし、各次元に沿ってソート O(nlogn)。したがって、はい、O(nlogn) 時間で kd ツリーを構築できます。

ただし、ツリーを検索する (最近傍を探しているとします) のは、よりトリッキーになります。そのためのわかりやすいドキュメントは見つかりませんでした。

struct Node
{
    int[2] point;
    Node* left;
    Node* right;
}

Node* createtreeRecursive (int** values /* int[2][len] */, int len, int dim = 2, int depth = 0)
{
    // If empty, return
    if (value <= 1) return null;

    // Get axis to split along
    int axis = depth % dim;

    int** sorted = sortAlongDim (values, axis);

    int mid = len / 2;
    Node* curr = new Node ();
    curr.point[0] = sorted [0][mid];
    curr.point[1] = sorted [1][mid];

    int** leftHalf = values;
    int** rightHalf = &(values [mid]);

    curr.left = createtreeRecursive (leftHalf, mid, dim, depth + 1);
    curr.right = createtreeRecursive (rightHalf, len - mid, dim, depth + 1);

    return curr;
}

int** sortAlongDim (int** values, int axis)
于 2010-11-24T06:58:08.433 に答える