[metapost] METATYPE1 pen-stroking and tight curves

[mskala at ansuz.sooke.bc.ca]

On Thu, 20 Sep 2012, Shriramana Sharma wrote:
> Hi Matthew -- did you consider finding the radius of curvature
> (http://en.wikipedia.org/wiki/Curvature) and testing it against the
> radius of the stroking pen?

Yes - the problem with that is that if I add nodes to a segment, the
radius of curvature won't change.  So that by itself can't be the only
condition, because if the only rule is "add a node when the curvature
radius is smaller then the pen," there's no way to know when to stop.
Maybe it could be combined with some other condition, though - maybe if
the radius of curvature is smaller than the pen, then we should subdivide
until the arc length is smaller than some limit (which might also be a
specific fraction of the pen size)?

> Also, re your previous remarks on how to find and introduce inflection
> points, have you considered testing for the cross-product of the first
> and second derivatives being zero? See
> http://www.caffeineowl.com/graphics/2d/vectorial/cubic-inflexion.html
> (but the algorithm is documented elsewhere too, like in
> http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.86.8080&rep=rep1&type=pdf
> p 4 so I hope it's not the unique discovery of the caffeineowl
> author.).

That's probably a better way to do it than the iterative method I talked
about earlier - as I said, that was a draft.  It should be reasonably easy
to find the inflection point analytically and once that's done, it's easy
to split the curve there.

However, I don't think inflection points are such a big issue; they're
relatively easy to avoid manually.  I've found the tight-radius corners to
be harder to deal with.

> Do let me know of any progress you have in this regard as I am sure my
> project will also be benefited.

Really solving this nicely (including the weird cases, not just a "good
enough in practice" approach) would be an interesting computer science
research problem.  I wonder if I can interest some of my academic
colleagues in it.
-- 
Matthew Skala
mskala at ansuz.sooke.bc.ca                 People before principles.
http://ansuz.sooke.bc.ca/