How To Compute The Mitered Offset Of A Polygon Using Its Straight Skeleton

I have a Straight Skeleton algorithm implemented in Python and would like to use it to offset the edges of a polygon. I have seen several papers suggesting this offsetting approac

Solution 1:

I'm not exactly sure what is going on with the offsets you show in your second image, however it should be quite straight forward to compute the offsets once you have the skeleton.

Each arc of the skeleton can be seen as a line segment (or ray) in 3space, with the 3rd coordinate being time. That is, it starts at some time t_s (when it was created in an event or as an initial wavefront vertex that is incident to an input point) and ends at some time t_v (if it is a bounded edge) in some wavefront event.

Now, to find an offset curve of distance t, iterate over all arcs, and for each arc you have not yet visited that exists at time t (i.e. t_s < t < t_e), start an offset segment in one of the two incident faces. Let this arc be a.

The question, of course, then is where does this segment end. To find its endpoint, walk along the straight skeleton face, initially moving along the direction of the wavefront propagation. That is, the next arc you look at is incident to a at t_e of a. Walk along the face until you find another arc, a', that is alive during t. This is where your segment stops. If you have not seen a' before, then there is another offset segment on the other side of a' that you can find in the same way.

Once you have looked at all the arcs of the straight skeleton, you will have a set of line segments that represents your offset curve(s) at time t.

This might be what you're trying to do, but it's not exactly clear from your animation.

Also, the skeleton you show appears to be correct (it's hard to see, because animation), but it appears your offset segments cross straight skeleton arcs. Each offset segment should always be confined to exactly one straight skeleton face (and it will be parallel to the input edge that is incident to and which emanated this face).

Also cf. P. and Held: Computing Mitered Offset Curves Based on Straight Skeletons (CADA, 12(4), 2015).