一連の四分木 (ヒルベルト曲線など) がある場合、特定の深さで最適な (または十分に良い) 範囲のセットを見つけるための良い方法は何でしょうか。
たとえば、バウンディング ボックス 0,0 と 1,3 の間のポイントを検索する場合、次の単純な範囲を適用できます。
- 深さ 1 - 範囲 0,0-1,0 (~33% の検索スペース)
- 深さ 2 - 範囲 0,0-1,0 および 1,0-0,1 (~13% の検索スペース)
- 深さ 3 - 範囲 0,0-1,0 および 1,3-0,3 (~9.8% の検索スペース)
明らかに、この検索の深さ 3 が最適ですが、縮小された検索スペースは、深さ 1 から深さ 2 への低下と比較して、わずかしか低下していません。
(はるかに) 大きい深さで、または境界を越える検索では、さまざまな深さの差を推定したり、理想的にはバウンディング ボックスをカバーするさまざまな深さの範囲の組み合わせを理想的に選択したりするための優れたアルゴリズムがあります。
特にポリゴンには興味がありませんが、ポリゴンで機能するソリューションがあればボーナスポイントです。