computational-geometry - 找到最适合的 3d 对象

Question

我有一个不均匀的 3d 对象，需要将另一个 3d 对称形状（圆锥或圆柱）放入其中。我需要旋转和扩展/收缩对称形状，以便我们可以在这个粗糙的物体中找到最大的拟合圆锥体/圆柱体。

我看过一些垃圾箱包装问题，但似乎都只处理矩形（容器以及要适合的物体），似乎并不完全符合我的要求。

该算法还应该具有最佳性能。

Answer 1

纸呢：

FOLLERT，弗兰克等人。计算最大的空锚定圆柱体和相关问题。国际计算几何与应用杂志，1997，7.06：563-580。

摘要说：

令 S 为 ℝd 中的 n 个点的集合，令 S 的每个点 p 具有正权重 w(p)。我们考虑计算从原点发出的射线 R（分别是通过原点的直线 l）的问题，使得 minp∈S w(p) · d(p, R) (resp. minp∈S w(p) · d(p, l)) 是最大的。如果所有权重都是 1，则这对应于计算从不包含 S 的任何点且半径最大的原点（即轴包含原点的圆柱体）发出的筒仓. 对于 d=2，我们展示了如何在 O(n log n) 时间内解决这些问题，这在代数计算树模型中是最优的。对于 d=3，我们给出了基于参数搜索技术并在 O(n log5 n) 时间内运行的算法。以前针对这些三维问题最知名的算法的运行时间几乎是二次方。在论文的最后部分，我们考虑了一些相关的问题。

一个pdf在这里。