Quadtrees：単純なケースを処理できない共通の交差メソッド

Question

私は単純なGUIライブラリを作成しており、マウスイベント中にどのオブジェクトが相互作用するかを決定するためにクォードツリーを使用しています。私はgithub上のいくつかのquadtreeライブラリを調べていましたが、それらはすべてquadtreeに長方形のオブジェクトを追加する方法を含んでいました。 方法は、すべてのケースでは、単に矩形が与えられた四分木と交差かどうかチェック：

return quadtree.x2 >= rect.x1 
    and quadtree.x1 <= rect.x2 
    and quadtree.y2 >= rect.y1 
    and quadtree.y1 <= rect.y2 

しかし、これは最も単純な例の一つで、不要な結果を与える：100x100の正方形の領域を想像してみてください。座標（0,0）、（0,50）、（50,0）、（50,50）の領域に4つの50x50四角いオブジェクトを配置します。これらのオブジェクトが1つのオブジェクトの最大容量を持つ100×100クォッド・ツリーに配置されていれば、四分木の最初のレイヤーが分割され、4つの結果ツリーがそれぞれ正方形の1つを正確に含むことが視覚的に予想されます。

私は正方形の中に配置されたツリーを決定するために上記の方法を使用する場合は、しかし、私は、各オブジェクトは、すべての4本の木と交差することを見つけます。これにより、各樹木は最大深度に達するまで迅速に分割される。

私はこれを回避するために見る唯一の方法は、2つのチェックを使用することです：。

return (quadtree.x2 > rect.x1 
    and quadtree.x1 < rect.x2 
    and quadtree.y2 > rect.y1 
    and quadtree.y1 < rect.y2) 
    or (quadtree.x2 == rect.x1 
    and quadtree.x1 == rect.x2 
    and quadtree.y2 == rect.y1 
    and quadtree.y1 == rect.y2) 

を（最も簡単な場合には大規模なオブジェクトがために、以来、バウンディングボックス内に表示しなければならないであろうたとえば、座標（0,0）、w = 100、h = 100のオブジェクトも左上のクォッドツリーに属します）。

また、四角形と四角形の重なりを計算してそれは非ゼロです。

何か不足していますか？これはquadtreeのための理想的な状況であるはずですが、ほとんどの実装では、それは大きな混乱です。

Answer 1

これは理想的な状況ではありません。なぜなら、4つの矩形は部分的に重なっているからです。たとえば、10^10の浮動小数点数を仮定すると、実際にはすべてのポイントは10^10の長さの小さな矩形であるため、長方形は10 ^（ - 10） 。これが深い木を得る理由です。

しかし、私はまた、少し修正されたオーバーラップチェックでツリーを改善できると思います。あなたのコードでは、サブノードはすべて少しだけ重なり合っています。これは、例えば、最小値（又は最大値）を除くと、より良い機能するであろう：

return quadtree.x2 >= rect.x1 
    and quadtree.x1 < rect.x2 
    and quadtree.y2 >= rect.y1 
    and quadtree.y1 < rect.y2 

だから左下のノードの座標を実際にそのノードの外あります。これは、少なくともポイント（50,50）のようないくつかのノードで起きるポイントを避け、左下の矩形は1つのノードにのみ格納されるでしょう。