求检测两条贝塞尔曲线同参数碰撞的高效算法

首先明确你的核心需求：不是找两条贝塞尔曲线任意参数下的交点，而是要检测它们是否在同一个t值（t∈[0,1]）上重合——本质上是求解方程 B₁(t) = B₂(t)，等价于构造差值曲线 C(t) = B₁(t) - B₂(t)，然后判断 C(t) 是否在 t∈[0,1] 上经过原点（2D/3D空间的零点）。

下面是无需遍历参数t、仅通过控制点就能快速检测的方案：

一、快速排除阶段（纯控制点计算，O(n)复杂度） #

这一步可以快速过滤掉绝大多数无碰撞情况：

• 凸包检测：贝塞尔曲线的凸包等于其控制点的凸包。计算差值曲线 C(t) 的控制点凸包，如果原点不在这个凸包内部，那么 C(t) 不可能经过原点，直接判定无碰撞。

  实现思路：先计算控制点的凸包，再用点-in-凸包算法判断原点是否在其中——这个算法非常高效，对于n个控制点的凸包，判断时间是O(log n)。

• 符号一致性检查：对于2D场景，分别看 C(t) 的x分量和y分量的控制点：
  • 如果所有x分量的控制点都大于0（或都小于0），那么 C(t) 的x(t)在整个[0,1]区间内都会保持同号，不可能等于0，直接排除；
  • 同理对y分量做同样检查。3D场景则扩展到z分量。

二、精确求解阶段（代数方法，无遍历） #

如果快速排除没把情况过滤掉，就需要精确求解 C(t)=0 是否有解在[0,1]内：

1. 将差值曲线转为多项式形式：贝塞尔曲线可以通过二项式展开转换为标准多项式。比如n次贝塞尔曲线的多项式形式为：
   C(t) = Σ (C(n,k) * (1-t)^(n-k) * t^k * P_k)，其中C(n,k)是组合数，P_k是差值曲线的控制点。
   展开后，x(t)和y(t)（2D）都是n次多项式。
2. 求多项式的公共根：问题转化为找x(t)=0和y(t)=0的公共根t∈[0,1]，这里可以用**结式（Resultant）**方法：
   • 结式是一个行列式，若两个多项式有公共根，则结式的值为0。对于n次的x(t)和y(t)，结式是(2n)×(2n)的行列式（当两个多项式次数相同时）。
   • 计算结式后，若结式不为0，说明没有公共根，判定无碰撞；若结式为0，则进一步求解公共根，验证根是否落在[0,1]区间内。
3. 低次曲线的简化处理：实际应用中最常用的是三次贝塞尔曲线，这时候x(t)和y(t)都是三次多项式，你可以用更简化的方法：比如将x(t)和y(t)联立，消元后得到一个6次多项式，求解这个多项式的根，再验证是否满足原方程且在[0,1]内。

三、特殊情况处理 #

• 如果两条曲线的控制点完全相同，那么C(t)恒为0，所有t∈[0,1]都满足碰撞；
• 如果差值曲线的某个控制点就是原点，需要验证对应的t值是否在[0,1]内（注意：贝塞尔的中间控制点不直接对应某个t值，必须解方程确认）；
• 数值精度问题：实际计算中要设置一个epsilon阈值（比如1e-6），判断计算结果是否近似为0，避免浮点数误差导致误判。

内容的提问来源于stack exchange，提问作者Thomas Wagenaar