image-processing - Quad-Tree を非正方形の長方形に適用できますか?

Question

Quad-Tree を使用して 2-D 高速衝突検出を実装しようとしています。

私の知る限り、Quad-Treeはリージョンを北西、北東、南東、南西の4つのサブリージョンに分割します。この分割は正方形で完全に機能します。しかし、領域が正方形ではない長方形の場合はどうなるでしょうか? その場合、長辺と短辺を均等に分割することはできず、短辺がどこまで分割できるかを決定します。

私はこれで正しいですか？ということですか？

Answer 1

四分木の辺の長さとして、関心領域のバウンディングボックスの幅と高さの最大値を単純にとります。

別の解決策: 私が見た 2 つのクワッド ツリーの実装では、内部的に四角形が使用されているため、提供されたルート境界が正方形でなくても、そのまま使用できます。各サブディビジョン ステップで境界の幅と高さの両方を分割します。
ただし、10 種類以上の異なる Quadtree タイプがあることに注意してください。Rectangle Quadtrees について話しています。

ある実装では、辺の長さを 2 で割った値を明示的に使用するため、非平方根の境界ではうまく機能しません。

ただし、最初の文をお勧めします。ルート境界として正方形を使用することをお勧めします。これは、すべての四分木タイプで機能します。