[metapost] turningnumber revisited
Dan Luecking
luecking at uark.edu
Mon Jun 27 20:11:48 CEST 2011
At 03:52 AM 6/27/2011, you wrote:
> 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.)
It is unclear what you mean here by "clearly". Knuth is
"clear in his definition only for such paths, but
it is "clear" to me that turning number does not rely
on digitization: MF's output on a "strange path" error
breaks down the path into parts that change direction in
multiples of 45 degrees (MFbook, page 119). Following a
gridded path would give changes of 90 degrees at a time.
> 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 ?
You can ask metafont: it seems to be 1 for most choices of A and B.
When a path makes an about face in a single point, MF could take
either of two interpretations: it is a 180 degree turn or it is a
-180 degree turn. For example, the triple cusp path:
(0,1){down}..{right}(1,0){left}..{down}(0,-1}--cycle
has turningnumber 2, indicating all three cusps are taken to
have 180 degree turns (plus 180 degrees worth of turning in the
curved segments). On the other hand, the "same" path in reverse:
(0,-1){up}..{right}(1,0){left}..{up}(0,1}--cycle
has turning number 0, indicating that at least one of the
cusps was given a value of -180..
>If turning number changes sign when a reflection of
>R^2 is applied to the cyclic curve, then the turning
>number is necessarily zero.
A little experimentation shows that MF's notion of turning
number doesn't even change sign when the path is reversed,
which would seem to be an obvious constraint. Both paths
above have a reversal with turningnumber of 1. All of the
following paths have turningnumbe 1:
p = (0,0)--(1,0)--cycle;
q = p yscaled -1;
r = p xscaled -1;
s = reverse p;
>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.
This definition does not rule out cusps, and the turning
number of a path with a cusp is ambiguous unless a way is
proposed to choose between a change of 180 and -180 at
the cusp.
Dan
Daniel H. Luecking
Department of Mathematical Sciences
Fayetteville, Arkansas
http://www-cs-faculty.stanford.edu/~knuth/iaq.html
More information about the metapost
mailing list