如何计算直线和曲线的最近点？ ..还是曲线和曲线？
给定直线和二次贝塞尔曲线的点，如何计算它们的最近点？
Given the points of a line and a quadratic bezier curve, how do you calculate their nearest point?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（7）
INRIA 有一篇关于这个问题的科学论文：计算两条贝塞尔曲线之间的最小距离 (PDF 在此）
There exist a scientific paper regarding this question from INRIA: Computing the minimum distance between two Bézier curves (PDF here)
我曾经编写过一个工具来完成类似的任务。贝塞尔样条曲线通常是参数三次多项式。要计算三次线段和直线之间距离的平方，这只是两个多项式函数之间距离的平方，它本身就是另一个多项式函数！请注意，我说的是距离的平方，而不是平方根。
本质上，对于立方线段上的任何点，都可以计算从该点到直线的距离的平方。这将是一个六阶多项式。我们可以最小化这个距离的平方吗？是的。最小值必须出现在该多项式的导数为零的地方。所以微分，得到一个五阶多项式。使用您最喜欢的求根工具来生成所有数字根。詹金斯和特劳布，无论如何。从该组根中选择正确的解，排除任何复杂的解，并且仅选择位于相关立方段内的解。确保排除与距离的局部最大值相对应的点。
所有这些都可以有效地完成，并且除了多项式求根器之外不需要使用迭代优化器，因此不需要使用需要起始值的优化工具，仅寻找接近该起始值的解决方案。
例如，在 3-d 图中，我显示了由 3-d 中的一组点（红色）生成的曲线，然后我取了位于外部圆中的另一组点，我计算了内部最接近的点从每条曲线绘制一条线到该曲线。这些最小距离点是通过上述方案生成的。
I once wrote a tool to do a similar task. Bezier splines are typically parametric cubic polynomials. To compute the square of the distance between a cubic segment and a line, this is just the square of the distance between two polynomial functions, itself just another polynomial function! Note that I said the square of the distance, not the square root.
Essentially, for any point on a cubic segment, one could compute the square of the distance from that point to the line. This will be a 6th order polynomial. Can we minimize that square of the distance? Yes. The minimum must occur where the derivative of that polynomial is zero. So differentiate, getting a 5th order polynomial. Use your favorite root finding tool that generates all of the roots numerically. Jenkins & Traub, whatever. Choose the correct solution from that set of roots, excluding any solutions that are complex, and only picking a solution if it lies inside the cubic segment in question. Make sure you exclude the points that correspond to local maxima of the distance.
All of this can be efficiently done, and no iterative optimizer besides a polynomial root finder need be used, thus one does not require the use of optimization tools that require starting values, finding only a solution near that starting value.
For example, in the 3-d figure I show a curve generated by a set of points in 3-d (in red), then I took another set of points that lay in a circle outside, I computed the closest point on the inner curve from each, drawing a line down to that curve. These points of minimum distance were generated by the scheme outlined above.
我只是想给你一些提示，在 QBCurve // 段的情况下：
为了获得足够快的计算，我认为您应该首先考虑为您的算法使用一种“边界框”。
假设 P0 是 QB 曲线的第一个点，P2 是第二个点，P1 是控制点，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' ??? ETC
你很快就会得到准确的解决方案，比如 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 上的递归，曲线 1 上最近的点Curve2 是 D 或 F。如果我们停止两者的递归 ->返回距离 = 分钟（AD、AF、CD、CF）。那么如果我们在 T1 上有递归性，并且线段 AB 最近，则新 T1 变为： A'=AB= 曲线一的点，其中 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 参数。
请注意，距离（曲线，线段）只是该算法的一个特殊情况，您应该实现距离（三角形，三角形）和距离（线段，三角形）才能使其工作。玩得开心。
I just wanna give you a few hints, in for the case Q.B.Curve // segment :
to get a fast enough computation, i think you should first think about using a kind of 'bounding box' for your algorithm.
Say P0 is first point of the Q. B. Curve, P2 the second point, P1 the control point, and P3P4 the segment then :
Now if (and when) you need precision :
think about using a divide and conquer algorithm on the parameter of the curve :
which is nearest from P3P4 ?? P0P1' or P1'P2 ??? if it is P0P1' --> t is beetween 0 and 0.5 so compute Pm for t=0.25.
Now which is nearest from P3P4?? P0Pm or PmP1' ?? if it is PmP1' --> compute Pm2 for t=0.25+0.125=0.375 then which is nearest ? PmPm2 or Pm2P1' ??? etc
you will come to accurate solution in no time, like 6 iteration and your precision on t is 0.004 !! you might stop the search when distance beetween two points becomes below a given value. (and not difference beetwen two parameters, since for a little change in parameter, points might be far away)
in fact the principle of this algorithm is to approximate the curve with segments more and more precisely each time.
For the curve / curve case i would first 'box' them also to avoid useless computation, so first use segment/segment computation, then (maybe) segment/curve computation, and only if needed curve/curve computation.
For curve/curve, divide and conquer works also, more difficult to explain but you might figure it out. :=)
hope you can find your good balance for speed/accuracy with this :=)
Edit : Think i found for the general case a nice solution :-)
You should iterate on the (inner) bounding triangles of each B.Q.C.
So we have Triangle T1, points A, B, C having 't' parameter tA, tB, tC.
and Triangle T2, points D, E, F, having t parameter tD, tE, tF.
Initially we have tA=0 tB=0.5 tC= 1.0 and same for T2 tD=0, tE=0.5, tF=1.0
The idea is to call a procedure recursivly that will split T1 and/or T2 into smaller rectangles until we are ok with the precision reached.
The first step is to compute distance from T1 from T2, keeping track of with segments were the nearest on each triangle. First 'trick': if on T1 the segment is AC, then stop recursivity on T1, the nearest point on Curve 1 is either A or C. if on T2 the nearest segment is DF, then stop recursivity on T2, the nearest point on Curve2 is either D or F. If we stopped recursivity for both -> return distance = min (AD, AF, CD, CF). then if we have recursivity on T1, and segment AB is nearest, new T1 becomes : A'=A B= point of Curve one with tB=(tA+tC)/2 = 0.25, C=old B. same goes for T2 : apply recursivityif needed and call same algorithm on new T1 and new T2. Stop algorithm when distance found beetween T1 and T2 minus distance found beetween previous T1 and T2 is below a threshold.
the function might look like ComputeDistance(curveParam1, A, C, shouldSplitCurve1, curveParam2, D, F, shouldSplitCurve2, previousDistance) where points store also their t parameters.
note that distance (curve, segment) is just a particular case of this algorithm, and that you should implement distance (triangle, triangle) and distance (segment, triangle) to have it worked. Have fun.
1.简单的坏方法 - 通过迭代从第一条曲线逐点开始，从第二条曲线逐点开始并获得最小值
2.确定曲线间距离的数学函数和该函数的计算极限，如：
|Fcur1(t)-Fcur2(t)| ->0
Fs 是矢量。
我认为我们可以计算它的导数来确定极值并获得最近和最远的点，
我稍后会考虑这个问题，并发布完整的回复。
1.Simple bad method - by iteration go by point from first curve and go by point from second curve and get minimum
2.Determine math function of distance between curves and calc limit of this function like:
|Fcur1(t)-Fcur2(t)| ->0
Fs is vector.
I think we can calculate the derivative of this for determine extremums and get nearest and farest points
I think about this some time later, and post full response.
根据标准分析来表述您的问题：您有一个要最小化的量（距离），因此您为该量制定了一个方程，并找到一阶导数为零的点。通过使用曲线的参数
p来对单个参数进行参数化，该参数介于第一个点的 0 和最后一个点的 1 之间。在直线情况下，方程相当简单：从样条方程获取 x/y 坐标，并通过向量方程（与直线法线的标量积）计算到给定直线的距离。
在曲线的情况下，解析解可能会变得相当复杂。您可能想要使用数值最小化技术，例如 Nelder-Mead，或者，因为您有一个一维连续问题，所以使用简单的二分法。
Formulate your problem in terms of standard analysis: You have got a quantity to minimize (distance), so you formulate an equation for this quantity and find the points where the first derivatives are zero. Parameterize with a single parameter by using the curve's parameter
p, which is between 0 for the first point and 1 for the last point.In the line case, the equation is fairly simple: Get the x/y coordinates from the spline's equation and compute the distance to the given line via vector equations (scalar product with the line's normal).
In the curve's case, the analytical solution could get pretty complicated. You might want to use a numerical minimization technique such as Nelder-Mead or, since you have a 1D continuous problem, simple bisection.
对于贝塞尔曲线和直线的情况
距离直线最近的点有三个候选点：
测试所有三个；距离最短者获胜。
在两条贝塞尔曲线的情况下
取决于您是否想要精确的分析结果，或者优化的数值结果是否足够好。
分析结果
给定两条贝塞尔曲线A(t)和< em>B(s)，您可以导出其局部方向的方程 A'( t) 和B'(s)。 A'(t) = B'(< 的点对em>s）是候选者，即曲线局部平行的（t，s）。我没有检查过，但我假设 A'(t) - B'< /strong>(s) = 0 可以解析求解。如果您的曲线与示例中显示的曲线类似，则该方程应该只有一个解或没有解，但可能有两个（或者在曲线相同但平移的情况下有无限多个 - 在这种情况下）您可以忽略这一点，因为获胜者始终是曲线段端点之一）。
采用与上面的曲线案例概述类似的方法，测试每个点对以及曲线段端点。距离最短者获胜。
数值结果
假设两条贝塞尔曲线上的点定义为 A(t）和B（s）。您希望最小化距离 d( t, s) = |A (t) - B(s)|。这是一个简单的双参数优化问题：找到最小化 d( t, t, s 和 t >s)，约束条件 0 ≤ t ≤ 1 且 0 ≤ s ≤ 1。
由于 d = SQRT( ( xA - xB)² + (yA - yB)²)，您也可以最小化函数 f( t, s) = [d( t, s)]² 保存平方根计算。
对于此类优化问题，有许多现成的方法。挑选并选择。
请注意，在上述两种情况下，任何比二次贝塞尔曲线更高阶的东西都可以给您提供多个局部最小值，因此需要注意这一点。从您给出的示例来看，您的曲线似乎没有拐点，因此这种担忧可能不适用于您的情况。
In the case of a Bézier curve and a line
There are three candidates for the closest point to the line:
Test all three; the shortest distance wins.
In the case of two Bézier curves
Depends if you want the exact analytical result, or if an optimised numerical result is good enough.
Analytical result
Given two Bézier curves A(t) and B(s), you can derive equations for their local orientation A'(t) and B'(s). The point pairs for which A'(t) = B'(s) are candidates, i.e. the (t, s) for which the curves are locally parallel. I haven't checked, but I assume that A'(t) - B'(s) = 0 can be solved analytically. If your curves are anything like those you show in your example, there should be either only one solution or no solution to that equation, but there could be two (or infinitely many in the case where the curves identical but translated -- in which case you can ignore this because the winner will always be one of the curve segment endpoints).
In an approach similar to the curve-line case outline above, test each of these point pairs, plus the curve segment endpoints. The shortest distance wins.
Numerical result
Let's say the points on the two Bézier curves are defined as A(t) and B(s). You want to minimize the distance d( t, s) = |A(t) - B(s)|. It's a simple two-parameter optimization problem: find the s and t that minimize d( t, s) with the constraints 0 ≤ t ≤ 1 and 0 ≤ s ≤ 1.
Since d = SQRT( ( xA - xB)² + (yA - yB)²), you can also just minimize the function f( t, s) = [d( t, s)]² to save a square root calculation.
There are numerous ready-made methods for such optimization problems. Pick and choose.
Note that in both cases above, anything higher-order than quadratic Bézier curves can giver you more than one local minimum, so this is something to watch out for. From the examples you give, it looks like your curves have no inflexion points, so this concern may not apply in your case.
法线匹配的点是它们最近的点。我的意思是你画一条与该线正交的线。 .如果该线也与曲线正交，则交点是最近的点
The point where there normals match is their nearest point. I mean u draw a line orthogonal to the line. .if that line is orthogonal to the curve as well then the point of intersection is the nearest point