C++如何实现通过指定n个坐标点生成路径的Spline样条曲线计算

要实现依次穿过所有给定坐标点的样条曲线，最常用的是三次参数样条插值方案，相比直接以x为自变量的样条，参数化方案可以避免x坐标重复出现时的计算异常，适配任意走向的路径。

实现步骤 #

• 输入校验：先校验输入的x、y坐标列表长度是否一致，且点的数量≥2，否则无法生成有效曲线。
• 格式转换：将std::list类型的坐标转为std::vector存储，方便后续随机访问元素。
• 参数化构造：引入参数t，采用弦长参数化方案给每个控制点分配对应t值：
  • 第一个控制点对应t=0
  • 后续每个控制点的t值 = 前一个t值 + 当前点与前一个点的欧氏距离
    这种参数化方式可以让曲线的采样密度和原始点的间距匹配，避免出现扭曲。
• 计算三次样条系数：分别对x(t)、y(t)两个维度做三次样条插值计算，每个分段[t_i, t_{i+1}]的三次多项式需要满足以下约束：
  1. 分段两端点的取值和对应控制点坐标一致
  2. 相邻分段的一阶导数连续
  3. 相邻分段的二阶导数连续
     边界条件默认可以选自然样条（曲线首尾端点的二阶导数为0），如果是封闭路径可以设置首尾一阶、二阶导数相等。
• 生成路径点集：按照你需要的路径采样密度，在t的取值范围内等步长采样，每个采样t值代入对应分段的三次多项式，计算得到对应的x、y坐标，存入结果即可。

代码实现 #

首先定义返回的Spline结构体，这里我们直接存储生成的路径点，也可以根据需求调整为存储样条系数方便后续动态采样：

#include <vector>
#include <list>
#include <cmath>

struct Spline {
    // 存储生成的路径点集，x、y为浮点型保证精度
    std::vector<std::pair<double, double>> path_points;
};

// 辅助函数：三次样条插值计算，输入参数t序列、对应的值序列，输出每个分段的三次多项式系数
std::vector<std::vector<double>> computeSplineCoeffs(const std::vector<double>& t, const std::vector<double>& vals) {
    int n = t.size() - 1;
    std::vector<double> h(n), a(n+1), l(n+1), mu(n+1), z(n+1), c(n+1), b(n), d(n);
    a = vals;
    
    for (int i = 0; i < n; i++) {
        h[i] = t[i+1] - t[i];
    }
    
    // 三对角矩阵求解
    for (int i = 1; i < n; i++) {
        l[i] = 2 * (h[i-1] + h[i]) - h[i-1] * mu[i-1];
        mu[i] = h[i] / l[i];
        z[i] = (3*(a[i+1] - a[i])/h[i] - 3*(a[i] - a[i-1])/h[i-1] - h[i-1] * z[i-1]) / l[i];
    }
    
    // 自然样条边界条件
    l[n] = 1;
    z[n] = 0;
    c[n] = 0;
    
    for (int j = n-1; j >= 0; j--) {
        c[j] = z[j] - mu[j] * c[j+1];
        b[j] = (a[j+1] - a[j])/h[j] - h[j]*(c[j+1] + 2*c[j])/3;
        d[j] = (c[j+1] - c[j])/(3*h[j]);
    }
    
    // 返回系数，每个分段对应[a_j, b_j, c_j, d_j]
    std::vector<std::vector<double>> coeffs(n, std::vector<double>(4));
    for (int i = 0; i < n; i++) {
        coeffs[i][0] = a[i];
        coeffs[i][1] = b[i];
        coeffs[i][2] = c[i];
        coeffs[i][3] = d[i];
    }
    return coeffs;
}

Spline CalculateSpline(std::list<int> x, std::list<int> y) {
    Spline result;
    int point_count = x.size();
    // 输入校验
    if (point_count != y.size() || point_count < 2) {
        return result;
    }
    
    // list转vector
    std::vector<double> x_vec(x.begin(), x.end());
    std::vector<double> y_vec(y.begin(), y.end());
    std::vector<double> t(point_count, 0);
    
    // 计算参数t
    for (int i = 1; i < point_count; i++) {
        double dx = x_vec[i] - x_vec[i-1];
        double dy = y_vec[i] - y_vec[i-1];
        t[i] = t[i-1] + sqrt(dx*dx + dy*dy);
    }
    
    // 分别计算x、y维度的样条系数
    auto x_coeffs = computeSplineCoeffs(t, x_vec);
    auto y_coeffs = computeSplineCoeffs(t, y_vec);
    
    // 生成路径点，这里设置每两个原始点之间采样10个点，可根据需求调整采样密度
    const int sample_per_segment = 10;
    for (int i = 0; i < point_count - 1; i++) {
        double t_start = t[i];
        double t_end = t[i+1];
        double step = (t_end - t_start) / sample_per_segment;
        for (int s = 0; s <= sample_per_segment; s++) {
            double current_t = t_start + s * step;
            double dt = current_t - t_start;
            // 代入三次多项式计算坐标
            double px = x_coeffs[i][0] + x_coeffs[i][1]*dt + x_coeffs[i][2]*dt*dt + x_coeffs[i][3]*dt*dt*dt;
            double py = y_coeffs[i][0] + y_coeffs[i][1]*dt + y_coeffs[i][2]*dt*dt + y_coeffs[i][3]*dt*dt*dt;
            result.path_points.emplace_back(px, py);
        }
    }
    
    return result;
}

效果示例 #

可选调整项 #

• 如果需要自定义边界的切线方向，可以把自然样条边界条件替换为夹紧样条，手动指定首尾点的一阶导数值。
• 如果是封闭路径，可以额外添加约束让首尾点的一阶、二阶导数相等，保证衔接处平滑。
• 采样密度可以根据实际需求调整sample_per_segment参数，数值越大生成的路径点越密集，曲线越平滑。

内容的提问来源于stack exchange，提问作者M. Abdul Rehman