[metapost] turning number revisited

[Dan Luecking]

At 06:54 AM 6/30/2011, you wrote:

>I believe I'm blind or silly or I completely mistunderstand you both
>(Dan and Larry) -- I cannot see the (simple) relation between cubic 
>and its derivative quadratic ... Assume, for example, that we have
>a square ABCD, and that its sides are approximated by "canonical"
>cubic splines (represented in MF/MP by the "--" operator), which,
>in this case, are just linear functions:
>   A + (B-A)*t     for t in [0,1]
>   B + (C-B)*(t-1) for t in [1,2]
>   C + (D-C)*(t-2) for t in [2,3]
>   D + (A-D)*(t-3) for t in [3,4]
>Therefore, its derivative is:
>   B-A  for t in (0,1) (observe that the intervals now are open)
>   C-B  for t in (1,2)
>   D-C  for t in (2,3)
>   A-D  for t in (3,4)
>so, the derivative of the original curve is constant
>over the interior of the intervals and undefined at
>their ends...

But Larry's construction of the differentiated path added
line segments corresponding to those places where the derivative
is discontinuous. For this example the differentiated path becomes

    (B-A)--(C-B)--(D-C)--(A-D)--cycle.

For a general

    p = <cubic> & <cubic> & ...

one would get (in general)

    p' = <quadratic>--<quadratic>-- ...

And the winding number of p' around (0,0) is the turningnumber
of p.

This is what Larry meant by using a winding number algorithm
_for quadratics_ to calculate a turningnumber for cubics; and
speculated (I think) that a winding number algorithm specialized
for quadratics might be an efficient way to calculate turningnumber.
(And I opined that turningnumber was already being handled at
the quadratic level, implying that there was unlikely to be any
improvement.)


Of course, rotating from B-A to C-B to C-D to A-D yields
>360 degrees. From what I understood reading MF sources,
>the algorithm implemented in MF makes somehow use of
>this property, am I right?

Yes. In addition to the turning of the curved portions, one
always adds the angles or turning at corners.


Dan


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