计算沿曲线均匀分布的点

Question

我使用这个方程来计算沿二次曲线的一系列点：

// Returns a point on a quadratic bezier curve with Robert Penner's optimization of the standard equation
result.x = sx + t * (2 * (1 - t) * (cx - sx) + t * (ex - sx));
result.y = sy + t * (2 * (1 - t) * (cy - sy) + t * (ey - sy));

遗憾的是，这些点分布不均匀，如下面的虚线渲染所示。曲线中间的点较密集，靠近边缘的点间隔更远。如何计算沿二次贝塞尔曲线均匀分布的点集？

请注意，我使用它来渲染虚线，因此 MATLAB 中的缓慢解决方案或其他方法将无法实现。我需要一个适合渲染器的快速解决方案。这不是为了研究或一次性计算！

编辑：我不是问如何完成上述任务。以上是我的渲染！我已经知道如何估计贝塞尔曲线的长度，计算点数等等。我需要的是一种更好的贝塞尔曲线点插值算法，因为我所计算的点沿曲线分布不均匀！

Answer 1

您想要生成二次贝塞尔曲线的等距（按弧长）细分。

所以你需要细分程序和计算曲线长度的函数。

求整条曲线的长度(

L

)，估计所需的线段数(

N

)，然后生成细分点，调整

t

参数得到长度约为

L/N

的Bezier线段

示例：您发现 L=100 并且想要 N=4 段。得到t=1/2，将曲线细分为两部分，得到第一部分的长度。如果长度 > 50，则减小 t 并再次细分曲线。重复（使用二分查找）直到长度值接近 50。记住 t 值并执行相同的过程，为曲线的前半部分和后半部分获取长度=25 的线段。

Answer 2

这种方法使用 THREE.js 库，这不在OP的问题中，但如果只是看看他们如何处理它可能会很有用：

  var curve = new THREE.QuadraticBezierCurve(
    new THREE.Vector2( -10, 0 ),
    new THREE.Vector2( 20, 15 ),
    new THREE.Vector2( 10, 0 )
);

  var points = curve.getSpacedPoints(numPoints);

Answer 3

我碰巧在一个项目中探索这个问题。我认为“MBo”上面的答案大部分是正确的，尽管计算成本很高

基于参数t的方法更容易计算，但不会产生均匀的距离。如果曲线有急转弯，那里的点会更密集（例如图中的曲线 C）。

需要注意的是，从 0 到 1 的参数 t 并不是所覆盖长度的分数。 事实上，以编程方式很难从给定的长度分数计算曲线上的点。

但是给定 t 值，您可以将原始曲线分成两部分，并计算它们的长度。所以解决办法就是反复按t分割，计算长度并调整t。

您可以编写近似方法，并为 100 个均匀间隔点的 0、0.01、0.02 等中的每个 t 调用它。但我认为运行时间太长了。

这就是我最终在我的案例中所做的事情。这是一个近似解，但很有效。在 t = 0.5 处递归分割曲线，然后分割左半部分和右半部分。直到每个段长度小于 5（像素）。当线段短于 5 个像素时，可以公平地假设它们是直线段。

现在您可以对长度的每个分数进行插值，例如 f（不要与 t 混淆）。因为每个分割点都有一个 f 值（到该点的长度除以总长度）。假设查询 f 分数落在两个连续分割点的两个 f 值 f1 和 f2 之间。

f1 => (x1, y1) // 已知

f' => ??

f2 => (x2, y2) // 已知

应用简单的线性插值来查找 f 处的坐标。这是一个 O(1) 的操作。您可以编写一个循环，通过扫描分割点以固定的 f 值间隔发射点。

---

附注我在 github 上检查了 THREE.js 源代码。 curve.getSpacedPoints 方法使用统一的 t 值。所以它并不是真正“均匀”间隔的。