[metapost] turningnumber revisited

[Boguslaw Jackowski]

Hello, Everybody,

> 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 ?

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

Coming back to the issue turningnumber vs. (actually not 
"vs" but "and") windingnumber:

supporting Larry, I didn't mean that the turningnumber is useless;
we need, as Dan convincingly pointed out, both operations.
The fairly robust an efficient (although perhaps suboptimal) 
implementation of the windingnumber I send to Taco (and Larry, and Dan).
It seems, that it is much simpler that DeK's turningnumber implementation 
(the details of the DeK's implementation are obscure for me, although
I perhgaps never spent enough time on the analysis of the implementation...).

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.

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?

Larry:
> Is anyone able to describe ghostscript's
> algorithm for winding number? I have not seen any
> account of it.

Don't they use a variant of a scan-line algorithm? Which, actually,
can be regarded as the computing of the winding number for every pixel; 
the same must happen (I guess), in MF when the weights of pixels are 
being computed; thus, in both cases, the windingnumber for pixels is 
implicitly calculated.

Incidentally, as I mentioned a few times, I used bitmap operations
in MF for defining useful macros; in particular, for defining
"mock turning number" (approximate yet robust): for example,
if after applying the fill operation to a path the number of pixels with 
weight, say, 1 is significanly larger than the number of pixels of the 
weight -1 (i.e., there is a tiny loop) we usually can safely assume that 
the turning number is 1 (i.e., we can ignore ignore the tiny loop). A pity 
that bitmap calculations are not available in MP... (Taco -- this is not
a wish-list item for you! :)

Cheers -- Jacko

Ps.

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].

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

-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
  Bogus\l{}aw Jackowski: B_Jackowski at GUST.ORG.PL
----------------------------------------------------------------
  Hofstadter's Law: It always takes longer than you expect, even
                    when you take into account Hofstadter's Law.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-