两条曲线的函数定义下，它们之间的最短距离是多少？

Question

两条曲线的函数定义下，它们之间的最短距离是多少？

4

我有两个函数描述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)|

然后使用牛顿法的一般化方法来解决方程组。

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

但是，我不确定这是否正确，而且有点不方便，因为我需要计算g的一阶和二阶导数，这需要进行数值计算。

是否有更简单、可能更快的算法来完成这个任务？

- alain

你能加上一张图吗？我猜你是指两个曲线。直线是笔直的（这会让问题变得相当无聊）。我也不确定你所说的向量“p1”和“p2”是什么意思。 - Vincent van der Weele

曲线不能是凸的。问题可以。而你的问题是否是凸的，取决于这些曲线。你对它们了解多少？ - Nico Schertler

2

那么你的问题不是凸的。你的问题表述非常合理（出于性能原因，只需去掉平方根）。然后使用任何最小化算法（例如梯度下降、牛顿、共轭梯度、沿主轴交替优化）。根据你的初始化和问题的“恶劣程度”，你应该考虑一些可以处理非凸问题的方法，例如Levenberg-Marquardt、模拟退火、BFGS。 - Nico Schertler

@YvesDaoust 是的，其中一些方法肯定是。我猜一些更简单的方法就足够了。至少在实践中是这样的。但它们不能提供理论保证，即它们将找到全局最小值。 - Nico Schertler

@NicoSchertler：你提到的方法都不能保证收敛，特别是模拟退火算法，它纯粹是一种启发式方法。我猜测通过利用目标函数的平滑性（Lipschitz条件？），应该可以导出带有保证收敛的方法，并构造函数值的括号。 - user1196549

显示剩余5条评论

2个回答

1

问题类似于在区域0<=x<=1和0<=y<=1上找到z的最小值，其中z是|误差|，x是t1，y是t2。

建议使用z=pow(f1(t1)-f2(t2),2)而不是|f1(t1)-f2(t2)|，因为它具有更平滑的特性，并寻找最小值。

由于f1(t1)和f2(t2)的特性似乎没有受到严格控制，建议在二维中进行二分搜索，如https://dev59.com/jlnUa4cB1Zd3GeqPedYu#6910155或https://dev59.com/jlnUa4cB1Zd3GeqPedYu#6909573。

- chux - Reinstate Monica

根据 OP 的绘图，可能存在多个解决方案。 - chux - Reinstate Monica

谢谢 +1。我一直认为只有一个最短距离，为什么你说可能有多个解决方案？ - alain

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - chux - Reinstate Monica

好的，现在我明白了。我只需要距离，所以如果曲线重叠，返回0.0就足够了。 - alain

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- user1196549 · Accepted Answer

如果您的曲线平滑，您可以尝试用圆弧来逼近它们。这可以通过沿着曲线抽样点三元组并检查中间点是否与形成的圆弧保持足够接近（这是“曲线展平”的一种通用方法；您可以递归地执行它）。

如果容差合理，弧的数量将相当适度（通常为10-20），您可以进行穷举式的弧/弧距离测试。

查找“APPROXIMATION OF A CUBIC BEZIER CURVE BY CIRCULAR ARCS AND VICE VERSA”以获得灵感。

为了说明，下面的图表显示了Lissajous曲线的三个离散化版本，容差分别为2、0.5和0.125（对应21、31和50个圆弧）。

与展平后的相同曲线进行比较（相同容差，58、120和248个线段）。