[metapost] turning number -- the neverending story?

[Dan Luecking]

At 04:52 AM 1/9/2012, you wrote:
>Dan:
>>If metapost is using the algorithm discussed on this list,
>
>I believe that the situation is ripe to replace the current
>version of the turning number algorithm with a new one, written
>from scratch. (Of course, I can ofer my help, if anyone needs it.)

The algorithm discussed on this list (and which I think is the
one used by current MP) is different from the one originally
used in MP, and that one is different from the one used by MF.

My own use of turning numbers and winding numbers treats them
as debugging tool: if a turning number is unexpected, it might
indicate a coding error.

Far more important to me is the polygonal pen problem. The
current turning number algorithm arose because MP used to
tap into the polygon pen code to detrmine winding number.
Since the polygonal code has bugs, so did winding number.

It is still (I think) a workable method, but only if that
code is corrected.

>Implementing the winding number (discussed minutely on this list)
>and next implementing the turning number as the winding number
>of the unit tangent vector around the origin should work --
>for smooth curves, with non-vanishing derivative.
>
>[As far as I remember, this was also the suggestion
>of Larry Siebenmann; I have an impression that a variant
>of this approach is implemented in MF, and thus in MP,
>although I was not able to analyse it carefully enough,
>given free time I was given :) ]
>
>The only problem is -- as Dan some time ago rightly emphasized --
>how to proceed with the singular cases? One must use ad hoc
>solutions -- this is obvious -- but how to guarantee (at
>the level of mathematical exactness) the consistence?
>
>Dan, are you able to sketch guidelines for handling singular cases?

I can enumerate the singular cases and suggest default actions.
There are two general issues.

1. Given that nodes and control points are reduced to integers,
some singular cases (e.g., cusps in a curve) are mathematically
exact and it is just a matter of deciding what to do with the
turningnumber (etc.) in such cases.

2. Other singular cases (a point lying on a path) are not
mathematically exact. This is relevant to winding number
calculations.

Both of these types of singularities can appear or disappear
upon simple transformations of paths and points.

Let me take some time and write up a descriptions of cases and
the issues involved.

>It seems to me that you have the subject carefully thought over.
>Or, maybe, you know papers concerning this subject?

Not yet, but I have been thinking about writing one.

>>The only peculiarity of the path is that the precontrols and
>>postcontrols coincide (i.e., it is actually a so called b-spline).
>
>Dan
>>I doubt this peculiarity has anything to do with this problem.
>
>Hmmm... Why, then, if you move randomly all nodes of the
>curve from my example, e.g.,
>
>  i:=0; z0=origin;
>  for f:=0, 1, 2, 2, -1, -1, 0, 0:
>   i:=i+1; z[i]=z[i-1] +
>    (uniformdeviate 100, uniformdeviate 100) +
>    p rotated (f*a);
>  endfor
>
>the turning number still reamins equal to 0?

I get always 0 also after changing the controls to

   ..z2 and z2+(eps,eps)..
   etc.

This "proves" it is not the equality of controls
that matters.


Dan


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