[metapost] turning number -- the neverending story?

[Dan Luecking]

At 04:07 AM 1/10/2012, you wrote:

>Hi,
>
>DL> The algorithm discussed on this list (and which I think is the
>DL> one used by current MP) is different from the one originally
>DL> used in MP, and that one is different from the one used by MF.
>
>Is this algorithm described somewhere in details?

It is, of course, completely "described" in the C sources, but
I can't find it. It was discussed on this list a couple of years
ago. When I get around to writing up my analysis, I will describe
the algorithm.


>DL> Far more important to me is the polygonal pen problem.
>[...]
>DL> Since the polygonal code has bugs, so did winding number.
>
>I believed that the code for polygonal pens has been already
>thoroughly debugged. Isn't that true?

No.

>(Initially, it contained
>terrible errors that were able to hang MP).

I never saw any hanging, just terrible output (which I still see).


>Incidentally, the behavior I reported a few years ago, still manifests:
>
>linecap:=butt;
>% diagonal ends:
>beginfig(100) draw (0,0)--(5cm,0) withpen pensquare scaled 3mm; endfig;
>% vertical ends:
>beginfig(101) draw (0,0)--(5cm,0) withpen pencircle scaled 3mm; endfig;
>end.
>
>Is it a documented feature?

I think it is a bug. The bug I was referring to is in the following:

%% bad.mp
beginfig(0)
   path pp;
   pp := (100,-100){up}..{up}(-100,100);
   draw pp withpen (pensquare scaled 5mm);
   pickup pencircle scaled 3bp;
   drawdot (100,-100);
   drawdot (-100,100);
endfig;
end

(It may well be the same bug.)

MP is supposed to fill a path obtained by following the
"outermost" vertex of the polygon, switching to a new vertex
when the changing direction of the path requires it. In the
above example, it should travel around the square at the ends
of the path, but it never does (in the version 1.504 that I
have).

I have also tested it with version 1.750. This gives the
correct result for the first quarter of the path, but the same
behavior for the remaining three quarters!

The old MP turningnumber code was supposed to drag a triangle
around the cycle and keep track of the switching of vertices
to deduce the number of turns. This is actually a good idea, but
can't be relied on if the code for polygonal pens is bad.


>Let me quote again the whole example, prudently modified:
[example omitted]

>The results seem to be stable.

Indeed. Now I'm going to guess that the algorith is confused
on the counting of zeros. The usual way to do this is to look
for changes in sign in the quadratic I previously called q(t).
Two of the three corfficients are 0 when the controls are equal.
The conclusion then should be: no change of sign. Perhaps the
code contains a ">" where ">=" should be (or vice versa)?


Dan


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