如何确定一个三angular贝塞尔path在一个终点的曲率

我一直在使用Bezierpath来绘制我需要的曲线。 我的项目中的每个基本形状都由三条三次贝塞尔曲线组成，这些曲线首尾相连排列，以便斜坡匹配。

我需要解决的基本问题是由三条贝塞尔曲线构成的复合曲线是否与自身相交。 经过一段时间的思考之后，我发现，考虑到曲线的限制，我可以将任务简化为其他任务：

三条贝塞尔曲线中的每一条的曲率在曲率方向上应该相对于它所邻接的曲线相反。 换句话说，应该有一条贝塞尔曲线与另一条曲线相邻的拐点。 如果不是这种情况，我想拒绝生成曲线的参数集并select一个不同的集合。

无论如何，我的基本问题是如何检测曲线是否存在一个拐点。

在图中，三条贝塞尔曲线中的每一条都以不同的颜色显示。 左边的黑色曲线在红色曲线相反的方向上弯曲，而右边的黑色曲线在相同的方向上曲线。 红色和左边的黑色曲线相交处有一个拐点，而红色和右边的黑色曲线相交处没有拐点。

编辑：下面，我添加了另一个图像，显示了包围贝塞尔path的多边形。 黑色曲线所示的多边形交叉线testing的是一个拐点，而不是一个循环。 我猜测可以通过检查包围的多边形是否相交来testing一条相交于另一条的曲线，如红色和蓝色曲线所示。

PS由于存在一些关于约束的问题，我将在这里列出其中的一些：

• 最左边的点和最右边的点具有相同的y值。
• 最左点的控制点的x值小于
  最右端控制点的x值。 这保持
  黑色和蓝色曲线相互交叉。
• 最左边和最右边的坡度在水平线的+/- 10度以内。
• 黑色和红色曲线的交叉点以及红色和蓝色曲线的交点将大致三分之一的曲线分开。 我没有确切的数字，但是一个样本界限应该是红色曲线左端的x值在最右边的x值的25％和40％之间。
• 交点的y值是整个宽度的+/-一小部分。
• 交叉点的斜率> 0.6和<3.0（正值或负值）。

Answer 1

曲率方程适度简单。 你只需要曲率的符号，所以你可以跳过一点math。 你基本上对第一和第二衍生产品的交叉产品的符号感兴趣。

这种简化只能起作用，因为曲线连接平稳。 没有相同的切线，就需要更复杂的testing。

曲线P的曲率符号：

ax = P[1].x - P[0].x; // a = P1 - P0 ay = P[1].y - P[0].y; bx = P[2].x - P[1].x - ax; // b = P2 - P1 - a by = P[2].y - P[1].y - ay; cx = P[3].x - P[2].x - bx*2 - ax; // c = P3 - P2 - 2b - a cy = P[3].y - P[2].y - by*2 - ay; bc = bx*cy - cx*by; ac = ax*cy - cx*ay; ab = ax*by - bx*ay; r = ab + ac*t + bc*t*t; 

请注意，r是一阶和二阶导数的叉积，符号表示曲率的方向。 在左曲线的t = 1和右曲线的t = 0处计算r。 如果产品是消极的，那么就有一个拐点。

如果你有曲线U，V和W，其中U是左边的黑色，V是中间的红色，W是右边的黑色，然后分别计算上面的bc，ac和ab。 如果两个连接都是拐点，则以下testing将成立：

 (Uab+Uac+Ubc)*(Vab) < 0 && (Vab+Vac+Vbc)*(Wab) < 0 

曲率的等式有一个我忽略的分母。 它不会影响曲率的符号，只有当曲线是一条直线时才会为零。

math概要：

 // start with the classic bezier curve equation P = (1-t)^3*P0 + 3*(1-t)^2*t*P1 + 3*(1-t)*t^2*P2 + t^3*P3 // convert to polynomial P = P0 + 3*t*(P1 - P0) + 3*t^2*(P2 - 2*P1 + P0) + t^3*(P3 - 3*P2 + 3*P1 - P0) // rename the terms to a,b,c P = P0 + 3at + 3btt + cttt // find the first and second derivatives P' = 3a + 6bt + 3ctt P" = 6b + 6ct // and the cross product after some reduction P' x P" = ab + act + bctt 

Answer 2

由于贝塞尔曲线的反演方程在自交点处始终为零，因此检查贝塞尔曲线是否具有双点或自相交的确定性方法之一是计算反方程并评估根。 正如TWSederberg在这个例子中详细介绍的那样 。 然后为了检测两个贝塞尔曲线（问题中的红色和黑色）是否相互交叉，有几个方法， 二进制细分 （更容易实现）和贝塞尔剪裁 （效率和代码复杂度非常好的平衡）， 隐式化值得）。

但更有效的做法可能是将曲线细分为小线段并find交点。 这是一个办法 。 特别是当你有兴趣知道path是否自相交，而不是在一个精确的交点。

如果你对分段贝塞尔曲线（或者上面提到的@Pomax的poly-bezier）的CV的位置有明确的假设，那么你可以尝试一下你在问题中提到的基于曲率的方法。

下面是与问题类似的曲线图。 在类似的情况下，似乎这可能会给你你正在寻找的解决scheme。 此外，在一个尖头的情况下，似乎这种快速和肮脏的方法仍然工作！

Answer 3

假设你有4个点：P0，P1，P2和P3，它描述了一个三次贝塞尔曲线（简称cBc ）。 P0和P3是起点和终点，P1和P2是方向点。

当P0，P1和P2共线时， cBc在P0 处有一个拐点。

当P1，P2和P3共线时， cBC在P3 处有一个拐点。

备注。

1）使用vector产品（P0P1×P1P2和P1P2×P2P3）分别检查共线性。 结果应该是一个零长度的向量。

2）避免P0，P1，P2和P3都是共线的情况，他们创build的cBc不是常规的曲线。

推论。

当P1 = P2时， cBc两边都有拐点。

Answer 4

@ Victor Engel：谢谢你的澄清。 现在解决scheme更容易。

总之，看看两条曲线的扭矩。 如果他们拉在一起，就会发生“拐点”，如果他们反对，“曲率”会继续下去。

备注： “inflexion”和“curvature”这两个词在这里比直接的math意义更直观，所以使用了撇号。

如前所述，一组点P0，P1，P2，P3定义了第一个三次贝塞尔曲线，其次是Q0，Q1，Q2和Q3 。 此外，4个向量： a，b，u，w将是有用的。

 a = P2P3 b = P1P2 u = Q0Q1 v = Q1Q2 

我将省略C1连续性检查，这已经由您完成了。 （这意味着P3 = Q0和a u = 0）

最后，将出现Tp和Tq扭矩。

 Tp = bxa 

（“x”表示vector乘积，但平面上的Tp被视为简单的数字，而不是vector。}

 if Tp=0 {very rarely vectors a, b can be parallel.} b = P0P1 Tp = bxa if Tp=0 No! It's can't be! Who straightened the curve??? STOP endif endif Tq = uxv if Tq=0 {also vectors u, v can be parallel.} v = Q2Q3 Tq = uxv if Tq=0 Oh no! What happened to my curve??? STOP endif endif 

现在最后的testing：

 if Tp*Tq < 0 then Houston! We have AN "INFLEXION"! else WE CONTINUE THE TURN!