4

KDツリーの最近傍探索のウィキペディアページを見ています。

ウィキペディアで提供されている擬似コードは、ポイントが2-D（x、y）の場合に機能します。

ポイントが3-D（x、y、z）の場合、どのような変更を加える必要があるかを知りたいです。

私はたくさんグーグルで検索し、スタックオーバーフローで同様の質問リンクを調べましたが、3D実装は見つかりませんでした。前の質問はすべて、入力として2Dポイントを取りますが、私がいる3Dポイントではありません。探している。

KDツリーを構築するためのWikiの擬似コードは次のとおりです。

function kdtree (list of points pointList, int depth)
{
    // Select axis based on depth so that axis cycles through all valid values
    var int axis := depth mod k;

    // Sort point list and choose median as pivot element
    select median by axis from pointList;

    // Create node and construct subtrees
    var tree_node node;
    node.location := median;
    node.leftChild := kdtree(points in pointList before median, depth+1);
    node.rightChild := kdtree(points in pointList after median, depth+1);
    return node;
}

KDツリーを構築した後、今すぐ最近傍を見つける方法は？

ありがとう！

4

3 に答える 3

5

ウィキペディアのページの「最近傍検索」という見出しの下に記載されているとおりに最近傍を見つけます。そこにある説明は、任意の数の次元に適用されます。あれは：

  • 最近傍を探しているポイントを挿入しようとしているかのように、ルートから再帰的にツリーを下ります。
  • リーフに到達したら、これまでのベストとして記録します。
  • ツリーを再び上る途中で、各ノードに出会うと、次のようになります。
    • これまでのベストより近い場合は、これまでのベストを更新します。
    • ベストソファーからターゲット ポイントまでの距離が、ターゲット ポイントからこのノードの分割超平面までの距離より大きい場合、
    • ノードのもう一方の子も処理します (同じ再帰を使用)。
于 2012-06-07T16:13:33.827 に答える
2

私は最近、3 次元空間での最近傍検索用に KDTree をコーディングしましたが、NNS、特に 3.2 の wiki を理解するのと同じ問題に遭遇しました。すべてのテストで機能するように見えるこのアルゴリズムを使用することになりました。

最初のリーフ検索は次のとおりです。

public Collection<T> nearestNeighbourSearch(int K, T value) {
    if (value==null) return null;

    //Map used for results
    TreeSet<KdNode> results = new TreeSet<KdNode>(new EuclideanComparator(value));

    //Find the closest leaf node
    KdNode prev = null;
    KdNode node = root;
    while (node!=null) {
        if (KdNode.compareTo(node.depth, node.k, node.id, value)<0) {
            //Greater
            prev = node;
            node = node.greater;
        } else {
            //Lesser
            prev = node;
            node = node.lesser;
        }
    }
    KdNode leaf = prev;

    if (leaf!=null) {
        //Used to not re-examine nodes
        Set<KdNode> examined = new HashSet<KdNode>();

        //Go up the tree, looking for better solutions
        node = leaf;
        while (node!=null) {
            //Search node
            searchNode(value,node,K,results,examined);
            node = node.parent;
        }
    }

    //Load up the collection of the results
    Collection<T> collection = new ArrayList<T>(K);
    for (KdNode kdNode : results) {
        collection.add((T)kdNode.id);
    }
    return collection;
}

以下は、最も近いリーフ ノードから開始する再帰検索です。

private static final <T extends KdTree.XYZPoint> void searchNode(T value, KdNode node, int K, TreeSet<KdNode> results, Set<KdNode> examined) {
    examined.add(node);

    //Search node
    KdNode lastNode = null;
    Double lastDistance = Double.MAX_VALUE;
    if (results.size()>0) {
        lastNode = results.last();
        lastDistance = lastNode.id.euclideanDistance(value);
    }
    Double nodeDistance = node.id.euclideanDistance(value);
    if (nodeDistance.compareTo(lastDistance)<0) {
        if (results.size()==K && lastNode!=null) results.remove(lastNode);
        results.add(node);
    } else if (nodeDistance.equals(lastDistance)) {
        results.add(node);
    } else if (results.size()<K) {
        results.add(node);
    }
    lastNode = results.last();
    lastDistance = lastNode.id.euclideanDistance(value);

    int axis = node.depth % node.k;
    KdNode lesser = node.lesser;
    KdNode greater = node.greater;

    //Search children branches, if axis aligned distance is less than current distance
    if (lesser!=null && !examined.contains(lesser)) {
        examined.add(lesser);

        double nodePoint = Double.MIN_VALUE;
        double valuePlusDistance = Double.MIN_VALUE;
        if (axis==X_AXIS) {
            nodePoint = node.id.x;
            valuePlusDistance = value.x-lastDistance;
        } else if (axis==Y_AXIS) {
            nodePoint = node.id.y;
            valuePlusDistance = value.y-lastDistance;
        } else {
            nodePoint = node.id.z;
            valuePlusDistance = value.z-lastDistance;
        }
        boolean lineIntersectsCube = ((valuePlusDistance<=nodePoint)?true:false);

        //Continue down lesser branch
        if (lineIntersectsCube) searchNode(value,lesser,K,results,examined);
    }
    if (greater!=null && !examined.contains(greater)) {
        examined.add(greater);

        double nodePoint = Double.MIN_VALUE;
        double valuePlusDistance = Double.MIN_VALUE;
        if (axis==X_AXIS) {
            nodePoint = node.id.x;
            valuePlusDistance = value.x+lastDistance;
        } else if (axis==Y_AXIS) {
            nodePoint = node.id.y;
            valuePlusDistance = value.y+lastDistance;
        } else {
            nodePoint = node.id.z;
            valuePlusDistance = value.z+lastDistance;
        }
        boolean lineIntersectsCube = ((valuePlusDistance>=nodePoint)?true:false);

        //Continue down greater branch
        if (lineIntersectsCube) searchNode(value,greater,K,results,examined);
    }
}

完全な Java ソースはここにあります。

于 2012-07-02T21:15:07.640 に答える
0

ポイントが 3-D(x,y,z) の場合、どのように変更すればよいか知りたいです。

この行で現在の軸を取得します

var int axis := depth mod k;

軸に応じて、対応するプロパティを比較して中央値を見つけます。例えば。axis = 0 の場合、x プロパティと比較します。これを実装する 1 つの方法は、検索を行うルーチンで比較関数を渡すことです。

于 2012-06-07T16:19:20.563 に答える