[metapost] re: envelope approximation

[Larry Siebenmann]

Greetings Youping Huang,

Welcome to the metapost list. 

You write:

 > I have been working on numerical solutions of the 
 > envelope of a path. My metapost program with a brief
 > explanation, and a few examples are included. The 
 > solutions look quite good.
 > 
 > It can be considered as a response to the challenge 
 > posted by Laurent Siebenmann to tex-fonts on May 6, 
 > 2003.

Roughly stated, the challenge was to demonstrate means for
finding the best and most efficient
piecewise-bezier-cubic approximation to th envallope of
an elliptic pen stroking a single bezier cubic segment.
Here the envelope means the frontier of the region inked
(as by mf or mp).

Your answer is the second posted (after one by Lars
Hellstrom (on "the tex fonts" list 2003) using least
squares approximation. And several efforts are still
under construction.

I agree that your results are promising.

One of your key ideas, the use of many normal lines to
evaluate approximation is one that I have been
exploiting. I therefore quickly recognized, in your
prose description, a conceptual error you have been
making whenever your elliptical pen is non-curcular.  I
will explain it below. To make a long story short, I
say exactly how to circumvent the error; and when you
have done so your approximations will be somewhat
better for non-circular pens.

I hope this helps.  I am away from my mf and mp
environment for the next couple of weeks so am 
unlikely to respond further for some time.

Best wishes,

Laurent Siebenmann


 %%% Normal line method for 
     approximation of a smooth curve %%%

If c(t), t\in [0,1], is a smooth, embedded, and
explicitly parametrized curve in the plane R^2, we seek
the closest approximation to it by by a smooth bezier
cubic b(t) t\in [0,1]. By closest we mean that the
*maximum* distance from the curve image c([0,1])
attained by b(t) for some t\in [0,1] is (nearly) the
least possible among bezier cubics that assume the same
position and direction at times t=0 and t=1.

The normal line method exploits the family of straight
normal line segments to c and of radius =< some positive
\delta small enough that they give an "normal tube" T
about c([0,1]) in R^2, parametrized thus:

      T = c([0,1]) x (-\delta,\delta)

with c([0,1]) x 0 identified naturally to c([0,1]). In
fact, \delta < the inverse of the maximum curvature of c
in [0,1] will serve provided that c turns through < 180
degrees.  The point c(t) x d in the normal tube T lies
then at distance in R^2  exactly d from the curve
c([0,1]) and the (unique!) closest point on the curve is
 c(t) x 0 in T which is identified to c(t) in R^2. These
are facts from second year calculus of two variables, or
from introductory differential geometry.

We consider only those bezier cubics b that cut all
these normal segments transversely.  (There may be
none, in which case one has to split c and start over
until there is.) When one exists there are a host of
(mostly complicated!) minimax methods for finding the
best b (or nearly).  Youping has one that will work
well; I have another.

Now, where is the flaw in  Youping's proceedure?
It is 

 > The error of our approximation is defined as the 
 > maximum difference between Env and env along normal 
 > lines of p.

Youping's offset curve Env is our  c and his env is our
b. Our lines normal to c = Env giving the correct
distance criterion are unfortunately not the lines normal
to Youping's  pencenter curve p *if* the elliptic pen is
not circular. However I am sure Youping can quickly
correct his method using the above comments.  It is just
a matter of using a different family of "normal" lines. 
His method already seems OK for circular pens.

Incidentally, there was also a conceptual error implicit
in Lars Helmstr"om least squares approach (see
discusion on the tex fonts list 2003) and no clear fix
has been proposed.