根据与另一个点的距离在bezier曲线上查找点

Question

因此，我有一条3D三次bezier曲线，并在曲线的任何位置找到一个起点，需要在曲线下方找到第二个点，该点离第一个点有特定的世界空间距离(而不是弧长距离)。

另一个问题是，如果第二个点到达曲线的末端，但仍然不在期望的世界空间距离，在这种情况下，我希望它沿着切线继续，直到达到距离。

有什么想法吗？

Answer 1

遗憾的是，我不知道有什么封闭形式的方程式能给你想要的点。也许接近这一点的最简单的技术是使用de Casteljau's algorithm递归地将贝塞尔曲线切成两条较小的贝塞尔曲线。当(a)曲线的所有边界点都离给定点太近或太远，或者(b)曲线的所有边界点都“足够接近”到等于所需的距离(可能它们都适合同一个像素)时，递归就会触底。

我非常确定给定Bezier曲线上到某给定点的给定线性距离的最大点数是4点。(当给定的Bezier曲线具有自交点时，可能会发生这种情况。)

编辑：

也许我应该先读完整个问题，然后再开始回答，对吗？标准的“四点”贝塞尔曲线段可以看作是无限长的三次曲线的一部分。在一个位置可能有一个弯曲或环或尖点，但距离该尖锐曲线足够远的地方，路径会变平，接近两条直线，每条直线都指向某个任意方向。遗憾的是，上面的解决方案只查找短Bezier曲线线段上的点。我假设你想要沿着无限长的三次曲线的点，这些点离给定点的距离是给定的，即使它们不在短贝塞尔曲线线段上。

反向==中的== de Casteljau

你可以反向运行(递归中点) de Casteljau的算法，在每次迭代中生成一个新的四点Bezier曲线，该曲线的大小是上一个贝塞尔曲线的“两倍”，直到你得到一个足够大的曲线来包含所需的点。(当所有4个初始点都离给定点“太近”时，则保证加倍最终会产生起点“太近”、终点“太远”的曲线段，然后可以使用上面的算法收敛到距给定点所需距离的点上)。这种方法只依赖于加、减、乘2和求平均，因此原则上它在数值上应该是相对健壮的。(它从不在任何位置t实际计算立方公式)。

==找零==

您可以将四点表示法转换为三次多项式表示法，并使用任何求根算法来收敛到所需的点之一。牛顿的方法应该工作得很好，因为贝塞尔曲线的短段几乎是直的。我们能把Finding the Minimum Distance Between a Point and a Cubic Spline中的牛顿法方程应用到这个问题上吗？为了简单起见，我将使用二分法，尽管它的运行速度比牛顿的方法慢。

与往常一样，三次Bezier曲线段可以描述为

B(t) = (1-t)^3 * P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3.

(不幸的是，这个等式在数值上并不总是健壮的--这就是为什么许多人使用递归减半来代替de Casteljau的算法)。

我假设您已经(或可以找到)给定点的t_given值，

x_given = B(t_given).x
y_given = B(t_given).y

给定的点与曲线上的其他点之间的距离由毕达哥拉斯定理给出，

distance2(t) = ( x_given - B(t).x )^2 + ( y_given - B(t).y )^2.
distance(t) = sqrt(distance2(t)).

您要查找的点位于函数的零点

given_distance2 = given_distance^2.
f(t) = distance2(t) - given_distance2.

假设给定的距离不是零，并且给定点的t_given < 1，则对分算法将运行如下所示

left = t_given
right = 1 // the endpoint of the given Bezier curve segment
while( distance2(right) < given_distance2 ){
    right = right*2
}

此时，t_left比所需距离更接近给定点，而t_right比所需距离更远(或者可能完全相等)。由于我们有一个点太近，另一个点太远，二等分算法应该可以工作。

while( (abs(f(right) is too big) AND (abs(left - right) is too big) ){
    // find midpoint
    midpoint = (t_left + t_right)/2

接下来，我们检查:第一个段left...midpoint是否包含零或midpoint...right？

    if( f(left)*f(midpoint) < 0 ) then
        // throw away right half
        right = midpoint
    else
        // throw away left half
        left = midpoint
}

return( right )

在这一点上，“右”值是t的值，B(右)是相应的点，这样从该点到原始给定点的距离(大约)是给定的距离。

Answer 2

你的问题陈述需要更多的改进。具体地说，当请求距起点A N个单位的某个点B时，您会受到欠约束。可能有多个点与A的距离为N。

抛开这一点不谈，是什么阻止你在曲线上以设定的间隔采样曲线，然后计算回A的线性距离。这不是最优的，但它会起作用。要处理N个距离之外的多个点，您必须制定一条规则。可能和找到的第一个点一样简单。