如何计算一条直线和一个二次贝塞尔曲线之间的最近点？
7个回答
7
有一篇来自INRIA的科学论文涉及这个问题：计算两条贝塞尔曲线之间的最小距离（PDF在此）。
- Sebastian Dressler
2
有趣的是，这对于一对二次贝塞尔曲线来说可能有些过头了，而且对于一条二次贝塞尔曲线和一条直线来说肯定是过头了。 - Jean-François Corbett
也许这有点过头了，但是之前很难找到，现在容易多了 :D - Sebastian Dressler
6
我曾经写过一个工具来执行类似的任务。Bezier样条通常是参数化的三次多项式。要计算立方段与直线之间的距离平方，只需要计算两个多项式函数之间的距离平方，本身又是另一个多项式函数！请注意，我说的是距离的平方，而不是平方根。
实质上，对于立方体段上的任何点，都可以计算从该点到该线的距离的平方。这将是一个6阶多项式。我们能否最小化距离的平方？可以。最小值必须出现在该多项式的导数为零的地方。因此，求导得到一个5阶多项式。使用您喜欢的生成所有数字根的根查找工具。例如Jenkins＆Traub。从该根集中选择正确的解决方案，排除任何复杂的解决方案，并仅选择在问题立方体段内部的解决方案。确保排除对应于距离局部最大值的点。
所有这些都可以高效地完成，并且除了多项式根查找器之外，不需要使用任何迭代优化器，因此不需要使用需要起始值的优化工具，仅找到靠近该起始值的解决方案。
例如，在3-d图中，我展示了由3-d点集生成的曲线（以红色显示），然后我又取了另一个位于圆外的点集，从中计算出最接近内曲线的点，向下绘制一条直线到该曲线。上述方案产生了最小距离的点。
实质上，对于立方体段上的任何点，都可以计算从该点到该线的距离的平方。这将是一个6阶多项式。我们能否最小化距离的平方？可以。最小值必须出现在该多项式的导数为零的地方。因此，求导得到一个5阶多项式。使用您喜欢的生成所有数字根的根查找工具。例如Jenkins＆Traub。从该根集中选择正确的解决方案，排除任何复杂的解决方案，并仅选择在问题立方体段内部的解决方案。确保排除对应于距离局部最大值的点。
所有这些都可以高效地完成，并且除了多项式根查找器之外，不需要使用任何迭代优化器，因此不需要使用需要起始值的优化工具，仅找到靠近该起始值的解决方案。
例如，在3-d图中，我展示了由3-d点集生成的曲线（以红色显示），然后我又取了另一个位于圆外的点集，从中计算出最接近内曲线的点，向下绘制一条直线到该曲线。上述方案产生了最小距离的点。
- user85109
8
“不需要使用需要开始值的优化工具” ... 但是在一般情况下，根查找算法也需要一个初始值或范围！ - Jean-François Corbett
没有所谓的多项式根查找工具需要用户提供起始值，例如Jenkins和Traub算法。另一方面，可以将多项式根问题转化为特征值问题，然后使用特征值求解器计算根。 - user85109
在这种情况下，曲线是二次的，因此只有一个最小值（对于段端点有附加条件），因此是的，可以确保它将收敛到全局最小值，只要两个曲线的初始值为0<t<1。 - Jean-François Corbett
关于 Jenkins-Traub，我已经明白了。 - Jean-François Corbett
1你对于线段和曲线的情况的处理方法显然是正确的，但我不明白它如何扩展到曲线和曲线的情况，除非任意采样其中一条曲线并从每个采样点计算到另一条曲线的距离。这基本上是某种形式的优化。 - Jean-François Corbett
显示剩余3条评论
1
1. 简单的不好的方法 - 通过迭代从第一条曲线的点开始，然后从第二条曲线的点开始，并获得最小值。 2. 确定曲线之间距离的数学函数，并计算该函数的极限，如：
|Fcur1(t)-Fcur2(t)| ->0
Fs是向量。
我认为我们可以计算其导数以确定极值并获取最近和最远的点。
我稍后会考虑这个问题，并发布完整的回复。
- Vsevolod
1
将问题用标准分析术语表述：您需要最小化一个量（距离），因此您需要为该量制定一个方程，并找到一阶导数为零的点。通过使用曲线的参数p进行单参数化，该参数介于第一个点的0和最后一个点的1之间。
在直线情况下，方程相当简单：从样条曲线的方程中获取x/y坐标，并通过向量方程（与直线法线的数量积）计算到给定直线的距离。
在曲线情况下，解析解可能会变得非常复杂。您可能需要使用诸如Nelder-Mead之类的数值最小化技术，或者由于您有一个1D连续问题，可以使用简单的二分法。
- thiton
1
我只想给你一些提示，针对 Q.B.Curve // segment 的情况： 为了获得足够快的计算速度，我认为你应该首先考虑使用某种“边界框”算法。 假设 P0 是 Q.B. Curve 的第一个点，P2 是第二个点，P1 是控制点，P3P4 是线段，则：
- 计算P0、P1、P2到P3P4的距离
- 如果P0或P2是最近的点 -> 这是曲线从P3P4到最近点。结束 :=)。
- 如果P1是最近的点，而Pi（i=0或1）是第二近的点，则在PiPC和P3P4之间的距离是您所寻求的距离的估计值，具体取决于您的需求。
- 如果需要更准确：计算P1'，它是从P1到Q.B.曲线上最近的点：使用t = 0.5应用BQC公式找到它。-> PiP1'到P3P4的距离是一个更准确的估计值，但成本更高。
- 请注意，如果由P1P1'定义的直线与P3P4相交，则P1'是QBC距离P3P4最近的点。
- 如果P1P1'不与P3P4相交，则您就没有运气了，必须走艰难的路线...
现在，如果（并且当）您需要精度：
考虑在曲线参数上使用分治算法： P3P4 最近的是哪个？ P0P1' 还是 P1'P2？如果是 P0P1'，则 t 在 0 和 0.5 之间，因此计算 t=0.25 时的 Pm。 现在 P3P4 最近的是哪个？ P0Pm 还是 PmP1'？如果是 PmP1'，则计算 t=0.25+0.125=0.375 时的 Pm2，然后最近的是哪个？PmPm2 还是 Pm2P1'？等等。 你将很快得到准确的解决方案，大约需要 6 次迭代，t 的精度为 0.004！当两点之间的距离低于给定值时，可以停止搜索（而不是两个参数之间的差异，因为对于参数的微小变化，点可能相距很远）。 实际上，这种算法的原理是每次更加精确地用线段逼近曲线。对于曲线/曲线情况，我首先会将它们“装箱”，以避免无用的计算，因此首先使用线段/线段计算，然后（可能）使用线段/曲线计算，只有在必要时才使用曲线/曲线计算。
对于曲线/曲线，分治法也可以解决，但更难解释，不过你可能会想出来。:=)
希望你能在速度/准确性方面找到良好的平衡。:=)
编辑：我想我找到了一个通用的好方法 :-) 您应该迭代每个B.Q.C.的（内部）边界三角形。 因此，我们有三角形T1，点A、B、C，具有参数tA、tB、tC。 和三角形T2，点D、E、F，具有参数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'=A B=曲线一上的点，tB=(tA+tC)/2=0.25，C=旧的B。对于T2也是如此：如果需要递归，则应用递归，并在新的T1和新的T2上调用相同的算法。当T1和T2之间找到的距离减去先前T1和T2之间找到的距离低于阈值时停止算法。 该函数可能类似于ComputeDistance(curveParam1, A, C, shouldSplitCurve1, curveParam2, D, F, shouldSplitCurve2, previousDistance)，其中点还存储其t参数。
请注意，距离（曲线、线段）只是此算法的一个特例，您应该实现距离（三角形、三角形）和距离（线段、三角形）以使其正常工作。玩得开心。- GameAlchemist
1
在贝塞尔曲线和直线的情况下
有三个候选点是最接近直线的：
- 贝塞尔曲线段上与直线平行的位置（如果存在这样的位置），
- 曲线段的一端，
- 曲线段的另一端。
测试所有三个；最短距离获胜。
在两个贝塞尔曲线的情况下
取决于您是否需要精确的分析结果，或者优化的数值结果已经足够好。
分析结果
给定两个贝塞尔曲线A(t)和B(s)，您可以推导出它们的本地方向A'(t)和B'(s)的方程。使A'(t) = B'(s)的点对是候选点，即使曲线在本地上平行的(t, s)。我没有检查过，但我认为可以解析地解决A'(t) - B'(s) = 0。如果您的曲线与您在示例中显示的曲线类似，那么该方程应该只有一个解或没有解，但可能会有两个解（或在曲线相同但平移时可能有无限多的解——在这种情况下，您可以忽略这一点，因为获胜者总是其中一个曲线段的端点）。采用与上述曲线线段情况类似的方法，测试这些点对以及曲线段端点。最短距离胜出。
数值结果
假设两个 Bézier 曲线上的点定义为A(t)和B(s)。您想要最小化距离d(t,s)=|A(t)-B(s)|。这是一个简单的二参数优化问题：找到最小化d( t, s)的s和t，并满足约束条件0 ≤ t ≤ 1和0 ≤ s ≤ 1。
由于 d = SQRT( ( xA - xB)² + (yA - yB)²)，您还可以通过最小化函数 f( t, s) = [d( t, s)]² 来避免平方根计算。
有许多现成的方法可供选择来解决这类优化问题。
请注意，在上述两种情况中，高于二次贝塞尔曲线的任何东西都可能会给您带来不止一个局部最小值，因此这是需要注意的。根据您提供的示例，看起来您的曲线没有反曲点，因此这种担忧可能不适用于您的情况。
- Jean-François Corbett
0
法线相交的点是它们最近的点。我的意思是你画一条垂直于该线的线。如果该线也垂直于曲线，那么交点就是最近的点。
- led_apprentice
1
对于示例1、4、5和8，这不是真的，因为曲线在那里被截断了。此外，这是一个必要条件，但不充分，因为最远点也将具有正交法线。 - thiton
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接