[metapost] turningnumber revisited

[laurent at math.toronto.edu]

Hi all,

Since there is agreement concerning the mathematical
concept "winding number" and the performance of its
Metapost (or PostScript) implementation
"windingnumber", I propose today to exploit "winding
number" to specify "turning number" and propose
potential Metafont implementations of the primitive
"turningnumber".

I restrict my definition of "turning number" to the
class \C of cyclic piecewise bezier paths that I
mentioned on 05 June, namely those cyclic paths p :
[0,n] --> R^2, p(0) = p(n), such that for
 i = 1, ..., n the restricted path:

    p_i := p|_{[i-1,i]} : [i-1,i] --> R^2

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

 (b) At each time t = 1, ..., n-1, the lower and upper
derivative vectors D_{-}p(t) and D_{+}p(t) are
related by a rotation of R^2, about the point p(i),
having an angle that lies in the open interval
(-180,180). Angles are measured in degrees.

Each derivative Dp_i(t), i = 1, ..., n,
 t \in [i-1,i], is a naturally bezier path ; of
degree one lower than that of p_i; it
lies in a copy of R^2 (called the velocity plane);
and it joins the point
 Dp_i(i-1) := D_{+}p(i-1) \in R^2 to the point
 Dp_i(i) := D_{-}p(i) \in R^2.  Condition (a) assures
that the entire path Dp_i(t), t \in [i-1,i],  is
disjoint from the origin.

Conditions (a) and (b) assure that for
 i = 1, ... , n-1 the affine interval joining the
point D_{-}p(i) to the point D_{+}p(i+1) lies in the
complement of the origin. Denote this path q_i. Since
q_i is affine linear it is easily seen to be also
naturally a bezier path lying in class \C
and of any any degree \geq 2 .

Now form the Knuthian end-to-end composition pp of
the sequence of 2n - 1 bezier paths:

    Dp_1, q_1, Dp_2, q_2, ... , q_{n-1}, Dp_{n-1}

Since this pp is a piecewise bezier path that lies in
the complement of the origin of the velocity plane,
it has a well defined winding number about the
origin.

Inspection of almost any common mathematical
definition of turning number valid for the class \C
(see Google) reveals that the winding number of pp
about the origin is the the turning number of p.

Since we have valid calculations of winding number
for piecewise bezier paths we instantly deduce a
valid calculation of turning number for the class \C.

I have not restricted the degree of the bezier paths
involved today since Jacko and I know winding number
algorithms that work well for all degrees.

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.
Indeed the degree of pp is one less than that of p so
pp will be quadratic for Metapost. For the quadratic
case, I have recently noticed that the 'refinement' or
'splitting' strategies prominent in algorithms
currently used for cubic and higher degrees become
entirely superfluous. I will hopefully find time to
explain that tomorrow.

Cheers

Laurent S.

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