[metapost] turning number revisited
Dan Luecking
luecking at uark.edu
Fri Jul 1 05:57:46 CEST 2011
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
More information about the metapost
mailing list