如何计算线条和曲线的最近点？ ..或曲线和曲线？

Question

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

Answer 1

我只是想给你一些提示，在案例Q.B.Curve //段： 得到一个足够快的计算，我想你应该首先考虑为你的算法使用一种'边界框'。 说P0是QB曲线，P2与第二点，P1的控制点，和P3P4线段然后的第一点：从P0

1. 计算距离，P1，P2到P3P4
2. 如果P0 OR P2是最近点 - >这是来自P3P4曲线的最近点。结束：=）。
3. 如果P1是最近点，并且Pi（i = 0或1）是第二个最近点，PiPC和P3P4之间的距离是您寻求的距离的估计值，可能根据您的需要足够精确。
4. 如果您需要更精确：计算P1'，这是Q.B.曲线上离P1最近的点：您发现它应用了t = 0.5的BQC公式。 - >距离PiP1'到P3P4的距离是一个更准确的估计 - 但成本更高 - 。
5. 请注意，如果由P1P1'定义的线与P3P4相交，则P1'是距P3P4最近的QBC点。
6. 如果P1P1' 不相交P3P4，那么你的运气了，你必须去艰难地...

现在，如果（当），你需要精度：

思考使用曲线参数上的分治算法： 它离P3P4最近？ P0P1'或P1'P2如果它是P0P1'→t在0和0.5之间，那么计算P = t = 0.25。 现在哪个离P3P4最近？ P0Pm或PmP1'？如果是PmP1' - >在t = 0.25 + 0.125 = 0.375时计算Pm2，那么哪个最接近？ 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分成更小的矩形，直到我们对于达到的精度是可以的。 第一步是计算从T2到T1的距离，并跟踪每个三角形上距离最近的线段。第一个“技巧”：如果在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的曲线1的点，C =在新的T1和新的T2上应用递归性，并调用相同的算法。当在T1和T2之间发现的距离减去在先前的T1和T2之间发现的距离低于阈值时停止算法。 函数可能看起来像ComputeDistance（curveParam1，A，C，shouldSplitCurve1，curveParam2，D，F，shouldSplitCurve2，previousDistance），其中点也存储它们的t参数。

请注意，距离（曲线，段）只是该算法的特定情况，并且您应该实现距离（三角形，三角形）和距离（段，三角形）以使其有效。玩的开心。

Answer 2

的地步，有正常人的比赛是他们最近点。我的意思是你画一条与该线正交的线。如果该线与曲线正交，则交点为最近点

Answer 3

1.简单的方法 - 通过迭代从第一条曲线开始逐点并从第二条曲线开始，然后得到最小值 2 。确定曲线之间距离的数学函数和此函数的计算极限：

| Fcur1（t）-Fcur2（t）| - > 0

Fs是矢量。

我认为，我们可以计算出本作确定的极值，并得到最近和farest点

我想想这一段时间后，产后全响应的衍生物。

Answer 4

存在着关于从INRIA这个问题上的科学论文：Computing the minimum distance between two Bézier curves（PDF here）

Answer 5

制定你的问题的标准分析方面：你已经有了一个数量减少（距离），所以你制定这样的一个公式数量并找到一阶导数为零的点。通过使用曲线的参数p，使用单个参数进行参数化，该参数在第一点0和最后一点1之间。

在线情况下，该方程非常简单：从样条线方程中获取x/y坐标，并通过向量方程计算与给定线的距离（标量乘以线的法线）。

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

Answer 6

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

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

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

例如，在三维图中，我显示了一组由三维点组成的曲线（用红色表示），然后我拿了另外一组位于外部圆的点，我计算了最接近指向每条曲线的内部曲线，绘制一条直线到该曲线。这些最小距离点由上述方案产生。

Answer 7

在贝塞尔曲线的情况下和一个线

有三个候选人的最近点到行：

1. 对贝塞尔曲线段中的位置即与该线平行（如果存在这样的地方），
2. 曲线段的一端，
3. 曲线段的另一端。

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

二贝塞尔曲线

的情况下，如果你想确切的分析结果，或者优化的数值结果是足够好赖。

分析结果

给定两个贝塞尔曲线一个（吨）和乙（小号），你可以得到方程的局部定向A'（t）和B'（s）。点对为其甲 '（吨）= 乙'（小号）是候选，即（吨，小号）该曲线是局部平行。我没有检查，但我假定甲 '（吨） - 乙'（小号）= 0可以解析地求解。如果您的曲线与您在示例中显示的曲线相似，则该方程式应该只有一个解或者没有解，但可能有两个（或者在曲线相同但翻译的情况下无限多） - 在这种情况下你可以忽略它，因为赢家将始终是曲线段端点之一）。

在类似于上述曲线轮廓大纲的方法中，测试每个点对，再加上曲线段端点。最短距离获胜。

数值结果

假设在两个Bézier曲线的点被定义为甲（吨）和乙（小号）。您想最小化距离d（t,s）= | 甲（吨） - 乙（小号）|。这是一个简单的双参数的优化问题：找到小号和吨，最大限度地减少d（吨，小号）与约束0≤吨≤1和0≤小号≤1 。

由于d = SQRT（（XA - 的xB）2 +（YA - YB）²），也可以只是最小化函数˚F（吨，小号）= [d（t,s）]²保存平方根计算。

对于这样的优化问题有numerous ready-made methods。挑选。

---

注意，在上述两种情况下，任何高阶比二次贝塞尔曲线可以送礼者你比一个极小，所以这是值得提防。从你给的例子看，你的曲线看起来没有拐点，所以这个问题可能不适用于你的情况。