[metapost] METATYPE1 pen-stroking and tight curves

[mskala at ansuz.sooke.bc.ca]

On Wed, 19 Sep 2012, Shriramana Sharma wrote:
> Hi Matthew. I've also been working on the same problem but from a different
> angle. Would you please explain why/how you arrived at or at least justify
> that formula involving those dot products?

Under these definitions:

> >             z0=(point l of p)/100;
> >             z1=(postcontrol l of p)/100;
> >             z2=(precontrol (l+1) of p)/100;
> >             z3=(point (l+1) of p)/100;

the path leaves z0 at time l heading toward z1 (that is, in the direction
(z1-z0)), and arrives at z3 at time l+1 heading from z2 (that is, in the
direction (z3-z2)).  I'm interested in whether it has made a tight turn
between those two times; so I'm interested in the angle between (z1-z0)
and (z3-z2).  Call the angle between them theta.  The value of the dot
product
   (z1-z0) dotprod (z3-z2)
is equal to the length of (z1-z0) times the length of (z3-z2) times the
cosine of theta.  The cosine of theta ranges from +1 (vectors pointing in
the same direction - not a tight curve) to 0 (vectors perpendicular -
that's a fairly tight curve) to -1 (vectors pointing in opposite
directions - a very tight curve and definitely a problem situation).

But I can't just look at the magnitude of that dot product because it
scales with the vector lengths.  Scale the coordinates up by a factor of 2
and the dot product will increase by a factor of 4.  So I want to divide
by another factor that will scale the same way, but will not depend on
angles.  The dot product of a vector with itself, equal to the length of
the vector squared, behaves that way.  So I divide by
   (z2-z1) dotprod (z2-z1)
to cancel out the length scaling.  What I'm left with is a number that is
something like (but not exactly the same thing as) the cosine of the angle
between the starting and ending directions of the path segment.  It will
be greater for segments that don't curve tightly, and lesser (sometimes
even negative) for segments that curve tightly.  When a segment is cut in
half, this number will tend to be greater for the halves than for the
whole, because absent inflection points, each half turns through about
half as many degrees as the whole.  (Smaller angle, greater cosine.)  So I
can compare my ratio against a threshold (in this case 0.5) to determine
whether I want to split:

> >        if ((z1-z0) dotprod (z3-z2))/((z2-z1) dotprod (z2-z1))<0.5:

I don't have a strong justification for using (z2-z1) in particular in the
denominator.  I tried several possibilities and that one seemed to work
best.  (And this formula itself is, as I mentioned, just the most
successful of many I tried.)  The threshold value 0.5 to compare against
similarly came from trial and error; I suspect that the most effective
value is related to the typical ratio between pen size and stroke length,
since that ought to be relevant and doesn't seem to come into the formula
in any other way.  Using (z2-z1) seems like it could cause trouble
(division by zero or numeric overflow) if z1 and z2 are equal or nearly
equal to each other, which is certainly a permitted case for paths; but I
haven't observed that to occur in practice and will deal with it if and
when it becomes a problem.

-- 
Matthew Skala
mskala at ansuz.sooke.bc.ca                 People before principles.
http://ansuz.sooke.bc.ca/