在一点处分割三次贝塞尔曲线 [英] Split a cubic Bézier curve at a point

问题描述

此问题和这个问题都展示了如何沿着曲线沿特定的参数化值0≤ t ≤1分割三次贝塞尔曲线，从而由两个新的分段组成原始曲线形状.我需要沿着我知道的坐标的曲线的点分割我的贝塞尔曲线，而不是对该点的参数化值 t 进行分割.

This question and this question both show how to split a cubic Bézier curve at a particular parameterized value 0 ≤ t ≤ 1 along the curve, composing the original curve shape from two new segments. I need to split my Bézier curve at a point along the curve whose coordinate I know, but not the parameterized value t for the point.

例如，考虑使用Adobe Illustrator，用户可以在其中单击曲线以将点添加到路径中，而不会影响路径的形状.

假设我找到曲线上最接近用户点击位置的点，如何从中计算控制点这?给定曲线上的一个点，是否有公式可以分割贝塞尔曲线?

Assuming I find the point on the curve closest to where the user clicks, how do I calculate the control points from this? Is there a formula to split a Bézier curve given a point on the curve?

或者给定曲线上的一个点，并且(不太希望如此)，有一种方法可以确定与该点相对应的参数化值 t (不是在二进制搜索中使用De Casteljau的算法)?

Alternatively (and less desirably), given a point on the curve, is there a way to determine the parameterized value t corresponding to that point (other than using De Casteljau's algorithm in a binary search)?

我的Bézier曲线恰好是2D的，但是一个很好的答案将包括应用在任意尺寸上的矢量数学.

推荐答案

无需使用De Casteljau的算法即可确定曲线上某个点的参数值，甚至可能更简单，但是您将不得不使用启发式方法找到一个好的起始值，然后近似地估算结果.

It is possible, and perhaps simpler, to determine the parametric value of a point on the curve without using De Casteljau's algorithm, but you will have to use heuristics to find a good starting value and similarly approximate the result.

一种可能且相当简单的方法是使用牛顿方法，例如:

One possible, and fairly simple way is to use Newton's method such that:

t _{n + 1} = t _n -(b _x (t _n )-c _x )/b _x '(t _n )

t_n+1 = t_n - ( b_x(t_n) - c_x ) / b_x'(t_n)

其中 b _x (t)指代多项式形式的贝塞尔曲线的 x 分量，其中控制点 x ₀ ， x ₁ ， x ₂ 和x ₃ ， b _x '(t)是一阶导数， c _x 是曲线上的一个点，使得:

Where b_x(t) refers to the x component of some Bezier curve in polynomial form with the control points x₀, x₁, x₂ and x₃, b_x'(t) is the first derivative and c_x is a point on the curve such that:

c _x = b _x (t)|0 ＜t ＜1

c_x = b_x(t) | 0 < t < 1

b _x (t)的系数为:

the coefficients of b_x(t) are:

A = -x ₀ + 3x ₁ -3x ₂ + x ₃
B = 3x ₀ -6x ₁ + 3x ₂
C = -3x ₀ + 3x ₁
D = x ₀

A = -x₀ + 3x₁ - 3x₂ + x₃
B = 3x₀ - 6x₁ + 3x₂
C = -3x₀ + 3x₁
D = x₀

和:

b _x (t)= At ³ + Bt ² + Ct + D，
b _x '(t)= 3At ² + 2Bt + C

b_x(t) = At³ + Bt² + Ct + D,
b_x'(t) = 3At² + 2Bt + C

现在，找到适合牛顿方法的良好起始值是棘手的部分.对于大多数不包含环或尖点的曲线，您可以简单地使用公式:

Now finding a good starting value to plug into Newton's method is the tricky part. For most curves which do not contain loops or cusps, you can simply use the formula:

t _n =(c _x -x ₀ )/(x ₃ -x ₀ )|x ₀ <x ₁ <x ₂ <x ₃

t_n = ( c_x - x₀ ) / ( x₃ - x₀ ) | x₀ < x₁ < x₂ < x₃

现在您已经拥有:

b _x (t _n )≈c _x

b_x(t_n) ≈ c_x

因此，对于 c _x ，应用牛顿方法的一个或多个迭代将更好地逼近 t .

请注意，Newton Raphson算法具有二次收敛性.在大多数情况下，良好的起始值将导致两次迭代(即少于半个像素)后的改善可忽略不计.

Note that the Newton Raphson algorithm has quadratic convergence. In most cases a good starting value will result in negligible improvement after two iterations, i.e. less than half a pixel.

最后，值得注意的是三次贝塞尔曲线具有通过找到一阶导数的根来找到极值的精确解.因此，可以将有问题的曲线在其极值处再细分，以去除环或尖点，然后通过分析所讨论的结果截面，可以获得更好的结果.以这种方式细分三次方将满足上述约束.

Finally it's worth noting that cubic Bezier curves have exact solutions for finding extrema via finding roots of the first derivative. So curves which are problematic can simply be subdivided at their extrema to remove loops or cusps, then better results can be obtained by analyzing the resulting section in question. Subdividing cubics in this way will satisfy the above constraint.

这篇关于在一点处分割三次贝塞尔曲线的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！