如何防止三次贝塞尔曲线中的循环

Question

我有一个生成三次二维贝塞尔曲线的计算。在这种情况下，端点是固定的，我的程序计算内部控制点。大多数时候，这些曲线会在两个相邻的形状之间产生简单的混合。但有时几何形状使得绘制曲线会产生一个循环，这在这个应用程序中看起来永远不会好看。在这种情况下，我愿意修改控制点以防止循环。但是为此，我需要检测给定的三次贝塞尔曲线在绘制时是否会循环。

我当然可以简单地在许多点对曲线进行采样并寻找一个循环，但我宁愿找到一个基于 8 个变量（4 个点中每个点的 x 和 y 值）的代数解。理想情况下，该解决方案不仅会告诉我是否存在循环，还会告诉我 "big" 循环在某种意义上如何。但即使有二进制 yes/no 答案也会有很大帮助。

有谁知道可以确定给定的三次 2D 贝塞尔曲线在绘制时是否会产生循环的算法？

Answer 1

当然：你可以看看它的canonical form，看看这四个点是否导致曲线"ending"在一定存在环路的区域

最初的理论在 1989 年的论文"A Geometric Characterization of Parametric Cubic curves"

中有所概述

Answer 2

先上代码，再解释。这个过程有点耗时，所以对代码进行了轻微的优化。现在它就像一个尖锐的选择，很少有候选人会通过所有测试。

type
  myType=Integer; {remember to change here to your own type, 
    an integers are good for an educational purpose}
  point_2d=record    xx,yy :myType  end;
  vector_2d=record    vx,vy :myType  end;    

function bezier_has_a_loop(p0,p1,p2,p3:point_2d):boolean;
              {-------------------------}
              function f_vec_from_2_pts(pa,pb:point_2d):vector_2d;
              begin
                with Result do begin
                  vx:=pb.xx - pa.xx;
                  vy:=pb.yy - pa.yy     end  end;
              {-------------------------}
              function f_cross_prod(va,vb : vector_2d):myType;
              begin
                 Result := va.vx*vb.vy - va.vy*vb.vx      end;
              {-------------------------}
              function f_mult(m:myType; v:vector_2d):vector_2d;
              begin
                with Result do begin
                  vx := m*v.vx;
                  vy := m*v.vy   end   end;
              {-------------------------}
              function f_sum(va,vb : vector_2d):vector_2d;
              begin
                with Result do begin
                  vx := va.vx+vb.vx;
                  vy := va.vy+vb.vy    end   end;
              {-------------------------}
              function f_rotate(v, rotor : vector_2d):vector_2d;
              var
                m_sin,m_cos:myType; {only for a readability purpose}
              begin
                m_cos:=rotor.vx {
                /sqrt(sqr(rotor.xx)+sqr(rotor.yy))  - unnecessary };
                m_sin:=rotor.vy {
                /sqrt(sqr(rotor.xx)+sqr(rotor.yy))  - unnecessary };
                with Result do begin
                  vx := -v.vx * m_cos - v.vy *m_sin;
                  vy :=  v.vx * m_sin - v.vy *m_cos   end   end;
              {-------------------------}
var
  a,b,c, c1,c2,c3  :vector_2d;
  ab,ac,bc:myType;
  bb,s1,s2,delta,shift,t_1_2 : Double;
begin

  a:=f_vec_from_2_pts(p0,p1);
  b:=f_vec_from_2_pts(p1,p2);
  c:=f_vec_from_2_pts(p2,p3);

  ab:=f_cross_prod(a,b); {on the planar, 
    myType for a cross product is just fine}}
  ac:=f_cross_prod(a,c);
  bc:=f_cross_prod(b,c);

  {==1== No inflection point(s) or cusp allowed}
  if ac*ac >= 4*ab*bc  then begin    Result:=False; exit end;

  c3:= f_sum( f_sum(a,c)  ,  f_mult( -2,b ) );
  if c3.vy<>0 then begin   {Is the bag's handle horizontal?}
    a := f_rotate(a,c3);      
    b := f_rotate(b,c3);
    c := f_rotate(c,c3);
    c3:= f_sum  ( f_sum(a,c) , f_mult(-2,b) ); 
    {Now the handle is forced to be horizontal.}
  end;

  c1:= f_mult ( 3,a );
  c2:= f_sum  ( f_mult(3,b) , f_mult(-3,a) );

  { Following 4 restrictions comes from a single caveats for a roots:
     0<= t1<t2<=1}
  bb:= -c1.vy / c2.vy;  { always  c2.vy<>0 }

  {==2== A central point (t1+t2)/2 outside the limits}
  if  (bb<0) or  (bb>2) then begin Result:=False;  exit  end;

  s1:= c1.vx/c3.vx;    { always  c3.vx<>0 }
  s2:= c2.vx/c3.vx;
  delta := -bb*(4*s2+3*bb)-4*s1;

  {==3==  delta is to big}
  if delta>1 then begin Result:=False;  exit  end;

  shift:=sqrt(delta);   { always  delta>0 }
  t_1_2:=bb-shift;    {for readability purpose only, 
    one can omit this and write below: if shift>bb }

  {==4==  t1 is to low }
  if t_1_2<0 then begin Result:=False; exit end;
  t_1_2:=bb+shift;      { no /2 here,beacause of *2 below}

  {==5==  t2 is to high}
  if t_1_2>2 then  Result:=False
              else  Result:=True  { TA DA! Thank you for your patience. }
end;

现在一些理论。

让我们考虑 4 个点 P0、P1、P2、P3。这些点（几乎总是）定义了三次贝塞尔曲线。
设点H1如向量P1_H1是向量P0_P1的一半.
设点H2如向量P2_H2是向量P3_P2的一半。
最后，让我们创建向量 h = H1_H2。（我个人称这个向量为 "the handle of the bag"，猜猜为什么。）

Bezier curve and its handle

不足为奇，当您开始各向同性缩放或旋转 P0、P1、P2、P3 时，矢量 h 将相应地变换。
也许对某些人来说这会是一个惊喜，向量 h = [_h_x,_h_y] 与向量 [c3x,c3y] 成正比] 从三次贝塞尔曲线的代数形式的最高系数创建。比例系数为(-1/2).

(事实上，当点H1=H2重合时，h向量消失，c3x=c3y=0，因此三次Bézier曲线至少减少为二次Bézier曲线，由 P0、H1、P3 点创建。)

现在有了线索：右旋总能将向量 h 水平（或垂直）旋转，并且这种旋转会将 c3y（或 c3x）减少为空值，但是保留循环。反过来，可以将所述问题简化为二次方程的微不足道的求根问题。（我想这是找到解决方案的决定性提示。）

为了测量循环，我建议考虑上面代码中的变量 delta。

   0 < delta <= 1
When delta -> 0, the loop vanishes. 
When delta -> 1, the loop becomes really pompous.

我对这个提议不太满意，但总比没有好。

如何防止三次贝塞尔曲线中的循环

How to prevent loops in cubic Bezier curves

loops

curve

bezier