[metapost] turning number -- the neverending story?

[Dan Luecking]

At 10:55 AM 1/5/2012, you wrote:

>Hello, dear (meta)fonters,
>
>I spotted a nasty bug in Metapost -- sorry, Taco, for spoiling
>the beginning of the new year... I hope that the bug will
>be easy to fix.

I think it _should_ be easy. It has the character of a possible
sign error. (Similar buggy results from turningnumber
have already reached this mailing list.)

Here's my analysis:

If metapost is using the algorithm discussed on this list,
the following calculations should be performed:

The derivative is a quardatic bezier, lets say
   (1/3)f'(t) = a(1-t)^2 + 2b (1-t)t + c t^2
where a,b,c are the differences between successive
control points. In the example, the first segment has
   a = (0,-100)
   b = (0,0)
   c = (-100,0)
Then one computes g(t) = (1/6)f'(t) x f''(t) (where
x = "cross product") to get
   g(t) = (a x b)(1-t)^2 + (a x c)(1-t)t + (b x c) t^2
In the example, the first and the last terms are 0 and
the middle coefficient is -10000:
   g(t) = -10000(1-t)t
The algorithm is based on the location of zeros of g(t).
In this case, there are none in the interval (0,1), which
means the path f(t) curves always to the right, or always
to the left[*].

In the present case, the negative value of g(t) indicates
clockwise turning (to the right). That means the change in
angle must be negative and strictly between 0 and -360
(values close to -360 would be evidence of a loop). Subtracting
the starting angle (-90) from the ending angle (180, I think[**])
gives 270 and this has to be adjusted by subtracting 360 to
make it negative, giving the correct turning: -90. In all four
segments, the function g(t) turns out to be the same, and -90
should be the angle change, totalling -360 (no corners or cusps,
which would introduce different problems).

I suspect the angle difference is not being properly adjusted.
That is, the angles are simply being subtracted. This leads to one
angle difference of 270 and three of -90. Summing these produces
a turning angle of 0.

Changing some points slightly can (for example) cause 180 to
become -179.99998, then instead of an angle difference of
(for example)
   180 - (-90) = 270,
one would get
   -179.99998 - (-90) = -89.99998
which would have the correct sign without any adjustment.

I have offered try to analyze the implementation of
this algorithm (if it is indeed the one being used), but I
don't know how to find it in the metapost sources.

>q=z1 .. controls z2 ..
>   z3 .. controls z4 ..
>   z5 .. controls z6 ..
>   z7 .. controls z8 .. z1 & cycle;

This path is
     (100, 0)..controls (100, -100) and ( 100,-100)
   ..(0,-100)..controls (-100,-100) and (-100,-100)
   ..(-100,0)..controls (-100, 100) and (-100, 100)
   ..(0, 100)..controls ( 100, 100) and ( 100, 100)
   ..cycle
which clearly starts going down, then the direction
continuously changes, becoming left, up, right, and
finally ends going down.

----------
[*] If g(t) has one or two simple zeros in (0,1) the f(t)
has one or two inflections, and the angle difference would
have to be adjusted to the range (-180, 180). A double zero
in (0,1) indicates a cusp between the two endpoints, and a
choice would have to be made as to how to how to adjust the
angle difference. It depends on whether one thinks of a cusp
as an infinitesimal loop or as two infinitesimally close
inflections. I prefer the latter.

There are degenerate cases (where g(t) is 0). This indicates that
f(t) stays within a line, but could change directions one or two
times. These have to be handled separately.

[**] If left is given an angle -180, then the second
segment produces a pre-adjustment value of 270 instead
of the first.

>The only peculiarity of the path is that the precontrols and
>postcontrols coincide (i.e., it is actually a so called b-spline).

I doubt this peculiarity has anything to do wth this problem.


Regards,
Dan


Daniel H. Luecking
Department of Mathematical Sciences
Fayetteville, Arkansas
http://www-cs-faculty.stanford.edu/~knuth/iaq.html