Straight Skeleton Madness (a plea for help)
After completing my work on boolean path operations, I have moved on to looking at algorithms for offsetting polygons. One of the ones that stands out is known as the 'straight skeleton' algorithm. This computes a set of connected paths which describe the position of verticies as the polygon offset size is altered. Unfortunately, it's only directly applicable to straight line paths (with mitre joins), but that's good enough for now. The algorithm is straightforward for convex polygons, but gets a little bit more complex when dealing with concave points, since this can lead to the creation of sub paths.
In theory, while the straight skeleton is not directly applicable to offsetting, it produces a structure which can be used to calculate an offset path. As an aside, the straight skeleton of a polygon is ideal for determining its 'roof structure' - which will be of use elsewhere in my software.
Progress on my .NET straight skeleton code has been slow but fairly decent. After overcoming a few issues, I now have an implementation which appears to work for shrinking polygons and which I thought worked well for expanding them too. That was until I noticed this class of shapes.
In essence, polygons with certain types of reflex (concave) vertices appear to spawn a series of skeleton arcs that are disconnected from the main skeleton. You can see why this is happening, as the spike in the outline grows (blue), it eventually overtakes an expanding edge (shaded in orange). The source of the new bisectors arcs in the skeleton is not the concave vertex itself, but it's neighbours. Unfortunately, the reference material I used to implement my algorithm doesn't appear to cope or mention these feature at all and they have left me stumped (and a little fed up too). So, if anyone can point me in a more sensible direction as to how to calculate them, please do so. I'd be very grateful!
The above image comes from Xara, here's my code's attempt. Clearly, it fails to generate either the orphaned arcs (orange area), and has a minor, but fixable problem with the skeleton arc from the vertex shades in yellow, which makes the overall outline look pretty catastrophic!
In theory, while the straight skeleton is not directly applicable to offsetting, it produces a structure which can be used to calculate an offset path. As an aside, the straight skeleton of a polygon is ideal for determining its 'roof structure' - which will be of use elsewhere in my software.
Progress on my .NET straight skeleton code has been slow but fairly decent. After overcoming a few issues, I now have an implementation which appears to work for shrinking polygons and which I thought worked well for expanding them too. That was until I noticed this class of shapes.
In essence, polygons with certain types of reflex (concave) vertices appear to spawn a series of skeleton arcs that are disconnected from the main skeleton. You can see why this is happening, as the spike in the outline grows (blue), it eventually overtakes an expanding edge (shaded in orange). The source of the new bisectors arcs in the skeleton is not the concave vertex itself, but it's neighbours. Unfortunately, the reference material I used to implement my algorithm doesn't appear to cope or mention these feature at all and they have left me stumped (and a little fed up too). So, if anyone can point me in a more sensible direction as to how to calculate them, please do so. I'd be very grateful!
The above image comes from Xara, here's my code's attempt. Clearly, it fails to generate either the orphaned arcs (orange area), and has a minor, but fixable problem with the skeleton arc from the vertex shades in yellow, which makes the overall outline look pretty catastrophic!
Comments
mail me at buffering;A;kulitorum dt com
Thanks.
You might want to take a look at the following:
http://www.cgal.org/Manual/last/doc_html/cgal_manual/Straight_skeleton_2/Chapter_main.html
P.S: Xara DOES NOT use a straight skeleton for the offsetting (or its implementation is broken), hence the odd spike you are seeing.
HTH
Fernando dot Cacciola @ scisoft-consulting dot com
Max