3d - 适合一组方向的最紧锥体

Question

给定 3D 中的一组单位方向d_1, ..., d_n ,

如何找到它们周围最紧的锥体？

例如，我怎样才能找到另一个单位向量m和一个表示角度的标量值alpha，例如：

foreach i, AngleBetween( m , d_i ) < alpha

阿尔法是最小的。

补充说明：方向可以跨越一半以上的空间。在这种情况下，“圆锥”是指从圆锥顶点开始并在圆锥轴给定角度内的一组半线。

Answer 1

如果您的一组方向都落在通过原点的一个半空间内，那么您可以计算单位半径球体上矢量尖端的凸包，这会在该球体上产生一个凸多边形，然后找到包围该多边形的最小圆. 您可以通过投影到合适的平面来避免球面计算。

我意识到这是一个抽象的观点，您可能需要更具体的建议，但它仍然可能会有所帮助：凸包 + 最小外接圆。

如果您的一组方向跨度超过半个空间，那么您需要在这种情况下定义“圆锥”的含义。

Answer 2

这是一个线性规划问题。

求 a, p 最大化 cos(a) 服从：
px*d1x+py*d1y*pz*d1z >= cos(a)
px*d2x+py*d2y*pz*d2z >= cos(a)
...
px *dnx+py*dny*pz*dnz >= cos(a)

我会研究 LP 算法。同时，我已经解决了一个非常相似的问题，这可能是一个起点：https ://github.com/VictorDavis/GeoConvexHull 。你是对的，一旦你找到了凸包，你就可以找到最小外接圆。但事实证明，证明 n 个点位于同一个半球并非易事。也许可以定制这个算法来回答你的“最小锥体”问题。