Making skeletons and mitred-offset curves

[n8willis]

It would be useful to extend the offset-paths functionality to find mitred-offset curves for complete closed contours.

The simplest practical application is deriving skeletons (as some proprietary Glyphs plugins do). My own interest is more along the lines of showing the contours, as some of the illustrations do at https://www.sthu.org/research/straightskeleton/ (which has links to nonfree implementation code, fair warning; studying the code there might trigger a reaction from those authors). For analytical reasons, not for interactive Glyphs tools.

This library seems to be the most closely-related work I can find; it would be a useful feature IMO.

[ctrlcctrlv]

MFEKstroke (underlying library: math.rlib) does this, I think, if I understood what you mean.

Be aware of MFEK/math.rlib#16, though (although I'm going to fix it soon, I have a patch around ⅔ done).

Given that Simon has been contributing to it…and given Simon wrote ufostroker, I assume he expects it to take over this task.

But maybe I'm just spamming you again, Nate. ;-)

[simoncozens]

No, this is asking for the opposite - given an outlined curve, find the open curve skeleton.

[ctrlcctrlv]

Oh I see! I have in the past cut off the ends of a path and then used FontForge's ability to interpolate curves…InkScape also contains a Path Effect called "Interpolate Sub-Paths":

This effect, I planned on writing into some MFEK library or another. I'd find it useful sometimes. It's in src/live_effects/lpe_interpolate.cpp. I planned on binding lib2geom somehow, perhaps via Ritual, then either rewriting these LPE functions in Rust or just copying the C++ file and linking it.

[n8willis]

But maybe I'm just spamming you again

Actually not funny.

then used FontForge's ability to interpolate curves

This is not interpolation; it's medial-axis finding. The generic algorithm is referred to as "grass fire." It can be done on any closed shape with an arbitrary number of contours. Every contour is offset inward by a fixed delta in each iteration. The corners and collisions where the offsets meet form the skeleton.

[n8willis]

For reference purposes, I have found a JavaScript implementation of medial-axis finding (and "scale axis" which is related, apparently) that operates on SVGs: https://github.com/FlorisSteenkamp/MAT

That was originally linked to from this StackOverflow question - https://stackoverflow.com/questions/29921826/how-do-i-calculate-the-medial-axis-for-a-2d-vector-shape ; it seems to be based on a 1997 paper called "New Algorithm for Medial Axis Transform of Plane Domain" which is, naturally, behind a paywall to those not in a Participating Institution. But it can, of course, be requested: https://www.semanticscholar.org/paper/New-Algorithm-for-Medial-Axis-Transform-of-Plane-Choi-Choi/70ae5b583303af0b4d60d356d08f8ed84e1babbc?p2df

There are a few other implementations out there that I've found so far, but the vast majority seem to be built around OpenCV and expect raster data. See this one for an intriguing header image — https://stackoverflow.com/questions/69184252/how-to-find-the-joints-and-endpoints-of-medial-axis — but the usual use case that explains the CV-slant is that medial axes are what you want self-navigating robots to use when avoiding obstacles: the medial axis is guaranteed to be equidistant from all barriers.

The only other real implementation I've found that operates on vector input is this GIS-oriented one that seems to expect polygons: https://github.com/fitodic/centerline

Obviously there's a lot of overlap between this problem and Delaunay / Voronoi tiling ("generalized Voronoi" at least), except that wanting to support quadratic & cubic contours is drastically harder (or at least drastically harder to do on GPUs etc, which again seems to be what most people are shooting for).

[n8willis]

This might also be interesting, given that it represents the solution in spline form (and given that it is accessible w/o paywallification): https://arxiv.org/pdf/1307.0118.pdf

[ctrlcctrlv]

In FontForge I only ever did it when I knew both sides of the path had the same number of points (incl. off-curve) as FontForge very poorly handles non-equal cases. So, yes, in FF it was interpolation, and if you cut both ends, much of the time it will be plain interpolation.

I realize that there's a harder problem above that yes

[n8willis]

much of the time it will be plain interpolation

No, it won't. A mitered offset is not an interpolation at all. It is a completely different operation.

[ctrlcctrlv]

@n8willis Did I say it was not?

Let me explain graphically all that I mean.

Often, when I do this, I have for example this closed shape:

As I said, I cut both ends.

I move both curves into different fonts.

In the FontView, «Element→Interpolate Fonts…»…

Yielding Untitled3.

Merging all back together, we have, in the direction of negative y, 2, 3, 1.

Where did the original shape come from, you may wonder? Just FontForge's Expand Stroke w/o Simplify, no trick…

All I am saying is that I routinely do work to both a "left" and "right" side to create an interpolatable "center", as would be a mitered offset.

Warning, I am about to try to be funny again. Actually, nah, it's too late. Good night. :)

[n8willis]

For the third time: a mitered offset is not an interpolation.

You are talking about a different problem.

[ctrlcctrlv]

I understand the algorithms are different for one versus the other.

All I have been trying to say this entire time is "I have had problems where this would have been useful, and I hack something similar by cutting it up and interpolating".

The Inkscape example I showed, those two curves are not interpolation compatible, it is more similar to what you're talking about and less similar to what FontForge does. Despite being called "Interpolate Sub-Paths". It is not interpolation in the VF sense.

The only reason I'm still going at this with you (you find me incredibly dense, I know) is just because I want to know what level of user intervention to create good input is okay, as it affects the difficulty of implementation.

[n8willis]

You are describing solely an alternative approach to 'derive stroke skeletons,' which I referred to in the initial issue as an example of "the simplest practical application" of mitred offsets. It is not the use case that interests me.

More importantly, 'derive stroke skeletons' is not the feature request here. "Find mitred-offset curves for complete closed contours" is. It is an extension of BezierPath.offset(). Alternative approaches to 'derive stroke skeletons' to do not solve the "find mitered offset curves" problem.

Maybe I shouldn't have even mentioned the word "skeleton" in the first place.

and I hack something similar by cutting it up and interpolating

Do it for an equilateral triangle then. Or a circle.

I want to know what level of user intervention to create good input is okay

NONE.

The hacking-something-together that you are describing is trying to solve a different problem. It does not solve this problem. You are describing a user-level, font-editing problem. This is a topology-level, non-interactive problem.