algorithm - 函数定义的两条曲线之间的最短距离

Question

我有两个函数在 2D 中描述两条曲线。

p1 = f1(t1)
p2 = f2(t2)

其中p1和p2是向量，t1和t2是标量，值在0.0到1.0之间.

曲线都是凸的，“肚皮”相对。它们可以旋转，并且可以定义新函数 y = h(x)，这样它们在 x 上的导数将单调递增/递减。

例子:

我正试图找到一种有效的算法来找到这些曲线之间的最小距离。

我认为，一种可能的方法是定义一个距离函数:

g(t1, t2) = |f1(t1) - f2(t2)|

然后使用 Newton's method 的泛化求解方程组

0 = ∂g(t1, t2)/∂t1    // partial derivative of g for t1
0 = ∂g(t1, t2)/∂t2    // partial derivative of g for t2

但是，我不确定这是否正确，而且这有点不方便，因为我需要 g 的一阶和二阶导数，我必须用数字计算它们。

是否有更简单、可能更快的算法来执行此操作？

Answer 1

如果你的曲线是平滑的，你可以尝试用圆弧来近似它们。这是通过沿曲线三倍采样点并检查中间点是否比它们形成的圆弧的给定公差更近来完成的。 (这是“曲线扁平化”的通用方法；您递归地进行)。

如果公差合理，弧的数量将相当适中(通常为 10-20)，您可以详尽地测试弧/弧距离。

查找“通过圆弧逼近三次贝塞尔曲线，反之亦然”以获得一些灵感。

---

为了便于说明，下图是利萨如曲线的三个离散化，公差分别为 2、0.5 和 0.125(对于 21、31 和 50 弧)。

与具有扁平化的相同曲线(相同公差，58、120 和 248 条线段)进行比较。