根据距另一点的距离查找贝塞尔曲线上的点

Question

因此，我有一条 3D 三次贝塞尔曲线，并且在曲线上的任何位置都找到了一个起点，并且需要在曲线下方找到第二个点，该点距第一个点特定的世界空间距离（不是弧长距离）。

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

有什么想法吗？

Answer 1

唉，我不知道任何封闭式方程可以给你你想要的点。
也许近似该点的最简单技术是使用以下命令将贝塞尔曲线递归地分成 2 条较小的贝塞尔曲线
de Casteljau 算法。
当以下任一情况时，递归触底：
(a) 曲线的所有边界点都距离给定点太近或太远，或者
(b) 曲线的所有边界点都“足够接近”，等于所需的距离（也许它们都位于同一像素内）。

我非常确定给定贝塞尔曲线上与某个给定点的给定线性距离的最大点数是 4 个点。
（当给定的贝塞尔曲线具有自相交时，可能会发生这种情况）。

编辑：

也许我应该在回答之前阅读整个问题，是吗？
标准的“四点”贝塞尔曲线段可以看作是无限长的三次曲线的一段。在一个位置可能有弯曲、环路或尖点，但距离该锐曲线足够远，路径会变平，接近 2 条直线射线，每条直线都指向某个任意方向。
遗憾的是，上述解决方案只能找到短贝塞尔曲线段上的点。
我假设您想要沿着无限长三次曲线的点，这些点距给定点给定距离，即使它们不在短贝塞尔曲线段上。

== de Casteljau 反向 ==

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

== 零查找 ==

您可以从四点表示转换为三次多项式表示，并使用任何求根算法来收敛于所需点之一。
牛顿方法应该效果很好，因为贝塞尔曲线的短段几乎是直的。
我们能否将牛顿法方程改编为
查找点和三次样条之间的最小距离
对于这个问题？
为了简化描述，我将使用二分算法，尽管它的运行速度比牛顿方法慢。

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

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 )

此时，“right”值为t的值，B(right)为对应点，这样该点到原始给定点的距离就是（近似）给定距离。

Answer 2

您的问题陈述需要进一步完善。具体来说，当要求距起点 A 为 N 个单位的某个点 B 时，您受到的约束不足。可能有多个点距 A 为 N 距离。

除此之外，您还无法沿曲线以设定的间隔对曲线进行采样然后计算回到 A 的线性距离。这不是最佳的，但它可以工作。要处理 N 距离之外的多个点，您必须制定一条规则。可能就像发现的第一点一样简单。