如何计算直线和曲线的最近点? ..还是曲线和曲线? [英] How to calculate the nearest point of a line and curve? .. or curve and curve?

问题描述

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

Given the points of a line and a quadratic bezier curve, how do you calculate their nearest point?

推荐答案

我只想给您一些提示，就Q.B.曲线////段而言: 为了获得足够快的计算，我认为您首先应该考虑对算法使用一种边界框". 假设P0是Q.B.曲线的第一个点，P2是第二个点，P1是控制点，P3P4是该段，则:

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 :

1. 计算从P0，P1，P2到P3P4的距离
2. 如果P0或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'是QBC与P3P4的最接近点.
6. 如果P1P1'不与P3P4相交，那么您就不走运了，您必须走艰难的路...

1. Compute distance from P0, P1, P2 to P3P4
2. if P0 OR P2 is nearest point --> this is the nearest point of the curve from P3P4. end :=).
3. if P1 is nearest point, and Pi (i=0 or 1) the second nearest point, the distance beetween PiPC and P3P4 is an estimate of the distance you seek that might be precise enough, depending on your needs.
4. if you need to be more acurate : compute P1', which is the point on the Q.B.curve the nearest from P1 : you find it applying the BQC formula with t=0.5. --> distance from PiP1' to P3P4 is an even more accurate estimate -but more costly-.
5. Note that if the line defined by P1P1' intersects P3P4, P1' is the closest point of QBC from P3P4.
6. if P1P1' does not intersect P3P4, then you're out of luck, you must go the hard way...

现在，如果(和何时)需要精确度:

Now if (and when) you need precision :

考虑对曲线的参数使用分治法: 距离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！当两点之间的距离小于给定值时，您可能会停止搜索. (而不是区别两个参数，因为参数略有变化，点可能相距较远) 实际上，该算法的原理是每次都越来越精确地对带有分段的曲线进行逼近.

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 :=)

认为我为一般情况找到了一个不错的解决方案:-) 您应该迭代每个B.Q.C.的(内部)边界三角形. 因此，我们有三角形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上停止递归，这是上一个点Curve2是D或F.如果我们都停止了递归操作->返回距离= min(AD，AF，CD，CF).那么如果我们在T1上具有递归性，并且线段AB最近，则新的T1变为:A'= AB =曲线1的点，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参数.

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.

这篇关于如何计算直线和曲线的最近点? ..还是曲线和曲线?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！