Bezier交圆实现思路

实现思路总结

Bezier与圆求交可以转换为“求Bezier曲线上的所有距离圆的中心点等于圆半径的点”，即“求Bezier曲线上的所有离圆的距离为0的点”。

显然根据定义，这意味着这些点位于圆上，因此算作交点。

$$
\operatorname{dist}(B(t), c.centre) = r
$$

$$
\operatorname{dist}(B(t), c) = 0
$$

1. 构造`LUT`查找表

构造LUT表，存储Bezier曲线上一些离散点（数组下标经过处理对应参数，数组的值对应具体的点信息），即在Bezier曲线上采样点并存入LUT表内。

构造LUT表的目的：基于曲线上一些离散采样点的坐标来逐步寻找距离圆心为 r 的点（交点），进行粗略距离检查。

getLUT(numPoints, ctrlPoints, degree):
    Create an empty list LUT

    For i from 0 to numPoints - 1:
        t = i / (numPoints - 1)   // Calculate the parameter t
        p = EvaluateBezier(t, ctrlPoints, degree)  // Evaluate the Bezier curve at t
        Append p to LUT         // Add the point to the LUT

    return LUT

2. 计算`LUT`表的每一个点到圆的距离

此时关心的应该是distance_to_point(c.centre, LUT[i]) - r。

3. 寻找局部最小值

遍历LUT表的采样点，选取表中下标相邻的三个点（i、i-1、 i-2），检查这三个点到圆的距离在i-1处是否形成局部最小值，且i-1下标处的点到圆的距离是否在容差范围内。

3.1. 具体代码实现逻辑

已知圆心和半径以及 LUT，不妨给定一个start索引，通过查看LUT表的三个相邻下标（index 、 index-1、index-2）所对应的点来查找局部最小值。如果这三个下标对应的点到圆上的距离值恰好在index-1下标处形成最小值，且index-1下标处的点到圆的距离在容差范围内，则成功找到一个局部最优解，此时的index就是局部最小值的后一个下标。于是局部最小值的下标应该是index-1（因为循环变量是相对于start 的，故返回值为start+index ），然后将该局部最优值加入粗略交点集合内，作为一个候选交点。

findClosest(start, p, r, LUT):
    minimizedDistance = some very large number
    pd2 = LUT[start-2], if it exists. Otherwise use minimizedDistance
    pd1 = LUT[start-1], if it exists. Otherwise use minimizedDistance
    slice = LUT.subset(start, LUT.length)
    epsilon = the largest point-to-point distance in our LUT
    i = -1;

    for (coordinate, index) in slice:
        q = abs(dist(coordinate, p) - r);
        if pd1 less than all three values epsilon, pd2, and q:
            i = index - 1
            break

        minimizedDistance = min(q, minimizedDistance)
        pd2 = pd1
        pd1 = q

  return start + i

由于检查是一个相对于某个start的值，因此我们可能根本找不到另外的候选值；倘若在这种情况下返回start - 1（返回值初始设置为start - 1），就可以确定没有更多的局部最优解可供查找，便跳出循环。

p = our circle's center point
r = our circle's radius
d = some initially huge value
start = 0
values = []
do:
    i = findClosest(start, p, r, LUT)
    if i < start, or i>0 but the same as start: stop
    values.add(i);
    start = i + 2;

4.精细化交点参数

查找完所有的局部最优解之后，能够发现LUT[i]是比LUT[i-1]和LUT[i+1]更合适的解，但是在这两个值之间的其他地方可能有更好的解，所以便需要精细化查找。

精细化查找即找到两点（LUT[i-1]和LUT[i+1]两点）间离圆最近的一个点（找到LUT[i-1]点到LUT[i+1]点区间内的距离圆的距离的全局最小值）。

4.1. 具体代码实现逻辑

首先在LUT[i-1]和LUT[i+1]这两点之间取点采样，计算每个采样点到圆的距离，找出采样点的局部最小值（index、index-1、index-2，其中index-1为局部最小）做为候选点；

接着对每一个候选点两侧点作为边界的区间（index-1为局部最小的采样区间）通过三分法递归查找（精细化）该区间内部局部最小值，使其与圆最接近；将精细化后的采样区间局部最小值与LUT[i-1]点到LUT[i+1]点区间内的全局最小值比较，取小者赋值给新的全局最小值；

遍历完所有的候选采样点后就能得到LUT[i-1]点到LUT[i+1]点区间内的全局最小值。

三分法仅适合单峰函数，故对于多峰函数应结合多点采样和局部最小值检测，然后获得全局最优。

其中对于每个局部最小值，使用三分法或二次插值法进行局部细化

5.判断交点类型为切线交点或法线交点

6.找到满足容差要求的所有交点

代码实现流程

初始化：
- 通过dynamic_cast获取圆和Bezier曲线对象。
- 获取圆心坐标、半径，以及Bezier曲线的控制点和度数。
生成LUT：
- 通过getLUT生成Bezier曲线的查找表LUT。
查找最接近的交点：
- 在LUT中查找最接近圆的点，使用findClosest定位潜在的交点。
精细化搜索：
- 对查找的交点进行精细化，使用refineGlobalSearch各个对局部最小值进行细化。
计算交点和关系：
- 计算两条曲线上的交点参数。
- 根据交点的方向判断是否为切线交点或法线交点。
返回结果：
- 最后返回包含所有交点的链表curve_curve_int。

核心函数

answer_int_cur_cur：主函数，负责计算并返回圆与Bezier曲线的交点。
- 输入：两条曲线（Bezier和圆）
- 输出：所有交点的信息
- 流程：
  1. 获取圆的参数（圆心和半径）和Bezier曲线的控制点和度数。
  2. 生成Bezier曲线上的LUT。
  3. 调用findClosest查找最接近的交点，并利用refineGlobalSearch精细化交点的参数。
  4. 基于交点的方向判断它们的关系（切线或法线）。
evaluateBezier：通过De Casteljau算法计算Bezier曲线在某个参数t对应的点。
- 输入：参数t，控制点数组ctrlpts，Bezier曲线的度数degree。
- 输出：参数t处的Bezier曲线点。
refineTernarySearch：利用三分法对Bezier曲线进行精细化搜索。通过在指定区间内进行递归搜索，寻找最接近目标半径的交点。
- 输入：控制点数组ctrlpts，目标半径r，圆心p，LUT，Bezier曲线参数区间t1和t2，Bezier曲线度数degree，容差tol。
- 输出：细化后的Bezier曲线交点的参数。
refineGlobalSearch：在指定区间内采样，计算每个采样点到圆心的距离，并找出局部最小值。然后，调用函数refineTernarySearch对局部最小值进行三分法细化搜索，获取最终最小值。
- 输入：控制点数组ctrlpts，目标半径r，圆心p，LUT，Bezier曲线参数区间t1和t2，Bezier曲线度数degree，容差tol。
- 输出：细化后的最小值对应的参数。
findCloest：通过计算LUT上的每个点到圆的距离，来判断局部最小值，并以此找到Bezier曲线与圆的最接近交点。
- 输入：起始索引start，圆心circle，目标半径r，LUT，前两个采样点到圆的距离pd2和pd1，容差tol。
- 输出：最接近交点的索引。
getLUT：通过在参数区间（(0,1)）内均匀采样，生成Bezier曲线上的查找表LUT。LUT用于后续的细化搜索。
- 输入：采样点数量numPoints，控制点数组ctrlpts，Bezier曲线度数degree。
- 输出：LUT，包含Bezier曲线上的所有采样点。