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

Larry Siebenmann laurent at math.toronto.edu
Fri Jan 21 07:42:37 CET 2005

```
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.

> prove that under suitable conditions, this process

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)
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.

```