binary-search-tree - アンバランスをバランスのとれた BSP ツリーに変換しますか?

Question

アンバランスなbsp をバランスの取れた bsp ツリーに変更する方法を示す例が必要です。

私を助けてください。

Answer 1

Quake では、これはマッパーに任されています。Quake BSP コンパイラは、起点からボリュームの 2 分割を開始します(0, 0, 0)。そのため、よりバランスのとれた BSP に適したマップを生成するために、マッパーは原点を中心に、3 つの軸すべてでジオメトリを中央に配置する必要があります。

同様の戦略があなたの問題に適用できると思います。BSP ノードの絶対境界 (最小値と最大値) を見つけ、中心点を計算します。ここから、ツリーの分割を開始する必要があります。マップが完全に対称でない限り、完全にバランスの取れたツリーを実現することはできません。しかし、実際には、これは比較的近いものになります。