[metapost] turningnumber revisited

laurent at math.toronto.edu laurent at math.toronto.edu
Fri Jul 1 08:18:29 CEST 2011


Hi Jacko, and others

Supoporting Dan, Jacko has presented the following
example where "subpath" and "intersectiontimes"
together conspire to overlook a genuine intersection
point of two bezier paths.

 >... Thu, 30 Jun 2011 08:00:32 +0200
 >...
 > path p,q,r;
 > p:=(0,0){up}..{down}(100,0); % just an arc
 > q:=subpath (2/5,3/5) of p;
 > r:=subpath (3/5,4/5) of p;
 > show q intersectiontimes r;
 > show point 1 of q;
 > show point 0 of r;
 > end.
 >
 > The log file reads:

 >> This is METAFONT, Version 2.718281
 >>  [...]
 >> (-1,-1)
 >> (64.8003,47.99994)
 >> (64.80087,47.99976) )

I am duly alarmed. Same result for MP in versions < 1!

Is it not a MF/MP bug for MF/MP to accept two rather
distinct points for the "point 3/5" of bezier path p?
I would argue that it is trivial to program the
primitive "subpath" so that the points are identical.
(What is Knuth's algorithm for subpath?) Here their
distance is about .0005 bp.

If this is not the bug, then it seems to me that
either the "intersectiontimes" primitive is ill
adjusted because its threshhold distance (for
declaring non-intersection) is too small, OR something
more serious is wrong in Knuth's "intersectiontimes"
algorithm.

Can you clarify this nasty example?

 ---------------------

You are still mystified by my use of a certain
'pseudo-derivative' pp of a cyclic piecewise bezier
path p.

 > But what I do not understand is that we work with
 > cubic splines, hence the only way of simple "degree
 > lowering" is differentiation.

True. But that loses almost nothing! In the classical
case when the given cyclic path p is smooth (or
continuously differentiable) for all t, one can
reconstruct p exactly from the its velocity
(or derivative) path p' by
vector integrating p' from the initial point p(0):

          p(t) = \int_0^t p'(t) dt

Thus p(0) and p' together are a legitimate
presentation of p.

In case p lies in my class \C, from the
"pseudo-derivative" pp that I defined, one easily
constructs a smooth cyclic path ppp that one can show
to be topologically regularly homotopic to p. Hence
ppp has by definition the the same turning number as
p.

In the special case of your square path p, a suitable
choice of the path ppp can be the boundary of a
small epsilon neighborhood of the square with
boundary p.

A so-called "topological regular homotopy" of a
topological immersion S^1 --> R^2 is merely a
continuous path in the space of topological
immersions that is *uniformly* locally injective
when viewed as a map  S^1 x [0,1] --> R^2. (This
uniformity prevents prevents loops from being
killed by shrinking to nothing.)

     All this theological stuff is to guide us to a
definition of an integer turning number that is
well behaved and computable by MP for all cyclic
piecewise bezier paths that do not 'backtrack'.
Some nice properties,  of which the first two have
already been mentioned:

(*)

 | The turning number of a cyclic and topologically
 | immersed path p is an integer well defined and
 | invariant under topological regular homotopy of p.

(**)

 | The turning number of an immersive 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)   .

Here is another:

(***)  The turning number of any topological embedding
S^1 --> \R^2 is \pm 1 and equal to its
winding number about any point in its interior.

This follows from  (**) and the Osgood-Schoenflies
theorem already mentioned.

Cheers

LS




More information about the metapost mailing list