计算科学 - 如何判断两个圆柱体是否相交？ - 吾爱随笔录

计算科学计算几何凸优化约束优化最小二乘二次规划

2021-11-29 00:34:07

考虑任意两个圆柱体，定义为：它们底部的中心 $A_i$ , 它们底部的半径 $R_i$ , 单位向量 $W_i$ 它们的轴方向和长度 $L_i$ 的气缸，其中 $i=1,2$ ：

两个圆柱相交的充要条件是什么？

我想以数字方式确定（通过程序，例如 Matlab 或 C++）两个给定的圆柱体是否相互交叉。所以问题是否在数值上可解，解的唯一性和存在性就变得很重要。

在数值上，我试图将问题转换为线性约束最小二乘问题，但发现很难证明交集和问题的解之间的等价性。

约束最小二乘问题是：

然后将最小值与 $\displaystyle\sum\limits_{i=1}^2 R_i^2$ 确定圆柱体是否相交。-- 似乎可以在没有交点而最小值仍然小于标准时找到反例。

如何找到一个数值可解（如数值凸优化）的充要条件，以确定两个圆柱体是否相交？

2个回答

David Eberly 在这里很好地描述了解决方案（带有伪代码）：http: //www.geometrictools.com/Documentation/IntersectionOfCylinders.pdf

简短的总结：像大多数凸-凸碰撞检测算法一样，您系统地搜索圆柱之间的分离轴。

为了将来对类似问题的参考，实时渲染的作者维护了一个链接表，用于不同类型的图元之间的交叉测试。

提示：

如果两个气缸平行，问题就简单了。否则，如果轴之间的垂直距离超过半径之和，则不存在交集。

否则，两个侧面之间有一条相交曲线。可以解析表示：不失一般性，第二个圆柱体是垂直的，有一个底在原点（如果不是，则旋转并平移）。其侧面有隐式方程

x^{2} + y^{2} = R_{2}^{2} .

$x^2+y^2=R_2^2.$

参数方程可以达到第一个圆柱体侧面的任意一点

A_{1} + U_{1} R_{1} \cos (s) + V_{1} R_{1} \sin (s) + W_{1} t, 0 \leq s \leq 2 π

$A_1+U_1R_1\cos(s)+V_1R_1\sin(s)+W_1t,\\ 0\le s\le 2\pi$ 在哪里

U_{1}

$U_1$ 和

V_{1}

$V_1$ 形成一个正交基

W_{1}

$W_1$ .

将参数方程插入隐式方程，得到一个二次方程 $t$ . 所以你可以表达 $t$ 作为一个函数 $s$ , 分析。

解决 $t=0$ 和 $t=L_1$ （数字上）为您提供属于第一个圆柱体的曲线的有用部分，并划定一个 $(s,t)$ 领域。

通过将该域边界的方程代入参数方程 ( $z$ 组件），您应该能够判断是否

0 \leq A_{1 z} + U_{1 z} R_{1} \cos (s) + V_{1 z} R_{1} \sin (s) + W_{1 z} t \leq L_{2}

$0\le A_{1z}+U_{1z}R_1\cos(s)+V_{1z}R_1\sin(s)+W_{1z}t\le L_2$ 发生在域中。

其它你可能感兴趣的问题