2

そこで、最近傍探索を行うためにKDツリーを実装しています。ツリー部分の構築は機能していますが、検索部分を完全には理解していないと思います。

隣人を探すために木を横断することについて、ウィキペディアの記事は次のように述べています。

Starting with the root node, the algorithm moves down the tree recursively, in the same  
way that it would if the search point were being inserted (i.e. it goes right or left 
depending on whether the point is greater or less than the current node in the split 
dimension).

「スピットディメンションの現在のノードよりも大きいまたは小さい」とはどういう意味ですか？クエリからの距離に基づいてポイントを比較しますか、それとも分割ディメンションでポイントを比較しますか？

また、誰かが超空間と超平面についての部分を説明できますか？理解できた気がしますが、よくわからないのでもう少し説明をお願いします。

ありがとう！

4

1 に答える 1

4

各ノードは、スペースを1つの軸に沿って2つの半空間に分割します。問題のポイントがその分割平面に対して相対的な位置を確認して、ツリーのどちら側を下に移動するかを決定します。たとえば、ポイントが（4,7,12）で、y軸を9で切断する分割平面がある場合、7と9を比較して、左側（未満）を下に移動することにします。最初にkdツリー。左側で最も近い隣人を見つけたら、それが2（分割平面までの距離：9-7）よりも近いかどうかを確認します。分割平面よりも近い場合は、他のハーフツリーをまったく横断する必要はありません。これが非常にうまく機能する理由です。ほとんどの場合、1つのサブツリーをトラバースするだけで済みます。

お役に立てば幸いです。

于 2010-11-04T17:49:01.847 に答える