[metapost] The strangest issues?

[Giuseppe Bilotta]

Hello all,

as you probably know, for my PhD I'm working on the problem
of approximating the envelope of a Bezier curves with Bezier
curves. In particular, I'm interested in finding the "best"
(for some definition of best) single-curve approximation
(i.e. without resorting to splitting the original curve).

In doing so, I've found a very strange result, and I'm now
writing to this list to see where I may have made a mistake.

Notation: [t,n,m] denotes (1-t)^{m-n} t^n.

We start from our given Bezier curve \gamma:

P0 [t,0,3] + 3 P1 [t,1,3] + 3 P2 [t,2,3] + P3 [t,3,3]

If we call r the radius of the circular pen and N0, N3 the
unit vectors orthogonal to the tangents in P0, P3, then a
side of the envelope starts at the point

Q0 = P0 + r N0

and ends in

Q3 = P3 + r N3

(you have the - sign for the other side). For the
approximating curve \omega we choose two other control points
Q1, Q2 such that Q1-Q0 is parallel to P1-P0 and Q2-Q3 is
parallel to P2-P3; this ensures that the tangents at the
extrema of the approximation match the ones of the envelope
itself:

Q1 = Q0 + \lambda0 (P1 - P0)
Q2 = Q3 + \lambda1 (P2 - P3)

I think that so far it's all well known.

Kinch chooses \omega (i.e. the values of \lambda0 and
\lambda1) by forcing it to pass through the point of the
envelope that comes from t=1/2, with a tangent parallel to
the tangent of the envelope at that point. If the
approximation is not good enough, the original curve is
bisected and the process is repeated for each subcurve.

Of course, there may be (and in fact there are, most of the
time) other approximations (other values of \lambda0,
\lambda1) that are better. My measure of "better" is the
maximum and minimum distance between \gamma and \omega
(L\infty-norm).

Let's start with the math: looking analytically for a global
solution of the problem, we should enquire on the points
that minimize the partial derivatives of the distance
function:

F(t,\tau,\lambda0,\lambda1) =
  = (\gamma(t) - \omega(\tau))^2

Dependence from \lambda0, \lambda1 is implicit in \omega,
and we have that the partial derivative of \omega wrt
\lambda0 is:

3 (P1 - P0) [\tau,1,3]

wrt to \lambda1 it's

3 (P2 - P0) [\tau,2,3]

If we look for points of maximum and minimum distance which
are different from the extrema (hence in particular \tau is
different from 0 and 1), the equations

dF/d\lambda0 = 0
dF/d\lambda1 = 0

can thus be written as:

(*)
(\gamma(t) - \omega(\tau)).(P1 - P0) = 0
(\gamma(t) - \omega(\tau)).(P2 - P3) = 0

which are to be combined with

(\gamma(t) - \omega(\tau)).\omega'(\tau) = 0
(\gamma(t) - \omega(\tau)).\gamma'(t) = 0

(where . represents the dot product). Now have a
look at (*): since we're on a plane, from it we can deduce

(P1 - P0) x (P2 - P3) = 0

(where x represents the cross product). That is, the two
sides of the original curve must be parallel! Isn't this
ridiculous? Where did I go wrong?

-- 
Giuseppe "Oblomov" Bilotta