[metapost] turningnumber revisited

[laurent at math.toronto.edu]

Hi all,

Thanks for many interesting comments. Being a mere
MP digest reader I did not see  most of Tuesday's
posts until visiting the archive this morning. So
there will be more reactions tomorrow.

I asked:

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

Following a backchannel hint by Dan, I looked at
the PostScript level 3 manual (PLRM of 1999)
available on Internet.  It documents boolean
"insideness-testing" operators letting one enquire
whether one path meets another or lies 'inside' the
another.  PLMR gives a good mathematical definition
of winding number. But as expected there is no
commitment to any algorithm. For a state-of-the-art
algorithm I still hope that the sourcecode of
Ghostscript is a good place to look.

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

Quite likely; I believe that Metafont (in its
prelim version) antedates PostScript. Another
approximate approach sometimes used is to take a
sufficiently close piecewise linear approximation
to the path and use fast linear algebra.  But
todays vector processors probably make the bitmap
approach much faster.

Jacko> supporting Larry, I didn't mean that the
 > turningnumber is useless; we need, as Dan
 > convincingly pointed out, both operations.

No dispute on that. It is also a historical
necessity given Knuth's turningnumber. But somehow
the craziness of the present implemantations of
turning number in MF/MP should be eliminated by MP
(or by MP macros if Taco devotes no time).
Likewise, the unnecessary deviations from the
mathematical turningnumber notion.

Yesterday I defined a class \C of piecewise bezier
paths and gave a certain derivation of turning
number from winding number, one that offers us a
STABLE implementation of turning number in MetaPost
for the class \C.

Jacko finds the class \C too restrictive objecting
to my condition (a) that each bezier component p_i
of a path p in \C  have no point where its velocity
vector is zero.

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

    Trusting Jacko, I have produced a plan for
dealing coherently with 'robustly cubic cusps', and
also certain 'thorns'; see below.

    I did give a larger class \D (say) of those
continuous cyclic paths p : S^1 --> R^2 that are
locally immersive. And I asserted that the
mathematical notion of turning number is well
defined for p in \D, and well behaved EXCEPT
for some instability phenomena.

One clear definition valid for all of \D runs as
follows. It is a non-trivial theorem (a consequence
of the century-old classical Osgood-Schoenflies
theorem) that any p \in \D can be extended to an
open topological immersion \p : S^1 x (-1,1) -->
R^2 with \p(x,0) = p(x) for x in S^1. Furthermore,
outside of S^1 x 0, the extension \p can be smooth
(= infinitely differentiable) and also nonsingular.
The turning number of p is then by definition equal
to the classical turning number (see Google) of the
smooth and smoothly immersive cyclic path
 \p| S^1 x u ---> R^2, where u is any point in
(-1,1) distinct from 0.

    My definition above of turning number on \D
seems to provide a practical way of dealing with
'robustly cubic' cusp points of bezier curves --
indeed without abandoning the key stability
property that turning number enjoys on \C. When we
have a 'near' cusp in the interior of a bezier
curve namely something that looks locally like:

       .
       .
      . .     [View with a constant width font!]
    .    .
 .          .

up to a certain (hopefully adjustable!) tolerance,
then we can simply assign to the cusp the turning
angle of its infinitesimal immersive
perturbations without double point or cusp,
i.e., looking like

       ..
      .  .
    .     .
 .           .

namely angle -180 degrees  when the path
orientation is from west to east, and +180 degrees
when the path orientation is from east to west.
(Naturally I use the math conventions that small
positive angles turn counterclockwise ;) This is
the rule dictated by my very general definition of
turning number on the class \D. I believe that I
can deal similarly with 'robustly cubic' cusps that
are lurking at an end point of a bezier path; I
suspect that such 'semicusps' occur in some fonts.
Likewise with 'thornlike' behavior at the junction
of two bezier paths, with or without hidden
cusp(s). Then, hopefully, the only phenomenon that
will still lead to annoying instability of
turningnumber is 'backtracking' (up to a tolerance)
on one bezier segment by the next bezier segment.

Cheers

Laurent S.