[metapost] Re: workaround for turningnumber bug

Larry Siebenmann laurent at math.toronto.edu
Wed Feb 2 17:22:04 CET 2005

Hi Taco

Thanks for the explanations from mp.web.  I imagine many of
us like to hear ample details on how mp works at a low level.
Some bugs have a complex mathematical origin in the algorithm
used! I still don't understand how JDH's algorithm 
responds to very tiny alpha-loops (see end of posting).

Me=LS> (1) politely refuse paths that mathematically speaking have no
> turning number. These are
>    (a) paths with a cusp, equivalently an interior point where the
> derivative is 0 (or within eps of 0).

I was talking there about a bezier segment, in general. I
should have said a non-integer time for a composite bezier

TacoH> How do I know this? That is the key problem, for me. Remember 
> function that I have the 4 points (P, P+, Q-, Q) not the mathematical 
> describing a path. That's why I raised the 
> "triangle question" in my other reply

If  P1--P2--   --Pn is the control n-lateral path of a degree
n bezier segment p(t), 0=<t=<1, the derivative (the path
described by the velocity vector p'(t) in R^2 is the degree
(n-1) bezier path with control path of mp length (n-1):

   n*(P1-P0) -- n*(P2-P1) --   --  n*(Pn-P{n-1})

Geometrically said, take the successive vectors (P{i-1}--Pi),
scale to 300%, and translate each, moving the initial point
to the origin of R^2. Then the end points of these n vectors
emanating from the origin are the control points of a degree
(n-1) bezier path that is the "derivative" path p'(t).

Hence, for the cubic bezier segment with control trilateral


the derivative is the  quadratic bezier segment

     3(B-A) -- 3(C-B) -- 3(D-C)

For the purposes of mp we have to convert the quadratic to a
cubic by the usual rule that the following picture recalls.
The integers on a straight segment indicate ratio of

             Y            1       YZ            2
                o ------------------X------------------------------- o  Z
               /               /
          1   /          /
             /      /
            /  /
       XY  X
   2   /     
o  X

BezierQuadratic(X--Y--Z) = BezierCubic(X--XY--YZ--Z)

To decide when a path passes through the origin ask mp when
the path intersects the origin -- using 'intersectiontime'.

 LS>    (b) paths with an internal node at which the turning
 > angle is 180 degrees or within eps thereof.

 TH> What is wrong with that? If this happens because of P+, it should
 > be fine as long as the Q- is not likewise strange, right?

I am talking about integral time nodes of a composite path.
Corner points!  A 180 degree corner is a -180 degree corner
so turning number is undefined.

LS> (1*) optionally give warning in case a b'ezier segment
  > has a self intersection. Or a small loop?

TH> What's the difference? And I think that a 
  > loop adds (or removes) 360
  > degrees to the turningnumber. Why should it not?

I have the impression that SMALL composite 
'alpha-loops' of self-intersection 
       |  \             /
       |    \        /
       |      \   /
       |       /\
       |    /      \ 
       | /            \

are often unintended and/or invisible accidents of path
joining as Knuth suggests doing it (see PS).  


Laurent S.


Consider the microscopic view of a rough and raggedy
cut and join operation:
        \                  /   A  
          \             / 
            \        /       
              \   /         Knuth suggests joining
               /\              A to A' by ".."
            /      \         
         /            \
      /                  A'

More information about the metapost mailing list