algorithm - 球扇形边界框(锥球相交)

Question

给定一个球形段(它的半径、方向和角度)，我如何以最简单的方式计算它的轴对齐边界框？

请注意，我对任意方向的片段感兴趣，而盒子必须与轴对齐。紧密定向的边界框计算起来很简单。

问题可以简化为球冠的边界框，但我也找不到算法。

Answer 1

为简单起见，假设我们平移和缩放坐标系，使中心位于 (0, ..., 0)，半径为 1。令 u 为坐标系的端点段(使得‖u‖² = 1)并让以弧度为单位的角度为 θ。蓝色部分是所有点v 使得‖v‖² ≤ 1 和u·v ≥ ‖< strong>u‖ ‖v‖ cos θ = ‖v‖ cos θ。要找到 d 维度的轴对齐边界框，我们需要找到 2d 向量 v 来最小化/最大化每个单独的坐标，即，给定一个向量 e 使得 +e 或 -e 属于轴基(例如，e> = (0, −1, 0, ..., 0)) 我们希望最大化 e·v 受 v 的限制>.

maximize e·v
subject to
‖v‖² ≤ 1
u·v ≥ ‖v‖ cos θ

我们首先观察到，不失一般性，‖v‖ = 0 或‖v‖ = 1，因为目标是线性的，其他点位于这些的凸组合。让我们关注后一种情况。

maximize e·v
subject to
‖v‖² = 1
u·v ≥ cos θ

其次，在e和u所跨越的空间中存在一个最优解。给定任何最优解，我们可以在不增加其范数或用e或u改变点积的情况下将正交投影引入该空间，因此投影也是可行和最优的.

因此，我们通过让 v = αe + βu 根据系数 α 和 β 重写问题。

maximize e·(αe + βu)
subject to
‖αe + βu‖² = 1
u·(αe + βu) ≥ cos θ

让我们扩展乘积并使用 ‖e‖² = ‖u‖² = 1 的事实。

maximize α + β(e·u)
subject to
α² + 2αβ(e·u) + β² = 1
α(e·u) + β ≥ cos θ

现在我们进行案例分析。忽略线性约束，目标最多为 1，因此解 α = 1 和 β = 0(即 v = e)是最优的。此解仅在e·u ≥ cos θ时可行。

如果此解不可行，则线性约束必须紧:α(e·u) + β = cos θ，或 β = cos θ − α (e·u)。然后我们可以代入，求解得到的二次方程，并采用得分更高的解(除非他们都得分为负，在这种情况下界限为 0)。