[metapost] Re: [metafont] Honza's puzzler

[Larry Siebenmann]

 *** A first tangent line census ***

     Suppose b is a (composite) bezier path of length l >= 1
in Knuth's sense (ie the concatenation of l simple b'ezier
cubic arcs with 4 control points each).

PROBLEM. Find *all* the lines L passing through
a given point z and tangent to b.  

Call this the tangent line census problem.

     *Interior* tangent lines L, are the ones of most
interest, *interior* meaning that the intersection of L with
b does not include b(0) or b(l).

     Here I use the discussion of yesterday to deal
completely with the case when  b  has NO CUSPS and 
 NO INFLEXIONS, and further turns through < 180 DEGREES.

Path  b  is then embedded and the foreward tangent ray at
b(0) and the backward tangent ray at b(l) intersect at a
point o (letter oh):

        \ forward tangent ray at b(0)
         \
          \
           \
            \
             \
              \
 <------------ o -------------------
 backward ray   \               x x    b(l)
    at  b(l)     \          x
                  \      x
                   \
                    \   x    path b
                     \
                      \  x
                       \
                        \ x

                           b(0)

These rays can be considered to be coordinate axes for R^2.

I now now distinguish 5 cases.  

(a) z is in the closed quadrant opposite the one containing
b.  No interior tangent lines!

(b) z is in either of the two open quadrants adjacant to the
one containing  b. Exactly one interior tangent line 
as explained yesterday!

(c) z  is on  b  but not on the axes.   There is exactly one
interior tangent line on  z  if z is not a corner of  b. 
The is a whole sheaf of tangent lines through  z  if 
if z is a corner of b.

Let Q be the interior of the quadrant containing b.

(d) z is in the unbounded component of Q - b, the one on the
concave side of  b. No interior tangent line through  z.

(e) z is in the bounded component of Q - b, the one near  o.
Exactly two interior tangent lines.  

Proof of (e) Extend the linear segment o--z to meet  b  at a
point v and take the two tangent rays to  b at v.  Then
apply the CONCLUSION of yesterday twice to assure exactly
two interior tangent lines through z.


Summary: the number of interior tangent lines through z
depends on the position of z  as indicated 
in brackets on this figure:

       
       \ forward tangent ray at b(0)
        \
         \
          \        [ 1 ]
[ 0 ]      \
            \
             \
 <------------ o -------------------
 backward ray   \               x x    b(l)
    from b(l)    \  [ 2 ]   x
                  \      x
                   \
                    \   x    path b
      [ 1 ]          \
                      \  x             [ 0 ]
                       \
                        \ x

                           b(0)

except for two unmarked cases 
 -- when z is on the axes: answer [ 0 ]
 -- when z is on b : answer in (c).

     The above easy but limited census can be used to attack
the general tangent line census problem by cutting up
general b into pieces of the above special sort.  The one
ticklish problem remaining will be to break up general b at
its inflexion points into pieces without inflexions.

Cheers

Laurent S.

PS.  Yesterday I wrote that the convergence ratio d'/d is
asymtotically d/D in the algorithm of Dirk and Jacko.  Dirk
says d/2D which is even better convergence, and he is
right. Sorry for the slip. I add that our calculations
assume that, at the point v of tangency, the curvature
radius R ot b at v exists and is finite.