基于迭代算法的Bézier曲线求交方法研究

Intersection Computation of Bézier Curves Based on Iterative Methods

摘要: 在计算机图形学及相关领域中，Bézier曲线求交问题备受关注。本文着重探究基于迭代算法的Bézier曲线求交方法。研究发现，当Bézier曲线的控制多边形不相交时，曲线本身必定不相交；而当控制多边形相交时，采用De Casteljau作为核心迭代手段，通过不断对曲线区间进行二分处理，逐步逼近曲线交点，有效提升求交的准确性与效率。此方法为解决Bézier曲线求交难题提供了新的思路与途径，在图形设计、计算机辅助几何设计等方面具有潜在应用价值。

Abstract: In the field of computer graphics and related areas, the problem of intersection of Bézier curves has received much attention. This paper focuses on exploring the method of finding the intersection of Bézier curves based on an iterative algorithm. The study reveals that when the control polygons of Bézier curves do not intersect, the curves themselves must not intersect; while when the control polygons intersect, the De Casteljau algorithm is adopted as the core iterative method. By continuously performing bisection processing on the curve intervals, the intersection points of the curves are gradually approached, effectively improving the accuracy and efficiency of intersection calculation. This method provides new ideas and approaches for solving the difficult problem of finding the intersection of Bézier curves, and has potential application values in aspects such as graphic design and computer-aided geometric design.

1. 引言

在计算机图形学(Computer Graphics, CG)与计算机辅助几何设计(Computer Aided Geometric Design, CAGD)领域，Bézier曲线作为一种灵活且强大的几何建模工具，被广泛应用于各种复杂形状的构建与表示[1]。在实际应用中，判断多条Bézier曲线是否相交以及确定交点位置是一个核心且基础的问题。

现有的Bézier曲线求交算法虽然丰富多样，但各有局限性。部分算法计算过程复杂，需要消耗大量的计算资源和时间，在处理大规模或复杂曲线模型时效率低下。还有一些算法在精度控制上存在不足，容易受到数值误差的影响，导致求交结果不准确。

本文主要对基于迭代算法Bézier曲线求交方法进行研究。此方法计算逻辑简洁高效，能有效减少计算量，显著提升计算效率，在复杂图形处理、精密模具设计等实际场景中具有广阔的应用前景。

2. 一元Bernstein基函数定义与性质

n次多项式Bernstein基函数为

$B_i^n\left(t\right)=\left(\begin{array}{c}n\\ i\end{array}\right)t^i{\left(1-t\right)}^{n-i},i=0,1,\cdots ,n,$

其中

$\left(\begin{array}{c}n\\ i\end{array}\right)=\frac{n!}{i!\left(n-i\right)!},i=0,1,\cdots ,n.$

为了方便，当i < 0或者i > n时，通常我们记$B_i^n=0$ [2]。Bernstein基函数决定了每个控制顶点对曲线上点的控制权重，随参数t在[0, 1]内变化，各基函数值相应改变，进而影响曲线形状。Bernstein基函数有如下性质：

(1) 非负性与权性：在计算曲线上某点时，所有控制顶点对该点的影响总和为1，确保曲线在控制顶点构成的凸包内，是Bézier曲线凸包性的数学依据。

(2) 端点特性：在端点t = 0和t = 1处，分别只有一个Bernstein基函数取值为1，其余全部为0即

$B_i^n\left(0\right)=\{\begin{array}{l}1,i=0,\\ 0,i\ne 0,\end{array}$ $B_i^n\left(0\right)=\{\begin{array}{l}1,i=n,\\ 0,i\ne n.\end{array}$

3. n次Bézier曲线的原理及其性质

称参数曲线段

$P\left(t\right)={\displaystyle \sum _{i=0}^n{P}_i}{B}_i^n\left(t\right),t\in \left[0,1\right]$ (1)

为一条n次Bézier，其中$B_i^n\left(t\right)\left(i=0,1,\cdots ,n\right)$ 为n次Berntein基函数，空间向量$P_i\in R^3\left(i=0,1,\cdots ,n\right)$ 为控制顶点，依次用直线连接相邻控制顶点，所得的n边折线多边形称之为Bézier多边形[2]。

利用Bernstein基函数的性质不难推出由(1)所定义的Bézier曲线有如下基本性质[2]：

(1) 端点插值性质：Bézier曲线插值于首末两个控制顶点，即P(0) = P₀，P(1) = P_n。

(2) 凸包性质：在几何意义上Bézier曲线完全落在由其控制多边形确定的凸包中。

(3) 对称性质：若控制顶点顺序反转，得到的Bézier曲线形状不变，但方向相反。这说明了由同一控制多边形定义的Bézier曲线是唯一的。

(4) 几何不变性与仿射不变性：Bézier曲线的形状取决于控制顶点，而与坐标系的选取无关，它是几何不变的。对Bézier曲线进行平移、旋转、缩放等仿射变换，等同于对其控制顶点进行相同的变换。

(5) 参数连续性：在参数区间[0, 1]上，Bézier曲线具有n − 1阶连续导数。

4. De Casteljau算法的迭代求交算法

在计算机辅助几何设计(CAGD)领域，De Casteljau算法是一种用于生成和计算Bézier曲线(Bézier Curves)的经典递归算法[3]。该算法基于凸组合原理，通过递归地对控制多边形的顶点进行线性插值，可高效地计算Bézier曲线上任意参数点的坐标。其核心思想是将n次Bézier曲线分解为两个n − 1次Bézier曲线的组合，通过迭代降阶的方式逐步逼近目标点，确保计算过程的数值稳定性与几何直观性。其迭代过程如下：

(1)对于给定的n次Bézier曲线，其控制点为$P_0,P_2,\cdots ,P_n$ ，要计算曲线上参数为$t\in \left[0,1\right]$ 的点B(t)。该算法通过不断地对控制点进行线性插值来逐步逼近曲线上的点[2]。

(2)计算过程[2]：一条n次Bézier曲线从形式上“降阶”为(n − 1)次Bézier曲线对任意的$0\le i\le n-1$ ，新的控制顶点$P_i^{\left(1\right)}$ 落在原控制多边形的边P_iP_{i + 1}上，且将边按比例t：(1 − t)进行分割。一直这样“降阶”下去，

$P\left(t\right)={\displaystyle \sum _{i=0}^{n-1}{P}_i^{\left(1\right)}}\left(t\right)B_i^{n-1}\left(t\right)=\cdots ={\displaystyle \sum _{i=0}^{n-k}{P}_i^{\left(k\right)}}\left(t\right)B_i^{n-k}\left(t\right)=\cdots =P_0^{\left(n\right)}\left(t\right),$

最后n次Bézier曲线从形式上“降阶”为0次Bézier曲线(即一点) $P_0^{\left(n\right)}\left(t\right)$ ，即我们要计算的曲线上的点P(t)。这就是Bézier曲线的De Casteljau算法，即为如下递归求值算法：

$\{\begin{array}{l}{P}_i^{\left(0\right)}\left(t\right)=P_i^{\left(0\right)}=P_i,i=0,1,\cdots ,n,\\ P_i^{\left(k\right)}\left(t\right)=\left(1-t\right)P_i^{\left(k-1\right)}\left(t\right)+t{P}_{i+1}^{\left(k-1\right)}\left(t\right),i=0,1,\cdots ,n-k;k=1,2,\cdots ,n.\end{array}$ (2)

上标k表示递推级数，每进行一级递推，控制顶点少一个，所得中间控制顶点都与参数t有关。

求交算法如下：

算法	三次Bézier曲线交点查找算法
输入	两组控制顶点：C1 = [0, 0; 2, 3; 5, 5; 0, 7]，C2 = [0, 5; 3, 2; 5, 3; 7, 5] (可替换为任意控制点)
输出	相交时：返回交点坐标 + 迭代次数，不相交：提示“无交点”
Step1	初始化控制点与绘图
	1) 定义控制点C1，C2 2) 生成100个参数t (linspace) 3) 计算曲线坐标(bezierCurve) → bezierC1/bezierC2 4) 绘制双曲线(蓝/红，线宽1.5)
Step2	凸包处理
	1) 计算凸包K1/K2 (convhull) 2) 绘制虚线凸包边界 3) 凸包相交检测(convexHullIntersect)： - 不相交→终止 - 相交→继续
Step3	变量初始化
	currentC1/C2 ← C1/C2 n = 0, tolerance = le^−^5 准备7种绘图颜色 intersectionPoint = []
Step4	迭代处理(De Casteljau subdivision)
	1) 分割曲线(deCasteljauSplit)： - 生成leftC1/rightC1, leftC2/rightC2 - 记录中间点midC1/midC2 2) 可视化分割过程(plotDeCasteljau)： - 绘制控制多边形 - 标记中间点(不同颜色)
Step5	子曲线相交检测
	1) 检查4种子组合(findIntersectingSubCurves)： leftC1 × leftC2/leftC1 × rightC2/rightC1 × leftC2/rightC1 × rightC2 2) 返回相交子对subC1/subC2及方向
Step6	收敛判断
	1) 计算曲线尺寸(checkConvergence) 2) 若max (sizeC1, sizeC2) < le^−^5： - 取中点作为交点 - 退出循环 否则： - 更新currentC1/C2 ← subC1/subC2 - n++
Step7	结果输出
	1) 绘制黄色五角星交点标记 2) 标注坐标值 3) 命令行输出坐标 + 迭代次数 4) C1，C2对应的参数t1，t2
辅助函数
bezierCurve	根据公式：$B\left(t\right)={\displaystyle \sum b_i{B}_{in}\left(t\right)}$ 计算曲线点
convexHullIntersect	分离轴定理：检查多边形在所有边法向量上的投影重叠
project	计算多边形在给定轴上的[minVal, maxVal]投影范围
deCasteljauSplit	递归分割控制点→返回左/右子曲线 + 3层中间点
plotDeCasteljau	可视化：控制多边形(虚线)、中间点(彩色)、连线
findIntersectingSubCurves	测试4种子曲线组合的凸包相交性
checkConvergence	判断曲线范围max(Δx, Δy)是否le^−^5

De Casteljau算法通过递归细分Bézier曲线，将求交问题转化为控制多边形检测：每次分割后，排除控制多边形不相交的子段，对可能相交的区间继续进行二分处理，直至逐步逼近曲线交点。这种分治策略利用曲线的特性，在保证一定精度的同时，显著减少算法所需的计算量。

De Casteljau算法作为一种基于几何特性的细分算法，在Bézier曲线求交问题上展现出显著优势。相较于代数法(受限于高次方程求解的数值稳定性)和传统细分法(效率受制于全局均匀细分) [4]，该算法采用二分策略：通过控制多边形检测快速剔除非交区域，显著提升计算效率；同时其递归细分过程自然保持几何精度，避免了代数方法的数值误差累积问题[5]。特别适合处理高次Bézier曲线的局部精确求交。相比之下，代数方法仅适用于低次曲线，牛顿迭代等数值方法则严重依赖初始值选取，而De Casteljau算法能够保持更高的数值稳定性和计算效率。

5. 数值实例

例1：给定两条三次Bézier曲线的控制顶点，分别为C1 = [0, 0; 1, 2; 3, 4; 4, 0]，C2 = [1, 3; 3, 2; 2, 3; 4, 4]，其具体图形为图1所示，经算法检测，两条曲线的凸包不相交，因此判定两条曲线不相交。

Figure 1. Two Bézier curves without intersection points

图1. 无交点的两条Bézier曲线

例2：给定两条三次Bézier曲线的控制顶点，分别为C1 = [0, 0; 2, 3; 5, 5; 0, 7]，C2 = [0, 5; 3, 2; 5, 3; 7, 5]，其具体图形为图2所示，经算法检测，两条曲线的凸包相交，进一步通过迭代分割检测，确认两条曲线的交点坐标。

Figure 2. Two Bézier curves with intersection points

图2. 有交点的两条Bézier曲线

在MATLAB后端运行算法，得到凸包相交处理信号，如图3所示；并获取最终Bézier曲线交点坐标，迭代次数及相交时C1 C2对应的参数t1、t2，如图4所示，整个过程流程图如图5所示。

Figure 3. Convex hull intersection and midpoint iteration diagram

图3. 凸包交集与中点迭代图

Figure 4. Bézier curve intersection and parameter diagram

图4. Bézier曲线交点及参数示意图

Figure 5. Flowchart

图5. 流程图

6. 结论

本文围绕基于迭代算法的Bézier曲线求交方法展开深入研究，以控制多边形的相交情况作为核心判断依据，构建出一套完整的求交策略。经研究发现，当Bézier曲线的控制多边形不相交时，曲线本身必然不相交，这一特性为快速筛选不相交曲线对提供了简洁高效的方法，有效避免了冗余计算，显著提升了处理大规模曲线数据时的前期筛选效率。针对控制多边形相交的情形，本文采用De Casteljau开展迭代运算。该方法以其简洁的逻辑和高效的运算过程，在众多测试案例中展现出良好的适应性。通过逐步逼近的策略，精准定位交点位置，在保证计算精度的同时，大幅减少了不必要的计算步骤。在与传统算法的对比实验中，基于De Casteljau算法的迭代求解策略在处理复杂曲线时，展现出更强的稳定性和更快的收敛速度，有力地证明了该方法在解决Bézier曲线求交问题上的有效性与优越性。然而，该方法也存在一定局限性。在处理具有极高阶数的Bézier曲线时，由于算法迭代次数增多以及浮点数运算精度损失的累积，计算效率会有所下降，且求交结果的准确性可能受到影响。此外，当曲线数量庞大且分布复杂时，控制多边形相交情况的判断开销会显著增加，进而对整体算法性能产生制约。未来研究可以考虑以下具体优化方向：在数值计算方面，可引入基于区间算术的自适应精度控制方法[6]，通过动态调整浮点运算精度来平衡高阶曲线的计算效率与准确性；同时结合误差补偿技术，减少迭代过程中的累积误差。在空间索引方面，可采用基于四叉树或BVH层次包围盒的空间划分结构，通过预计算建立空间索引来加速控制多边形的相交检测。此外，针对特定应用场景(如CAD图形处理)，可研究基于GPU并行计算的加速方案，利用CUDA等框架实现控制多边形相交判断的并行化处理。这些优化方案可以先通过MATLAB/Python进行算法验证，再使用C++进行性能优化，最终形成完整的优化解决方案。从而探索更高效的空间索引结构，改进控制多边形相交判断流程，以进一步拓展该方法的应用范围与性能表现。

基金项目

辽宁师范大学教师指导本科生科研训练项目(项目编号：JSZDBKSXM2024077)；

辽宁师范大学2025年大学生创新创业训练计划项目(项目名称：障通无阻，安全智行——基于有理Bézier曲线的自动驾驶智能避障规划系统研究及应用)。