graphics - 乱数 N (N<50) を指定して空間を N 個のパーティションに分割できるアルゴリズムはありますか?

Question

空間分割については、R-Tree、kd-tree、境界間隔階層などについて読みました。これらのデータ構造は、空間クエリに役立つことがわかりました。ただし、パーティション分割は行いますが、データ構造からそれらのパーティションを取得する方法がわかりません。したがって、私の質問は、「数値 N と、たとえば X 個のポリゴンを含むマップが与えられた場合、ほぼ同じ数のポリゴンを含む N 個のパーティションを取得できますか?」ということになります。

Answer 1

正確に N 個のパーティションが必要な場合は、R ツリーの一般的な一括読み込み戦略のいずれかが機能するはずです。必ずしも最適であるとは限りませんが、ほぼ同じサイズの正確に N 個のパーティションを生成するようにこれらを強制することができます。

kd ツリーには、左側にも右側にもないオブジェクトがあります。ただし、kd-tree の一括読み込み戦略を使用して、それを変更して N 個のパーティションを生成することができます。実際には、バルクロードと R ツリーのもう 1 つの単純でありながら非常に効果的な方法もあります。

N を 2 の累乗、またはdある数の 4 乗に制限すると、分割は通常より良くなります。したがって、3D データセットを 9 ページに分割する方が、8 ページに分割するよりもはるかに簡潔に実装できます。