[metapost] Re: the common tangent problem

[Larry Siebenmann]

`Honza` Prachar's Puzzler was:

 > Do you have any idea how to do a tangent to 
 > path p from point z.

The Jackowski-Laurie algorithm (possibly classical?) is 

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

Here is a more general problem to which much the same
method applies:

COMMON TANGENT PROBLEM. Given two planar paths  p  and  q,
find, if possible, a line L that is tangent to both  p  and  q
where L does not contain end points of p or q.

Here is a geometric description of an algorithm
to (attempt to) find L.

COMMON TANGENT ALGORITHM (possibly classical?)
Given a point u on p and a point v on  q, apply some
algorithm to find a points u' on  p such that the tangent to
p at u' is parallel to u--v.  Then similarly find a point v'
on q  at which the tangent line is parallel to u'--v. Then
repeat this process with u' and v' in place of u and v.
Iterate to (hopefully) get lines L(u'--v') converging
to the wanted line L.

(*) ASSUME, for simplicity, that  p and q are composite
bezier cubic.

Then 'some algorithm' would be 'directiontime' of MP. (For
more general curves one can often use a binary search
directly.)


(**) ASSUME, for more simplicity, that  both p and q have no
inflexions and turn through  > 0 but < 180 degrees.

Next, I give sufficient conditions assuring a unique
solution L to the problem,

The notion of *horizon of p*  intervenes. The horizon of  p
is the explicitly defined open set (call it Hp today) of the
plane in which we showed yesterday that for z in Hp there is
a unique line tangent to p through z and not containing
endpoints of p. For example, in the figure below, Hp is the
two quadrants marked [ 1 ]:
(USE CONSTANT WIDTH  FONT FOR FIGURES!)

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

                           p(0)

ASSERTION.  Granting (*) and (**), suppose q lies in the
horizon of p and reciprocally.  (The figure below
illustrates p and q satisfying these conditions.) Then there
is a unique solution L to the common tangent problem.
Furthermore the given algorithm finds the solution.



                         \ 
                          \
                           \
                            \       
                             \
                              \
                               \
                  ------------- o -------------------
                                 \               x x    q(l)
                                  \          x
                                   \      x
                                    \
                                     \   x    path q
                                      \
                                       \  x
                                        \
                                         \ x
           
       \                                    q(0)
        \ 
         \
          \
           \       
            \
             \
              \
 ------------- o -------------------
                \               x x    p(l)
                 \          x
                  \      x
                   \
                    \   x    path p
                     \
                      \  x
                       \
                        \ x

                           p(0)



I believe that the quadratic convergence asserted by Dirk
Laurie also applies here.  And hopefully a full census of
common tangents to p and q could be made by applying the
assertion and related considerations to suitably chosen
pieces of p and q.  

One application would be to draw using MP the convex hull of
any collection of composite b'ezier curves.

Has anyone encountered other potential applications for
common tangents?

Cheers

Laurent S.