[metapost] turningnumber revisited
laurent at math.toronto.edu
laurent at math.toronto.edu
Mon Jun 27 10:52:24 CEST 2011
Hi all,
Winding number and turning number are integer
invariants that play significant roles in
Metafont and PostScript.
On Sat, 04 Jun 2011 i wrote:
> Which MP (or MF) paths are now claimed to have a well
> defined 'turningnumber'? And what are the properties
> asserted for the turning number function?
> And who cares?
> ...
> I could venture reasonable answers for those paths
> that are end-to-end composed of nowhere singular
> b'eziers paths that abut at nonzero angles.
To "abut at nonzero angle" means that at any time t
where two component bezier paths of a given cyclic
bezier path p abut, the angle is non zero
between the two control vectors there of the
two bezier paths.
[Use a constant width font for the figures below]
This local picture is OK
p(t)
-----------o-----------
/
/
and this is OK /
/
o-----------
but this is not OK o========== .
Turning number is used by Knuth in Metafont
(= MF) whilst winding number goes unmentioned. The
program Metafont defines turning number for all
piecewise bezier paths -- through its primitives
"turningnumber" and "turningcheck".
On the other hand PostScript uses winding
number, whilst turning number goes unmentioned.
Winding number is not an absolute invariant of a
cyclic path p; it is a joint invariant of p and a
point disjoint from the image of p.
MP (= Metapost) currently uses turning number
through the Metafont primitives (reprogrammed). Jacko
recently pointed out some anomolous behavior; it has
made me reappraise this notion as it might apply
to Metapost.
Incidentally, it is clearly time for
Metapost to introduce a "windingnumber" primitive.
Fortunately, this his poses no obstacles that
have not been overcome on this list.
In his Metafont book, Knuth defines turning
number clearly only for cyclic paths that lie on the
edges of a square pixel grid and are allowed only
turns of plus or minus 90 degrees (not 180 degrees
= "about turn"). The turning number of such a 'grid
path' is by definition the sum of the all the turn
angles at the turns of the cyclic path. (Incidentally
such paths lie in my June 04 class.)
Concerning the definition of turning number for
piecewise bezier paths Knuth merely states that the
Metafont program suitably approximates the path by
a path of the above restricted type and uses the
latter's turning number as specified above. This is
not a clear definition until one clearly specifies
how the the 'grid path' approximation is made. Who
can clarify?
There is a daring statement in the "Metafont
book" page 111:
<< Every cyclic path has a {\sl turning number\/} >>
This statement alarms me. What is the turning number
of the cyclic path
A -- B -- cycle ?
If turning number changes sign when a reflection of
R^2 is applied to the cyclic curve, then the turning
number is necessarily zero. Indeed, this path is
invariant under reflection in the line containing A
and B. This zero turning number seems OK in itself,
but what is the restricted grid path by which the
Metafont program defines the turning number? It
seems to me to be difficult to define such a path by
a rule that is local in nature.
I suspect that Metafont sometimes gives crazy answers
for turning number when applied to paths outside the
restricted class of paths for which I ventured that
I have a good definition of turning number.
Perhaps Knuth needed the turningcheck parameter
in part because of such craziness?
Having mentioned one subclass of piecewise bezier
curves that have a very well behaved winding number,
let me mention a much larger class of continuous cyclic
paths for which I can still unambiguously define a
well behaved turning number. It is the class of
continuous cyclic paths p: S^1 --> R^2 from the
standard circle to the standard cartesian plane that
are "locally injective" in the following sense:
There exists a sufficiently small positive e > 0
(this e depending on p), such that, if a and b are
distinct points in S^1 and the distance d(a,b) in S^1
is < e, then p(a) and p(b) are distinct points of
R^2.
For this much larger class, the turning number
of a cyclic path p is a topological invariant in the
following sense: If H : R^2 --> R^2 is any
homeomorphism of R^2, and h :S^1 --> S^1 is any
homeomorphism of S^1, then the composition
H p h : S^1 --> R^2 is clearly also a locally
injective cyclic path; its turning number is, up
to sign, the same as that of p. The sign \pm 1
relating the two turning numbers is the product
degree(H) degree(h) .
In the smaller class I proposed on 04 June,
winding number is stable under perturbation of the
points specifying (in the traditional way) a cyclic
piecewise bezier path.
Unfortunately, in the larger class just defined,
turning number is highly unstable under all the usual
notions of perturbation. But it is stable under the
not-so-usual notion of perturbation by 'topological
regular homotopy'.
Comments and quieries are welcome.
Cheers
Laurent S.
More information about the metapost
mailing list