私はクワッドツリーで2次元高速衝突検出を実装しようとしています。四角形ではない四角形に四角形を適用できますか？
AFAIKでは、クアッドツリーは、領域を北西、北東、南東および南西の4つのサブ領域に分割します。この分割はの正方形と完全に一致します。しかし、地域がの非正方形の長方形の場合はどうなりますか？その場合、長辺と短辺を均等に分割することはできません。また、短辺は分割できる範囲を決定します。
私はこの問題に直面していますか？それは意味されていますか？
注目領域の境界ボックスの幅、高さの最大値をクワッドツリーの辺の長さとしてください。
もう1つの解決策：私が見た2つのクワッドツリーの実装では、内部に長方形が使用されているので、指定したルート境界が正方形でなくてもボックスが使い果たされます。それぞれの細分化ステップで境界の幅と高さの両方を分割します。
ただし、10種類のQuadtreeタイプがあります。私はRectangle Quadtreesについて話しています。
1つの実装では、2で割ったa側の長さが明示的に使用されるため、非平方根境界ではうまく機能しません。
しかし、私は最初の文章を推奨しています。正方形を根本的に使用することをお勧めします。 これはすべてのクワッドツリータイプで機能します。
長方形の最も長い辺と同じ辺を持つ四角形の四辺形を使用できない理由はありますか？空の空間には何も存在しませんが、それは無視できるオーバーヘッドでなければなりません。 –
あなたはいくつかのパディングを追加することを意味します。それは良いアイデアです。しかし、任意の形の領域はどうですか？できるだけ小さな四角で囲んでいいですか？ – smwikipedia
それはアイデアです！クアッドツリーは、任意のスペースを囲む場合でも同じように動作します。 –