[metapost] turningnumber revisited

[Dan Luecking]

At 01:25 AM 6/28/2011, laurent at math.toronto.edu wrote:

>      There seem to be several sound principles that
>should and can guide the implementation of primitives
>on a graphics program. Here are some vaguely stated
>desiderata that hopefully apply to "turningnumber"
>in Metapost:
>
>(1) Since the MetaPost primitive "turningnumber"
>parallels a known mathematical invariant the "turning
>number" of suitable cyclic plane paths, the main
>properties of "turningnumber" should correspond as
>exactly as possible to those of the mathematical
>concept.

This is obvious, but I might modify that last atatement to
   "...as exactly as possible, but not more exactly than possible..."


>(2) The MetaPost program should issue a warning when
>"turningnumber" fails, i.e. seems to be undefined
>and/or to violate the properties of the mathematical
>concept.  This should happen only 'exceptionally'.

This is essentially impossible unless one specifies a
threshhold for issuing the warning, _plus_ a method for the
detection of cusps. (The problematic case is of course a
cusp where a change in angle of +/-180 occurs.)

A cusp within a cubic bezier can be detected by
the coincidence of roots of a certain quadratic. But the
extraction of roots is a discontinuous operation. Minor
changes in the coodinates of a path (say a rotation) could
turn a quadratic with a double root into one with roots
separated by epsilon (= smallest non-zero positive number).

A cusp at a node can be detected by comparing the direction
of the postcontrol and precontrol points. This can be done
in at least four ways: v1=(a,b) and v2 = (c,d) have the same
direction if
   angle v1 = angle v2 or
   a*d = b*c or
   a/b = c/d or
   unitvector(a,b) = unitvector(c,d).
These four methods of detecting a cusp can produce different
results. For example with the traditional precision
   angle(30,110.00001) = angle(21,77)
which indicates a cusp, but
   21*110.00001 - 77*30 = .00032,
which does not. Higher precision simply changes the threshhold
at which such differences occur.

If a path is rotated, then slight inaccuracies in the sine and
cosine of angles can turn a cusp into a non-cusp, and vice versa.

[Also, for the concept of winding number, imprecision in the
location of a point and the calculation of a path can turn
a point that is "on" a path to one that is not "on" it, producing
similar problems (not to mention the already discussed problem of
intersection of paths).]

[Good points 3 and 4 omitted]

>      Similar desidarata apply to the mathematical
>"winding number" concept and its projected MetaPost
>implementation "windingnumber". There, somewhat
>miraculously, no puzzling cases have surfaced
>(yet!?).

Read back in the archives when we disussed path intersection.
One of the examples included was path (call it P), which was
a subpath of another (call it Q). Clearly P and intersect,
but the intersetiontimes primitive said they did not, presumably
because of the inherent problems of fixed precision computation.

Exactly such a situation would render the winding of of Q about
a point problematic. So in this sense a puzzling case has already
surfaced. If one cannot determine reliably determine intersection
of paths, one cannot reliably determine whether a point is on a
path and therefore whether a winding number exists.


Dan


Daniel H. Luecking
Department of Mathematical Sciences
Fayetteville, Arkansas
http://www-cs-faculty.stanford.edu/~knuth/iaq.html