如何判断一个点是否在给定容差内的二次Bézier曲线上？

我正在为Bézier曲线编写一个库。我已经可以将曲线作为一定分辨率下的一组点来计算，但我现在需要做相反的处理;检测给定点是否在给定容差范围内的曲线上（例如0.0001）。 有没有一个简单的数学函数可以做到这一点？如何判断一个点是否在给定容差内的二次Bézier曲线上？

请短语你的答案在接受两个参数（x和y）函数的形式（仍然被认为是“开”从曲线的距离）的公差和输出布尔？

来源

2017-02-03 Ben Leggiero

简答：不，因为你使用的是IEEE浮点数，而不是完美的数学表达式。所以，你真正想要的是一个评估，告诉你*你的观点距离曲线有多近，这样你就可以决定“足够接近”是指“开”。就象素渲染曲线而言，0.1的距离几乎“在曲线上”。或者做一下@方程式，但是你仍然需要看看'tx'和'ty'值是多少*实际*点，以及这些和你自己的点之间的距离。 –

作为次要评论：您使用的是哪种语言，因为它很可能已经存在贝塞尔曲线库，并且您的努力将会更好地使用它们，并且如果它们在特定环境中有缺陷，则有助于改进它们。=） –

谢谢请注意，@ Mike'Pomax'Kamermans！如果有帮助，我会使用'BigDecimal'的相同算法。此外，这是在** Kotlin **。 –

对于定义为

C（T）= P 0（1-T）^ 2 + 2P1t（1-T）+ P2T^2 = P 0 + 2（P1-P0二次贝塞尔曲线）T +（P0-2P1 + P2）吨^ 2，

对于给定的点Q躺在C（T）必须存在0和1之间对于t的溶液，其满足

（P0-Q）+2（P1-P0）t +（P0-2P1 + P2）t^2 = 0

因此，可以尝试找到共同实根为以下两个方程

（P0X-2P1x + 2P2x）吨^ 2 + 2（P1X-P0X）T +（P0X-QX）= 0
（P0y-2P1y + 2P2y）吨^ 2 + 2（P1Y-P0y）T +（P0y-QY）= 0

如果这样的共同的实根存在，它是0和1之间，它意味着点Q位于曲线上。

对于三次贝塞尔曲线，您可以按照类似的方式执行此过程，但您必须找到三次方程的根。

来源

2017-02-04 23:25:14 fang

请注意，这是一个数学问题的好答案，但不足以解决编程问题：在IEEE浮点域中，几乎没有完美的解决方案，根据数学不是这样的，“应该”在曲线上。所以你仍然需要一个epsilon检查;或者通过评估这一点，然后查看距离原点有多远，找到的“tx”和“ty”值处的坐标是多少，或者您需要计算该点与曲线的距离，然后进行基于epsilon的决策关于该距离是否足够小以将该点视为“在曲线上” –

您能否以采用两个参数（x和y）和公差（距离曲线仍然考虑的距离）的函数形式来回答您的答案“）并输出一个布尔值？ –

您想要在曲线上找到最接近该点的参数，然后就可以找到距离。如果你有贝塞尔曲线B（t）和一个点P，然后解决

（PB（t））的⋅ B'（T）= 0

对于二次贝塞尔这给出了一个可以通过分析求解的三次方程。或者，您可以使用迭代求解器。最小距离是|| P-B（t）||。

来源

2017-03-12 14:35:32 kuribas

你可以用一个函数的形式来描述你的答案，这个函数需要两个参数（x和y）和一个容差（曲线的距离仍然被认为是“on”）并且输出一个布尔值？ –

上面的公式给你一个分析函数，但它可能不是你想要的。由于四舍五入误差，即使使用稳定的立方根求解器，结果可能也不准确，因为从bernstein基变换到功率基是不稳定的。例如，这里是一个描述找到点投影的迭代方法的论文：http://www.geometrie.tugraz.at/wallner/sproj.pdf然后你的公式变成|| P - 最接近（B，P）| | kuribas

我并不十分在意舍入错误。有什么办法可以把它变成'f（x，y，tolerance）：boolean'？ –

您可以利用在https://pomax.github.io/bezierinfo/#projections上描述的“距离曲线”方法，但是会为任何坐标找到一个单一的t值。对于“曲线上的这一点？”这很好（多个t值不会改变答案; 0表示曲线偏离，1表示曲线上，2或更多曲线仍然在曲线上）。

对于t（我假设您为了只计算一次绘制坐标而不是每次绘制曲线时已经执行的效率）而在几个（相对接近的间隔）值处取样曲线，以及然后用最接近的t得出结果，开始走弯曲，减少距离，直到找到最小距离（走路的方式取决于你：你可以做一个粗到细的步行，或者开始很好，或者根据曲线切线确定跳动的距离等）。

然后你的结果字面上只是return minDistance <= tolerance。

来源

2017-03-21 20:42:58

如何判断一个点是否在给定容差内的二次Bézier曲线上？

回答

相关问题