[metapost] turningnumber revisited

[Boguslaw Jackowski]

Hi,

Luigi:
> But the interesting point now is:
> in
> mode_setup;
> turningcheck :=0;
> path p;
> p:=(0,0)..{up}(1,1) & (1,1){down} .. {1,0}(2,0){-1,0} -- cycle ;
> for i:=0 upto 1000: show (1+i/1000,turningnumber (p rotated (1+i/1000) ));
> endfor
> end.
> 
> why the turningnumber jump from 2 to zero  around 1.47 degrees ?

Jacko: 
> Good question. :) Actually, this is what I'd expect -- infinitesimal 
> changes of the path causing an abrupt change of the turning number.

Dan:
> This seems to be the answer: Try it with autorounding := 0;

Aaaa... Right. Using recently almost exclusively MP, I've already 
forgotten about this peculiar MF feature. :)

> Metafont: the program" says:
>
>  "A tricky question arises when a path jumps four octants.
>   We want the direction of turning to be counterclockwise
>   if the curve has changed direction by 180, or by
>   something so close to 180 that the difference is probably
>   due to rounding errors; otherwise we want to turn through
>   an angle of less than 180.
>
> It would therefore seem to follow that a cusp is taken always
> as a 180 degree change, and it is only the small changes
> introduced by autorounding that sometimes cause it to be seen
> as a non-cusp with a turning very close to -180 degrees.

Thank you for the explanation and recalling the DeK's explanation.

Larry:
> However, it seems to me likely that algorithms
> specially tailored to QUICKLY calculate winding
> number of piecewise QUADRATIC  bezier paths will be
> advantageous for MetaPost's turningnumber primitive.

Jacko: 
> Don't understand... You'd need to _approximate_ cubic path by quadratic
> ones which seems to be a rather cumbersome and complex task. Can it be done 
> robustly?

Dan:
> The point, I think, was to perform a differentiation on the cubics
> (an easy and fairly robust action), producing quadratics. One then
> could _use_ these quadratics internally, computing their winding
> number, producing the winding number of the original cubics. There
> is no approximation of cubics by quadratics.

Well... My math knowledge is perhaps insufficient -- I cannot see
at the moment how to compute the winding number of the original curve 
having the winding number of its derivative (although I agree that 
differentiation is a robust operation). Perhaps I have to dwell
a bit on the problem.

> Larry suggests that there might be winding number calculations
> for quadradics that are fast and efficient and could be used to
> find turningnumber. In another message I opined that quadratics
> are already used for turningnumber by MF. I add to that the
> observation that the MP turningnumber algorithm is also mainly
> driven by computations with quadratics.

Agreed. As far as I remember, quadratics in MF (and in MP?) are used
to find "turning points" of the original curve, i.e., extremes -- these 
points obviously correspond to zeros (x or y) of the derivative. But 
computing zeros of the derivative is not as robust as differentiation.

I'm interested very much what Larry keeps in mind. :)

Larry:
> is a bezier path enjoying the properties:
>  (a) p_i is nondegenerate in the sense that the
> derivative vector Dp_i(t) := dp_i(t) / dt at p(t) is
> non-vanishing for all t in the interval [i-1,i].

Jacko: 
> In practice, I believe, you _cannot_ impose such severe restrictions.

Dan:
> I agree. But one needs a reasonable and simple disambiguation
> method when a cusp is detected. I think perhaps Knuth's choice
> to make always 180 degrees is as good as any.

Yes. But one cannot ignore that the problem exists. Larry
tries to avoid the problem assuming that paths behave neatly. :)
Or I've overlooked a "disambiguation approach" in Larry's
"desiderata"?

Thanks -- cheers -- Jacko

-- 
BOP s. c.
ul. Bora-Komorowskiego 24, 80-377 Gdansk, Poland
tel. (+48 58) 553 46 59,  fax (+48 58) 511 03 81
bop at bop.com.pl, http://www.bop.com.pl