How to compute the mitered offset of a polygon using its Straight Skeleton

Question

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 approach unfortunately none of them provides specific information on how to achieve it. Among them:

• A CGAL implementation of the Straight Skeleton of a Simple 2D Polygon with Holes

Since the very definition of a Straight Skeleton is based on the continuous wavefront or grassfire propagation of the edges, it is specially suited for polygon offsetting. In particular, it can be used to obtain the so-called “mitered” offsetting were corners remain as such in the offset polygon

• Skeletons and offsetting: A topological point of view

If the skeleton of P is already known then the computation of a single offset curve for any given radius r is simple, efficient (linear time) and numerically stable. All one has to do is to traverse the skeleton in a certain way and insert element by element of the offset curve.

I tried for each edge to constrain the offsets to their surrounding "bones" but found that the output was not satisfactory: some offsets are not matching and I see gaps where lines should be touching each other.

(higher quality here)

Question: What is the correct way to compute the mitered offset of a polygon using its Straight Skeleton?

Answer 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).