[metapost] Feature Request: Get envelope of path stroked with arbitrary pen

Peter Wilson herries.press at earthlink.net
Fri Feb 9 19:41:16 CET 2018

On 09/02/18 00:36, mskala at ansuz.sooke.bc.ca wrote:
> On Thu, 8 Feb 2018, Kevin Keith wrote:
>> It would be of immense use if it were possible to get the path of the
>> outline of some arbitrary pen stroke.
>> Since metapost already outputs bezier curves, instead of bitmaps, it would
>> seem that the machinery to compute the envelope is already in place, so it
>> shouldn't be too difficult to expose this as an operator in the language
>> itself.
> I agree this would be nice.  However, I don't think it's so easy to do.
> METATYPE1 (used by the Latin Modern project and my own Tsukurimashou) has
> an implementation in Metapost macros; it usually works, but requires
> handholding, and when it fails it's difficult to debug.  FontForge also
> has an implementation of a similar feature, which has always been buggy
> and a cause of user complaints.  If it were to be a Metapost language
> feature, I hope that the implementation would be at the standard of
> quality and non-bugginess that we expect of "engine" code in the TeX
> ecosystem - and I think algorithms to actually achieve that on the "expand
> stroke" problem may be an open research problem.  Among other issues, the
> envelope of a path defined by cubic splines is not itself a cubic spline,
> so you need to do some approximation, and coming up with rules for how
> close the approximation needs to be, that cover all cases, is difficult.

In the 1980's I was involved in the TRUCE (Tri-Rational Unified Cubic 
Engine) project at the GE Research Laboratories, aimed at automatically 
generating NC (Numerically Controlled) tool paths for machining 
components from solid (geometric) models. Part of this was trying to 
solve offsetting a cubic curve into another one (which would not be a 
cubic and in general could be self-intersecting). As far as I am aware 
there were no publications about this but useful practical algorithms 
were developed about which I have no useful knowledge.

It is a HARD problem.

More information about the metapost mailing list