[metapost] turningnumber revisited

laurent at math.toronto.edu laurent at math.toronto.edu
Thu Jul 7 07:17:29 CEST 2011



Hi All,

     From the conceptial viewpoint of pure
mathematics, the calculation of the turning number of
a cyclic piecewise bezier path p : [0,n] ---> R^2
that happens to be locally topologically immersive
seems now to me to be a fairly simple matter.  This
very roughly means that if MP had instant and
infinite precision floating point calculation
abilities I would be ready to program a turning
number calculation.  Today I'll make just a tiny step
towards justifying this optimism.

     Practical calculation of turning number in
today's MF/MP etc will be much more complex because
of instabilities and inaccuracies in MP practice
(that I probably do not yet fully understand!).
SO I WILL NOT PROGRESS ON PRACTICAL CALCULATION UNTIL
THE SIMPLER MATHEMATICAL DISCUSSION IS COMPLETE.

     Recall the class \C of cyclic bezier paths of 05
June, namely those 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 and dilation of R^2, about the point p(i),
having an angle that lies in the open interval
(-180,180). Angles are measured in degrees.

Note my correction of today

     "rotation" ==> "rotation and dilation"

in (b). It repairs an accidental glitch in my
definition of \C --- a glitch which seems not to
invalidate my discussions involving \C.

     On <Tue, 28 Jun 2011 02:40:50 -0400 (EDT)> I
have given a calculation of the integer turning
number for p \in \C in terms of the well-understood
winding number about the origin of a
"pseudo-derivative" path pp.  Since the class \C and
the winding number calculation are stable under
perturbation of the Casteljau data and under bezier path
subdivision, both the mathematical AND the practical
aspects of turning number for p in \C seem to be
in good shape.

     Today I mention the slightly larger class \C+.
It is defined like \C except that

     "(non-nul) direction vector"

replaces

     "derivative vector".

The direction vectors of the bezier paths
automaticly vary continuously.

     A key example of bezier path that may appear as
segment of  a  p \in \C+ and not in \C is:

 \b(A,B,C,D) with Casteljau polygon

            A=B --- C
                     \
                      \
                       D

The derivative vector at the point A=B is zero but
the direction vector there is the non-null direction
 (C-A) / |C-A|  .

     The good news of today is that the turning
number calculation algorithm I gave for \C on Tue, 28
Jun 2011 02:40:50 -0400 (EDT) obviously applies to
\C+.

     Unfortunately, instabilities of turning number
occur in \C+.  For example, the point A=B of the above
example is a cusp of its maximally extended cubic
path, and that path can devellop a loop under
perturbation. Thus *practical* problems for winding
number calculations remain for paths in \C+.

Cheers

Laurent S.





More information about the metapost mailing list