小编mik*_*olt的帖子

我正在寻找一种算法,让我可以确定一个实体对象是否适合具有给定尺寸的盒子(矩形棱镜).可以旋转和平移固体以适合盒子内部.

我已经有了解决这个问题的方法:

1. 计算实体的最小边界框(已知算法).
2. 确定最小边界框是否适合另一个框(简单).

(编辑:这不是一个有效的解决方案)

这有效,但我正在寻找更有效的解决方案.最小边界框算法在O(n ^ 3)时间内运行,其中n是顶点数.我希望有一个O(n ^ 2)算法.

请注意,除了"实体对象"之外,我也可以询问形成实体凸包的点集是否适合框内.