基于数值法优化二次贝塞尔曲线路径点标记方案

问题背景 #

我尝试在二次贝塞尔曲线上按给定步长distance放置标记点，一开始写了个朴素实现，直接把弧长比例当成参数t来计算点，但发现标记点分布得乱七八糟——后来才反应过来，二次贝塞尔的t是时间参数，和弧长并非线性关系，相同t增量对应的弧长差不一样，直接映射肯定失效。

最初的代码是这样的：

const p = toPoint(map, points[section + 1]);
const p2 = toPoint(map, points[section]);
const {x: cx, y: cy} = toPoint(map, cp);
const ll1 = toLatLng(map, p),
ll2 = toLatLng(map, p2),
llc = toLatLng(map, { x: cx, y: cy });
const lineLength = quadraticBezierLength(
  ll1.lat,
  ll1.lng,
  llc.lat,
  llc.lng,
  ll2.lat,
  ll2.lng
);
for (let index = 0; index < Math.floor(lineLength / distance); index++) {
  const t = distance / lineLength;
  const markerPoint = getQuadraticPoint(
    t * index,
    p.x,
    p.y,
    cx,
    cy,
    p2.x,
    p2.y
  );
  const markerLatLng = toLatLng(map, markerPoint);

  markers.push(markerLatLng);
}

之前想过把曲线拆成大量小段，挨个计算弧长找接近目标的点，但这方法效率极低，哪怕从上次找到的点往后查找，速度还是没法看。

解决方案：用牛顿迭代法根据弧长反推参数t #

最实用的方案是用数值迭代（比如牛顿法）：给定目标弧长，反算出对应的t值，再代入贝塞尔公式计算坐标。这种方法迭代3-5次就能达到足够精度，复杂度极低。

具体步骤 #

1. 先计算整条曲线的总弧长，确定需要生成的标记点数量。
2. 实现一个函数，计算从t=0到任意t处的弧长。
3. 用牛顿迭代法，根据目标弧长不断修正t值，直到该t对应的弧长与目标弧长的误差足够小。
4. 遍历每个目标弧长（distance * index），求解对应的t，再计算坐标存入结果数组。

代码实现 #

1. 基础工具函数：计算切线和弧长

// 计算二次贝塞尔曲线在t处的切线向量（导数）
function getQuadraticDerivative(t, x0, y0, cx, cy, x1, y1) {
  const dx = 2 * (1 - t) * (cx - x0) + 2 * t * (x1 - cx);
  const dy = 2 * (1 - t) * (cy - y0) + 2 * t * (y1 - cy);
  return { dx, dy };
}

// 计算从t=0到t的弧长，用自适应辛普森积分保证精度和速度
function getArcLengthAtT(p0, cp, p1, t) {
  const x0 = p0.x, y0 = p0.y;
  const cx = cp.x, cy = cp.y;
  const x1 = p1.x, y1 = p1.y;

  // 被积函数：切线的长度
  const integrand = (t) => {
    const { dx, dy } = getQuadraticDerivative(t, x0, y0, cx, cy, x1, y1);
    return Math.sqrt(dx * dx + dy * dy);
  };

  // 自适应辛普森积分实现，直接用就行
  function adaptiveSimpson(a, b, eps, S, fa, fb, fc) {
    const c = (a + b) / 2;
    const d = (a + c) / 2;
    const e = (c + b) / 2;
    const fd = integrand(d);
    const fe = integrand(e);
    const Sleft = (c - a) * (fa + 4 * fd + fc) / 6;
    const Sright = (b - c) * (fc + 4 * fe + fb) / 6;
    const Snew = Sleft + Sright;
    if (Math.abs(Snew - S) <= 15 * eps) {
      return Snew + (Snew - S) / 15;
    }
    return adaptiveSimpson(a, c, eps / 2, Sleft, fa, fc, fd) +
           adaptiveSimpson(c, b, eps / 2, Sright, fc, fb, fe);
  }

  const fa = integrand(0);
  const fb = integrand(t);
  const fc = integrand(t / 2);
  const S = (t - 0) * (fa + 4 * fc + fb) / 6;
  return adaptiveSimpson(0, t, 1e-6, S, fa, fb, fc);
}

2. 牛顿迭代求解对应t值

// 根据目标弧长d，找到对应的二次贝塞尔参数t
function findTByArcLength(p0, cp, p1, targetD, totalLength) {
  if (targetD <= 0) return 0;
  if (targetD >= totalLength) return 1;

  // 初始猜测：用线性映射，接近真实值，加快收敛
  let t = targetD / totalLength;
  const eps = 1e-6; // 精度阈值，1e-6足够地图标记场景
  const maxIter = 10; // 最多迭代10次，一般3-5次就达标

  for (let i = 0; i < maxIter; i++) {
    const currentLength = getArcLengthAtT(p0, cp, p1, t);
    const { dx, dy } = getQuadraticDerivative(t, p0.x, p0.y, cp.x, cp.y, p1.x, p1.y);
    const derivative = Math.sqrt(dx * dx + dy * dy); // 弧长对t的导数，即切线长度

    // 牛顿迭代公式：修正t的值
    const delta = (currentLength - targetD) / derivative;
    t -= delta;

    // 限制t在0-1范围内，避免越界
    t = Math.max(0, Math.min(1, t));

    // 精度达标就停止迭代
    if (Math.abs(currentLength - targetD) < eps) {
      break;
    }
  }

  return t;
}

3. 生成标记点的主函数

// 主函数：输入二次贝塞尔三点p0, cp, p1，步长distance，返回标记点坐标数组
function generateMarkersByArcLength(p0, cp, p1, distance) {
  const markers = [];
  const totalLength = getArcLengthAtT(p0, cp, p1, 1);
  const count = Math.floor(totalLength / distance);

  for (let index = 1; index <= count; index++) {
    const targetD = distance * index;
    const t = findTByArcLength(p0, cp, p1, targetD, totalLength);
    // 计算t对应的二次贝塞尔点坐标
    const x = (1 - t)**2 * p0.x + 2 * (1 - t) * t * cp.x + t**2 * p1.x;
    const y = (1 - t)**2 * p0.y + 2 * (1 - t) * t * cp.y + t**2 * p1.y;
    markers.push({ x, y });
  }

  return markers;
}

方案优势 #

• 收敛快：初始值用线性映射，牛顿迭代通常3-5次就能达到要求精度，效率极高。
• 复杂度低：每个标记点的计算复杂度为O(1)（迭代次数固定），整体为O(n)，n为标记点数量，远优于分段查找的方法。
• 精度可控：通过eps参数调整精度，可根据场景灵活设置。

内容的提问来源于stack exchange，提问作者Igor Shmukler