Straight Skeleton (imperfect)
Straight Skeleton from HEM faces
Inspired by a comment, this morning I played around with the idea of composing straight skeletons for the faces generated by the Half-Edge Mesh Definition posted earlier.
A polygon’s straight skeleton resembles the voronoi skeleton or medial axis, but is composed of only straight segments (and typically fewer of them, a voronoi skeleton’s resolution is dependent on the number of sampling points along the perimeter, but more points means more segments in the skeleton as well).
Each face (extruded edges) has its own straight skeleton. The most complex, in the center, is still only 13 segments
There are a number of algorithms in existence for computing the straight skeleton. This one follows the following steps:
- Calculate the bisecting vector at each vertex
- Find the distance to the intersection of this vector with the bisectors before and after it
- If two consecutive vectors intersect sooner than either intersects its other neighbor, make an itersection and:
- Remove the spanned edge, the engaged vertexes and vectors
- Insert the intersection point to the vector list
- Recalculate the bisecting vector based on the two edges on either side of the intersection point
- Update the intersection distances in both directions
- Continues in a loop around the face until the last intersection is found
The calculation of the straight skeleton in steps
This process was easy to implement but does a have a few drawbacks. The first is that while it works on most polygons, because intersections are always calculated from the outside in, there are occasions where a better intersection will appear for a vertex after another intersection has already been calculated. This can cause the straight skeleton to “fold back” on itself or not complete at all.
The other drawback is that the skeleton cannot be calculated for polygons with holes in them because my Half-Edge Mesh definition does not accommodate faces with holes. This would require orienting the segments as inputs before any calculation of the mesh, which is a step I don’t want to require. This straight skeleton can, however, calculate multiple, detached faces (i.e. free-floating polygons), though you’ll want to cull through the output as each polygon will have an internal (good) skeleton and an inverted (bad) skeleton. The bad skeletons will seem to be directly overlaid but will include a number of unnecessary zero-length segments.
Quotidien 