binary-search-tree - 将不平衡转换为平衡 bsp 树？

Question

我需要一个示例来说明如何将不平衡的 bsp 更改为平衡的 bsp 树。

请帮我。

Answer 1

在 Quake 中，这实际上是由映射器决定的。Quake BSP 编译器从源开始对卷进行二等分(0, 0, 0)。因此，为了生成更平衡且对 BSP 友好的地图，映射器应在所有三个轴上围绕原点将其几何图形居中。

我认为类似的策略可能适用于您的问题。找到 BSP 节点的绝对边界（最小值和最大值），并计算中心点。那是您应该开始对树进行分区的地方。现在，除非您的地图完全对称，否则您将永远无法获得完美平衡的树。但是，出于实际目的，这会让您相对接近。