我有一个三角形的多边形汤，我想为其构建一个 BSP 树。我当前的程序只是通过一次从模型中插入一个随机三角形来构建一个 BSP 树，直到所有三角形都被消耗掉，然后它检查树的深度和广度并记住它获得的最佳分数(最低深度，最低广度) )。
根据定义，最佳深度将是 log2(n)(如果共面三角形分组，则更小？)其中 n 是我的模型中的三角形数量，最佳宽度是 n(意味着没有发生 split )。但是，有某些三角形配置永远不会达到这个顶峰。
是否有有效的测试来检查我的 BSP 树的质量？具体来说，我试图为我的程序找到一种方法，让我知道它应该停止寻找更优化的构造。
最佳答案
最优树的构建是一个NP完全问题。确定给定的树是否是最优的本质上是相同的问题。
从这个 BSP faq :
关于algorithm - 如何测试给定的 BSP 树是否最优？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/163225/