math - 如何计算直线和曲线的最近点？ ..还是曲线和曲线？

Question

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

Answer 1

我只是想给你一些提示，在 Q.B.Curve//段的情况下:
为了获得足够快的计算，我认为您应该首先考虑为您的算法使用一种“边界框”。
假设 P0 是 Q. B. 曲线的第一个点，P2 是第二个点，P1 是控制点，P3P4 是线段，然后:

计算从 P0、P1、P2 到 P3P4 的距离

如果 P0 或 P2 是最近的点 --> 这是距离 P3P4 的曲线最近的点。结束:=)。

如果 P1 是最近的点，而 Pi(i=0 或 1)是第二个最近的点，则 PiPC 和 P3P4 之间的距离是对您寻求的距离的估计，这可能足够精确，具体取决于您的需要。

如果您需要更准确:计算 P1'，它是 Q.B.curve 上离 P1 最近的点:您发现它应用了 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 具有“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= 曲线一的点，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 参数。

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