[metapost] turningnumber revisited
Boguslaw Jackowski
B_Jackowski at GUST.org.pl
Tue Jun 28 11:08:18 CEST 2011
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.
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
More information about the metapost
mailing list