11

给定一条线和一条二次贝塞尔曲线的点，你如何计算它们最近的点？

在此处输入图像描述

4

7 回答 7

7

INRIA 有一篇关于这个问题的科学论文：计算两条贝塞尔曲线之间的最小距离（此处为 PDF）

于 2011-12-12T12:03:52.477 回答
6

我曾经写过一个工具来完成类似的任务。贝塞尔样条曲线通常是参数三次多项式。要计算立方线段和直线之间距离的平方，这只是两个多项式函数之间距离的平方，它本身就是另一个多项式函数！请注意，我说的是距离的平方，而不是平方根。

本质上，对于立方线段上的任何点，都可以计算从该点到线的距离的平方。这将是一个 6 阶多项式。我们可以最小化距离的平方吗？是的。最小值必须出现在多项式的导数为零的地方。所以区分，得到一个五阶多项式。使用您最喜欢的根查找工具，以数字方式生成所有根。詹金斯和特劳布，无论如何。从该组根中选择正确的解决方案，排除任何复杂的解决方案，并且仅选择位于相关立方段内的解决方案。确保排除与距离的局部最大值相对应的点。

所有这些都可以有效地完成，并且不需要使用除多项式根查找器之外的迭代优化器，因此不需要使用需要起始值的优化工具，只找到接近起始值的解决方案。

例如，在 3-d 图中，我显示了由 3-d 中的一组点生成的曲线（红色），然后我取另一组点在外面的圆圈中，我计算了内部最近的点从每个曲线，画一条线到该曲线。这些最小距离点是由上述方案生成的。

在此处输入图像描述

于 2011-12-12T14:37:04.987 回答
1

在贝塞尔曲线和直线的情况下

距离直线最近的点有三个候选：

  1. 贝塞尔曲线段上与直线平行的地方（如果存在这样的地方），
  2. 曲线段的一端，
  3. 曲线段的另一端。

测试所有三个；最短距离获胜。

在两条贝塞尔曲线的情况下

取决于您是否想要精确的分析结果，或者优化的数值结果是否足够好。

分析结果

给定两条贝塞尔曲线A ( t ) 和B ( s )，您可以推导出它们的局部方向A ' ( t ) 和B ' ( s ) 的方程。A ' ( t ) = B ' ( s )的点对是候选点，即曲线局部平行的 ( t , s )。我没有检查，但我假设A ' ( t ) - B ' ( s) = 0 可以解析求解。如果您的曲线与您在示例中显示的曲线相似，则该方程应该只有一个解或没有解，但可能有两个（或在曲线相同但平移的情况下无限多 - 在这种情况下您可以忽略这一点，因为获胜者将始终是曲线段端点之一）。

在类似于上述曲线案例大纲的方法中，测试这些点对中的每一个，以及曲线段端点。最短距离获胜。

数值结果

假设两条贝塞尔曲线上的点定义为A ( t ) 和B ( s )。你想最小化距离d ( t , s ) = | A ( t ) - B ( s )|。这是一个简单的两参数优化问题：在0 ≤ t ≤ 1 和 0 ≤ s ≤ 1的约束条件下，找到最小化d ( t , s ) 的s和t。

由于d = SQRT( ( xA - xB)² + (yA - yB)²)，您还可以最小化函数f ( t , s ) = [ d ( t , s )]² 以保存平方根计算。

对于此类优化问题，有许多现成的方法。挑选。

请注意，在上述两种情况下，任何比二次贝塞尔曲线更高阶的曲线都可以为您提供多个局部最小值，因此需要注意这一点。从您提供的示例中，您的曲线看起来没有拐点，因此这种问题可能不适用于您的情况。

于 2011-12-12T20:32:35.713 回答
1

1.简单的坏方法-通过迭代从第一条曲线逐点遍历并从第二条曲线逐点遍历并获得最小值 2.确定曲线之间距离的数学函数和该函数的计算极限，例如：

|Fcur1(t)-Fcur2(t)| ->0

Fs 是向量。

我认为我们可以计算它的导数以确定极值并获得最近和最远的点

一段时间后我会考虑这个问题，并发布完整的回复。

于 2011-12-12T12:00:41.653 回答
1

用标准分析来表述你的问题：你有一个要最小化的量（距离），所以你为这个量制定一个方程，并找到一阶导数为零的点。使用曲线的参数 使用单个参数进行参数化p，该参数介于第一个点的 0 和最后一个点的 1 之间。

在直线的情况下，方程相当简单：从样条方程中获取 x/y 坐标，并通过矢量方程（与直线法线的标量积）计算到给定直线的距离。

在曲线的情况下，解析解可能会变得非常复杂。您可能想要使用数值最小化技术，例如 Nelder-Mead，或者，因为您有一个一维连续问题，所以使用简单的二分法。

于 2011-12-12T12:05:09.490 回答
1

我只是想给你一些提示，例如 QBCurve // 段：为了获得足够快的计算，我认为你应该首先考虑为你的算法使用一种“边界框”。假设 P0 是 QB 曲线的第一个点，P2 是第二个点，P1 是控制点，P3P4 是段然后：

  1. 计算从 P0、P1、P2 到 P3P4 的距离
  2. 如果 P0 OR P2 是最近点 --> 这是曲线上离 P3P4 最近的点。结束：=）。
  3. 如果 P1 是最近点，而 Pi（i=0 或 1）是第二最近点，则 PiPC 和 P3P4 之间的距离是您寻找的距离的估计值，可能足够精确，具体取决于您的需要。
  4. 如果您需要更准确：计算 P1'，这是 QB 曲线上离 P1 最近的点：您会发现它应用了 t=0.5 的 BQC 公式。--> 从 PiP1' 到 P3P4 的距离是一个更准确的估计——但成本更高——。
  5. 请注意，如果由 P1P1' 定义的线与 P3P4 相交，则 P1' 是 QBC 离 P3P4 最近的点。
  6. 如果 P1P1' 不与 P3P4 相交，那么你运气不好，你必须走艰难的路......

现在，如果（以及何时）您需要精度：

考虑在曲线参数上使用分而治之算法：离 P3P4 最接近？P0P1' 或 P1'P2 ??? 如果是 P0P1' --> t 介于 0 和 0.5 之间，因此计算 t=0.25 的 Pm。现在哪个离P3P4最近？？P0Pm 或 PmP1' ?? 如果是 PmP1' --> 计算 Pm2 为 t=0.25+0.125=0.375 那么哪个最接近？PmPm2 或 Pm2P1' ??? 等等，您将立即得出准确的解决方案，例如 6 次迭代，您在 t 上的精度为 0.004 ！当两点之间的距离低于给定值时，您可能会停止搜索。（并不是两个参数之间的差异，因为对于参数的微小变化，点可能会很远）实际上该算法的原理是每次越来越精确地逼近曲线。

对于曲线/曲线情况，我会首先将它们“装箱”以避免无用的计算，因此首先使用段/段计算，然后（可能）使用段/曲线计算，并且仅在需要曲线/曲线计算时使用。

对于曲线/曲线，分而治之也有效，更难以解释，但您可能会弄明白。:=)

希望您能通过这个找到速度/准确性的良好平衡:=)

编辑：认为我在一般情况下找到了一个不错的解决方案:-) 你应该迭代每个 BQC 的（内部）边界三角形所以我们有三角形 T1，点 A、B、C 有 't' 参数 tA、tB、tC . 和三角形 T2，点 D、E、F，具有 t 参数 tD、tE、tF。最初我们有 tA=0 tB=0.5 tC= 1.0 和 T2 相同 tD=0, tE=0.5, tF=1.0 这个想法是递归调用一个过程，将 T1 和/或 T2 分割成更小的矩形，直到我们没问题达到精度。第一步是计算从 T1 到 T2 的距离，跟踪每个三角形上最近的线段。第一个“技巧”：如果在 T1 上的段是 AC，则在 T1 上停止递归，曲线 1 上的最近点是 A 或 C。如果在 T2 上最近的段是 DF，则在 T2 上停止递归，最近的点在曲线 2 为 D 或 F。如果我们停止两者的递归 -> 返回距离 = min (AD, AF, CD, CF)。那么如果我们在 T1 上具有递归性，并且段 AB 是最近的，则新 T1 变为：A'=AB= 曲线一的点，tB=(tA+tC)/2 = 0.25，C=old B. T2 也是如此：如果需要，应用递归并在新 T1 和新 T2 上调用相同的算法。当 T1 和 T2 之间的距离减去前一个 T1 和 T2 之间的距离低于阈值时停止算法。该函数可能看起来像 ComputeDistance(curveParam1, A, C, shouldSplitCurve1, curveParam2, D, F, shouldSplitCurve2, previousDistance) 其中点还存储它们的 t 参数。T2 也是如此：如果需要，应用递归性并在新 T1 和新 T2 上调用相同的算法。当 T1 和 T2 之间的距离减去前一个 T1 和 T2 之间的距离低于阈值时停止算法。该函数可能看起来像 ComputeDistance(curveParam1, A, C, shouldSplitCurve1, curveParam2, D, F, shouldSplitCurve2, previousDistance) 其中点还存储它们的 t 参数。T2 也是如此：如果需要，应用递归性并在新 T1 和新 T2 上调用相同的算法。当 T1 和 T2 之间的距离减去前一个 T1 和 T2 之间的距离低于阈值时停止算法。该函数可能看起来像 ComputeDistance(curveParam1, A, C, shouldSplitCurve1, curveParam2, D, F, shouldSplitCurve2, previousDistance) 其中点还存储它们的 t 参数。

请注意，距离（曲线，线段）只是该算法的一个特例，您应该实现距离（三角形，三角形）和距离（线段，三角形）以使其工作。玩得开心。

于 2011-12-12T13:31:37.800 回答
0

法线匹配的点是它们最近的点。我的意思是你画一条与这条线正交的线。.如果那条线也与曲线正交，那么交点就是最近的点

于 2011-12-12T11:43:45.913 回答