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

[Larry Siebenmann]

Hi All,

Simultaneously, on Tue, 18 Jan 2005, Dirk Laurie
<dpl at sun.ac.za> (both lists?) and Boguslaw Jackowski
<bop at bop.com.pl> (metapost list only) proposed essentially
the same algorithm for obtaining a line tangent to a given
b'ezier curve  b that passes through a give point z.
Quoting Dirk: 

 > Here is an attempt.  The geometrical method is:
 > given an approximate tangent point, connect to
 > point z to give an approximate tangent; the new
 > approximate tangent point is the closest point on
 > the curve where the slope equals that of the
 > approximate tangent.  

I am as happy about this neat algorithm as Dirk and Jacko.

 > Exercise for the reader:
 > prove that under suitable conditions, this process
 > is quadratically convergent.

I tried this exercise, and came up with the following
specific estimate for rate of convergence to a tangent line
from z to a point w of tangency interior to a generic b'ezier
segment b: Let d be the distance from w of an approximate
tangent point v on path b, and let v' and d' be the
approximate tangent and its distance from w after one
iteration of the process.  Then the ratio d'/d is
asymtotically (R/D)*(d/R) = d/D, where D is abs(z-w) and R
is the radius of curvature of b at w, ie  d'/d approaches
this ratio as the number of iterations becomes large. I hope
Dirk will correct me if I have gone astray (and I often do).

I now formulate a useful condition that assures the
existence of one unique solution z--w of the tangent line
problem.

Suppose b is bezier with no inflexion point.

[ Aside: More generally b can be any continuous *convex* arc
in the plane. It need not be be bezier; it is just the image
of a continuous one-to-one map of a closed interval say
[0,1] of the line R into the plane R^2.  Convex means that
the cyclic path b--cycle is the frontier of a convex 2-disk
in R^2; equivalently, it means that if x and y lie on b  the
interval x--y is either in  b  or meets  b  in the end
points of x and y only. This is enough to assure that at
every point x of b there is at least one tangent line, and
maybe many --- as one has at corners of a composite bezier
curve.  There is also a well defined foreward tangent ray at
each point, and likewise a backward tangent ray much as for
b'ezier paths.]

Suppose that the foreward tangent ray at b(0) and the backward tangent
ray at b(1) intersect at point o (letter oh):

       \ forward tangent ray at b(0)
        \
         \
          \
           \
            \
             \
 ------------- o -------------------   
(backward ray)  \               x x    b(1)
                 \          x
                  \      x
  point  z         \
                    \   x    path b
                     \
                      \  x
                       \
                        \ x
                           
                           b(0)


These rays can be considered to be coordinate axes for R^2.
Suppose that the point z lies neither in the (closed)
quadrant of b, nor in the (closed) quadrant opposite to b,
but rather in the interior of one of the two others.

CONCLUSION. Then there exists a unique tangent line L to
path b passing through z and not touching the endpoints of
b. Furthermore when b is composite bezier cubic, the
algorithm suggested by Dirk and Jacko finds this unique
tangent line.

NB.  The line L is unique but the intersection of L with b
may be an interval rather than a point when b is composite.

     Later, I will try to go on to indicate how this leads
to an algorithm to find *all* tangent lines to a composite
b'ezier curve b that pass through a given point z.

Cheers

Laurent S.