[metapost] Some observations on turning and self intersection

[Dan Luecking]

Before the current spate of emails on these subjects, I had been studying
them sporadicallly, but intensely. Mainly I had been interested in
curvature, hoping to find a way of estimating curvature reliably from the
control points. Curvature is important (for me) for determining when or where
certain _non-affine_ transformations one might wish to apply to a path break
down. An example is moving a path perpendicular to itself a constant distance
(the envelope problem) which I wanted to do in a MP macro.

I attempted to find all possible ways a cubic Bezier could behave. Perhaps
there is a book on this somewhere, but I couldn't easily find one so I tried
to come up with a small list of "typical" cubics that would generate _all_
possibilities by a combination of affine transformations plus these three
non-affine ones:
   time shift, that is change f(t) to f(t+c).
   time scaling, f(t) -> f(bt)
   "subpathing": f(t) defined for all t, cut it off at t=0 and 1

I've finally come up with the 12 examples below. Each is extremely simple and
easy to analyze. One can then obtain information about a Bezier path segment
by analyzing the appropriate one of these and applying all the
transformations that turn it into the desired path.

It might actually be possible to implement algorithms that compute
information this way. But for me the important point was to understand
the large scale behavior of cubics and detecting the existence of certain
effects (inflections, loops, cusps, etc.)

Here is how these cubics aris. Start with the general cubic

   f(t) = A + Bt + Ct^2 + Dt^3

Since we may shift as we like, let A=(0,0) and since we may rotate and
scale, D=(0,1) (unless D was (0,0) to start with). So

   f(t) = (at + bt^2, ct + dt^2 + t^3)   (*)

If D = (0,0) the the same analysis allows us to make C=(0,1) and then

   f(t) = (at, bt+t^2)

and so on. Instead of tediously going through all the cases, let me
explain one case and then just list the rest. Suppose case (*) with b <> 0.
Then xscaling (and perhaps reflecting) makes b=1 and a time shift give the
xpart this form:  t^2 - b^2/4. Then a shift and we have:

   f(t) = (t^2, ct + dt^2 + t^3)

now slant by -d (vertically: x->x, y->y-dx) to make the ypart ct + t^3,
then, if c <> 0, time scale by sqrt(|c|), follow with an xscale and a
yscale to get

   f(t) = (t^2, +/-t + t^3)

With the plus sign this is smooth and non-selfintersecting, with the minus
sign it has a loop. If c=0 one gets (t^2, t^3) which has a cusp.
That takes care of all the actual cubics. Here's the full list:

  (0,0)        trivial paths
  (0,t)        straight line
  (0,t^2)      half-line covered twice
  (0,t^3)      line covered once with a pause (f'(t) = (0,0)) at t=0
  (0,t+t^3)    same, but no pauses
  (0,-t+t^3)   line, but reverses direction at t=-1/sqrt3 and again at 1/sqrt3
  (t,t^2)      parabola
  (t,t^3)      y = x^3, ypart pauses at t=0
  (t,t+t^3)    like above, but ypart never pauses
  (t,-t+t^3)   as above, but ypart pauses twice.
  (t^2,t^3)    cusp at t=0
  (t^2,t+t^3)  smooth, no loop, inflections at t=1/sqrt3 and t=-1/sqrt3
  (t^2,-t+t^3) smooth, loop, selfintersecting at t=1 and t=-1.

Note that if one transformed a Bezier segment, keeping track what happens to
t = 0 and 1 through the time transformations, and ended up on the last one,
one could tell if a self intersection occurs inside 0 < t< 1: the
transformed times have -1 and 1 between them.

Finally, the sign of the function k(t) = f'(t) x f''(t) tells us the
direction of curvature, positive for counterclockwise. The sign changes
give inflection points. Linear transformations merely multiply it by the
determinant, shifts leave it unchanged. Time shifts in f(t) merely shift
time in k(t) and time scaling in f(t) by b multiplies it b^2. The last
three types above are the only ones where k(t) is quadratic and it has a
double root for the cusp, two separate roots for the unlooped variant and
no roots for the loop. Thus the lack of roots of k(t) detects (but does not
locate) selfintersection.

The formula for k(t) is
   k(t)/6 = (a x b)(1-t)^2 + (a x c)(1-t)t (b x c)t^2
where a = postcontrol 0 of f - point 0 of f
       b = precontrol 1 of f - postcontrol 0 of f
and   c = point 1 of f - precontrol 0 of f

The condition for a loop is then  (a x c)^2 < 4(a x b)(b x c).


This is probably all well known to geometers, but I only discovered it
recently and thought it might help with some of the questions discussed
here lately.


Cheers,
Dan


Daniel H. Luecking
Department of Mathematical Sciences
University of Arkansas