如何确定一个实体是否适合O（N ^ 2）中给定的框内？
我正在寻找一种算法，可以让我确定一个固体物体是否可以放入具有给定尺寸的盒子（直角棱镜）内。 固体可以旋转并平移到盒内。
我已经有了解决这个问题的方法：
（编辑：这不是一个有效的解决方案）
这工作，但我正在寻找一个更有效的解决方案。 最小边界框算法运行在O（n ^ 3）时间，其中n是顶点的数量。 我希望有一个O（n ^ 2）算法。
请注意，代替“固体物体”，我可能会问，形成固体凸包的点集是否可以放入箱内。
你可能想看看这篇论文。 它给出了一个算法，而不是在O（n log n + 1 / epsilon ^ 3）时间内计算3D最小边界框的1 + epsilon近似。
快速排除一些物体
如果您希望答案通常为“否”，那么您可以很快排除许多实例（如下所示）：如果有一对点的间隔超过了您盒子的最长对角线，则形状不能可能适合它。 这是O（n ^ 2），但是只要你找到一对更远的对，你就可以停下来，并且你还可以首先根据最长的维度对点进行排序，并将对立点的点作为对，以增加找到的机会
结合Eric J.提出的使用边界球来控制物体的建议，这可能会很快解决很多情况。
快速统治一些物体
你拥有的另一个选择是随机投影点数，并计算AABB; 如果它适合你的盒子，你就完成了。 这需要生成随机的单位长度向量。
如果这不是过时的，那么目前没有更快的确切算法：
当前最快的3D边界长方体算法是由[O'Rourke，1985]在O（n3）时间内运行的，有几种特殊情况，并且实现起来相当困难。 O'Rourke的算法是基于他的观察，“一个包围凸多面体的最小体积的框必须至少有两个包含多面体边的相邻面。”没有找到更快的精确算法。
无论如何，由于O（n3）算法在实践中对于大点集合来说可能非常缓慢，因此对3D和更高维度中的最小立方体的快速近似值得关注。 已经提出了几种方法，例如：（1）仅考虑具有与多面体面相一致的面的立方体（如[O'Rourke，1985]中所讨论的O（n2），并且可以是2倍太大） ，（2）点集上的主成分分析（这是快速的，但往往导致一个不好的解决方案），（3）蛮力方法，取样一个长方体的许多可能的方向，（4）减少大点设置为一个较小的近似集合（例如，通过选择离散网格中包含设定点的单元格）[Barequet＆Har-Peled，1999]等。 所有这些方法都在解决方案准确性与执行效率之间进行权衡。
所以你必须决定你是否需要确切的结果，或者你是否可以接受和使用所引用的文章。
链接地址: http://www.djcxy.com/p/82087.html上一篇: How to determine if a solid fits inside a given box in O(N^2)?