1

我一直在做一个项目，我使用贝塞尔路径来绘制我需要的曲线。我的项目中的每个基本形状都由三个三次贝塞尔曲线首尾相连，以便斜率与它们相交的位置相匹配。

我需要解决的基本问题是由三个贝塞尔曲线组成的复合曲线是否与自身相交。经过一段时间的思考，我发现鉴于曲线的约束，我可以将任务简化为其他内容：

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

无论如何，我的基本问题是如何检测曲线相互邻接的拐点是否存在。

在插图中，三个贝塞尔曲线中的每一个都使用不同的颜色显示。左边的黑色曲线在它们相交的点处与红色曲线的弯曲方向相反，但右边的黑色曲线在同一方向弯曲。在红色和左黑色曲线相交处存在一个拐点，但在红色和右黑色曲线相交处没有。

循环贝塞尔路径

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

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

  • 最左边的点和最右边的点具有相同的 y 值。
  • 最左边点的控制点的x值小于
    最右边点的控制点的x值。这可以防止
    黑色和蓝色曲线相互交叉。
  • 最左边和最右边点的斜率在水平线的大约 +/- 10 度范围内。
  • 黑色和红色曲线的交点以及红色和蓝色曲线的交点将整条曲线分成大约三分之二。我没有确切的数字，但样本界限是红色曲线左端的 x 值介于最右边点 x 值的 25% 到 40% 之间。
  • 交点的 y 值是整个宽度的 +/- 一小部分。
  • 交叉点处的斜率 > 0.6 且 < 3.0（正或负）。
4

4 回答 4

4

曲率方程比较简单。你只需要曲率的符号，所以你可以跳过一点数学。您基本上对一阶和二阶导数的叉积的符号感兴趣。

这种简化只适用于曲线平滑连接。如果没有等切线，则需要更复杂的测试。

曲线 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。如果两个连接都是拐点，则以下测试将成立：

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

曲率方程有一个我忽略的分母。它不影响曲率的符号，并且仅当曲线是一条线时才为零。

数学总结：

// 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
于 2013-08-10T22:21:37.473 回答
1

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

但更有效的方法可能是将曲线细分为小线段并找到交点。这是一种方法。尤其是当您想知道路径是否自相交，但不是在准确的交点上时。

如果您对分段贝塞尔曲线（或上面提到的@Pomax 的多贝塞尔曲线）的 CV 位置有明确的假设，您可以尝试在问题中提到的基于曲率的方法。

这是与问题相似的路径上的曲率图。在类似情况下，这似乎可以为您提供您正在寻找的解决方案。此外，在风口浪尖的情况下，这种快速而肮脏的方法似乎仍然有效！

双点 风口浪尖

于 2013-06-17T17:25:20.607 回答
1

@维克多恩格尔：谢谢你的澄清。现在解决方案更加简单。

简而言之，看看两条曲线的扭矩。如果它们拉在一起，就会发生“弯曲”，如果它们相反，则“弯曲”会继续。

备注：这里的词 “屈曲”和“曲率”比严格的数学含义更直观，因此使用撇号。

和以前一样，一组点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 x u =0）

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

Tp = b x a

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

if Tp=0            {very rarely vectors a, b can be parallel.}
    b = P0P1
    Tp = b x a 
    if Tp=0 
        No! It's can't be! Who straightened the curve???
        STOP
    endif
endif

Tq = u x v 
if Tq=0            {also  vectors u, v can be parallel.}
    v = Q2Q3
    Tq = u x v 
    if Tq=0 
        Oh no! What happened to my curve???
        STOP
    endif
endif

现在是最后的测试：

if Tp*Tq < 0  then    Houston! We have AN "INFLEXION"!
              else    WE CONTINUE THE TURN!
于 2016-08-14T20:42:19.650 回答
0

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

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

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

评论。

1) 使用向量积（分别为 P0P1 x P1P2 和 P1P2 x P2P3）检查共线性。结果应该是一个零长度向量。

2) 避免P0、P1、P2、P3都共线的情况，它们产生的cBc不是常识中的曲线。

推论。

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

于 2016-08-10T12:09:47.620 回答