9

エッジでラップする 2D マップがあります。したがって、右端から移動すると、マップの左側に再び表示されます。他の 3 つのエッジについても同様です。

これは、ポイントの範囲内の要素を見つけるために使用する KDTree の継承可能な問題です。通常、超球体が超平面と衝突するかどうかをチェックして、ツリーの反対側を検索し続ける必要があるかどうかを確認しますが、このチェックはラップ エッジでは機能しません。

ドーナツ 2D 空間で動作するように KD ツリーを変更する方法はありますか?

4

3 に答える 3

4

データ構造は変更する必要はありませんが、検索手順は変更する必要があります。[0, w) * [0, h) の座標 (x, y) で各ポイントを表します。w はマップの幅、h は高さ、* はデカルト積を表します。これらのポイントを通常の KD ツリーに格納します。

KD ツリーを検索するための基本的なプリミティブは、点 (x, y) と四角形 [a, b] * [c, d] を指定して、点から四角形までの距離 (二乗) を決定することです。通常、これは g(x, a, b) 2 + g(y, c, d) 2です。

g(z, e, f) = e - z if z < e
             0     if e <= z <= f
             z - f if f < z

z から [e, f] までの 1 次元距離です。トロイダル空間では、ラップアラウンドを考慮して g をわずかに変更します。

g(z, e, f, v) = min(e - z, (z + v) - f) if z < e
                0                       if e < z < f
                min(z - f, (e + v) - z) if f < z.

距離の二乗は g(x, a, b, w) 2 + g(y, c, d, h) 2です。このバリアントの実行時間は同等になると思います。(繰り返しをやり直しますが、通常の KD ツリーの最悪のケースは、ほとんどの場合、実際よりもはるかに悪いです - O(n 1/2 ) は、n 個の点の中から 2D で最近傍を特定します。)

于 2011-11-15T22:55:29.603 に答える
2

Jitamaroは、「2xサイズ」の四分木に基づく方法を提案しましたが、説明しませんでした。代替方法を暫定的に提案する前に以下で説明するように、クアッドツリーが2つではなく4倍のノードを使用することを除いて、これは合理的な提案です。

各（x、y）座標が整数-.5 < x <= .5で-.5 < y <= .5あり、整数である場合は常にj, k、点（x + j、y + k）は点（x、y）と同一であると仮定します。四分木Tが範囲内の座標を持つ点をカバーするようにします-1 < x,y <= 1。（x、y）のアイテムをTに追加するたびに、ここで-.5 < x,y <= .5、elseのx' = {x-1場合は、elseの場合は。また、（x、y'）、（x'、y'）、および（x'、y）にアイテムを追加します。[後でポイントを削除するときは、（x'、y'）などを再度計算して削除します。]間隔外のルックアップ座標が適切に調整されている限り、最も近いポイントのルックアップが適切に機能することは簡単にわかります。x>0x+1}y' = {y-1y>0y+1}(-.5,.5]

4倍のノード数が取引を妨げる場合、上記の座標がレベルより上のサブツリーで使用されk=3、相対座標がレベルより下に格納されkている場合、レベルより下のサブツリーの単一コピーを維持できるはずであることに注意してくださいk。つまり、レベルの各サブツリーにkは4つの親があります。（これが完全に機能するかどうかを知るのに十分なことは考えていません。機能しない場合は回答を編集します。）

于 2011-11-06T05:46:20.870 に答える
0

quadtree は、4 つのリーフを持つ KD ツリーです。四分木は、そのデータ構造自体がラップであるため、ラップするのに役立ちません。構造の四分木 2x サイズを使用するだけです。

于 2011-11-06T01:13:14.507 に答える