[metapost] Re: [metafont] Honza's puzzler
Larry Siebenmann
laurent at math.toronto.edu
Sat Jan 22 05:43:31 CET 2005
*** 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.
More information about the metapost
mailing list