如何确定一个立方体在O(N^2)的时间复杂度内是否能放在给定的盒子里？

Question

我正在寻找一种算法，可以确定一个立方体实体是否能够放入给定尺寸的矩形箱子中。该实体可以旋转和移动以适应箱子内部。

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

1. 计算实体的最小边界框（已知算法）。 2. 确定最小边界框是否能够放入另一个盒子中（简单）。

（编辑：这不是有效的解决方案）

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

请注意，与“实体对象”相比，我可能只是在问由该实体的凸包形成的点集是否能够放入盒子中。

- mikebolt

---

从实际角度来看，我们谈论的顶点数量是多少？ - Robert Harvey

好的。嗯，其中许多顶点都不相关。只有那些距离对象中心最远的顶点才会起作用（内部或凹面的顶点根本不重要，只有凸面的顶点），因此我建议您仅搜索那些在计算中会产生影响的顶点。换句话说，您并不需要太多细节来确定对象是否适合。 - Robert Harvey

@RobertHarvey 很好的观点。除了忽略凸包内部的点外，忽略靠近物体某个中心的点可能也是一个不错的选择。 - mikebolt

如果剔除过程将您的相关顶点数量降至约100个，这并不会让我感到惊讶，这将使您现有的O(n^3)算法可行。 - Robert Harvey

@mikebolt：是的，但如果最小外接球适合，那么最小外接矩形也会适合。只有当它不适合时，您才需要更昂贵的最小外接矩形计算。如果大量输入数据通过边界球计算，则可以避免对大量输入值进行边界框计算（因此您将在O（N ^ 2）和O（N ^ 3）之间具有分摊性能）。 - Eric J.

Answer 1

你可能想看一下这篇文章。它提供了一种算法，可以在O(n log n + 1/epsilon^3)的时间内计算出一个3D最小边界框的1+epsilon近似值。

- Joshua

Answer 2

如果this没有过时，那么目前没有更快的精确算法：

目前最快的三维边界长方体算法是由[O'Rourke, 1985]提出的，时间复杂度为O(n3)，有几个特殊情况，并且实现起来相当困难。O'Rourke的算法基于他的观察：“包围凸多面体的最小体积盒子必须至少有两个相邻的面包含多面体的边缘。” 目前还没有找到更快的精确算法。

尽管如此，由于对于大点集而言O(n3)算法可能非常慢，因此人们对于在三维及更高维度中寻找最小长方体的快速近似方法非常感兴趣。已经提出了几种方法，例如：（1）仅考虑具有与多面体面重合的面的长方体（如[O'Rourke, 1985]所讨论的那样是O(n2)，但可能会大2倍），（2）对点集进行主成分分析（这很快，但通常会导致较差的解决方案），（3）暴力方法，对长方体的许多可能方向进行采样，（4）将大点集缩小为较小的近似集（例如，通过选择包含集合点的离散网格中的单元格）[Barequet＆Har-Peled，1999]等。所有这些方法都在解决方案精度与执行效率之间进行权衡。

因此，您必须决定是否需要精确的结果，或者是否可以接受近似值并使用其中一个参考文章。

- Jens Schauder

Answer 3

快速排除一些对象

如果您预计答案通常是“否”，则可以按照以下方式相对迅速地排除许多实例：如果有一对由盒子最长对角线以上的距离分隔的点，则该形状不可能适合其中。这是O(n^2)，但是一旦找到了更远的一对，就可以停止，您还可以首先沿着最长维度对点进行排序，并从相反的两端选择点作为成对点以增加发现机会。

与Eric J.建议结合使用边框球来规定一个物体中的，这可能会快速解决许多情况。

快速排除一些对象

您拥有的另一个选项是仅随机投影点多次，并计算AABB；如果它适合您的框，那么您完成了。 这需要生成随机单位长度向量。

- j_random_hacker