To recap, straight skeletons are useful data structures for calculating the offset path for a (simple) polygon. They are also used for calculating roof structures. Most of the material I've found on the web seems to be concerned with calculating internal skeletons, although no distinction is usually made between the two types.
To be able to expand polygonal paths I need to be able to calculate external skeletons. Unfortunately, I've found that these are less frequently discussed and appear to have features that you don't encounter in internal skeletons. I've nicknamed these 'breakthrough verticies'. These occur when a 'pointed' section of a path overtakes and punches through a different edge as the path is expanded. They produce skeleton arcs that have no parent node in the original path, and may be completely disconnected from the main skeleton.
My original implementation of a straight skeleton algorithm had no concept of these features. While it handled a lot of external paths with no problems, it was unable to cope with paths with breakthrough verticies, producing odd looking results (as covered in an earlier post). I have now managed to modify my original algorithm to cope with these.
The first example uses the path that originally alerted me to the problem. It contains one breakthrough edge and is a relatively trivial test case. Note how the skeleton contains a group of arcs centred on the source of the breakthrough event and how these affect the offset path.
A more complex example of a breakthrough event is shown in the next example. In this case, the breakthrough location occurs at a point where an edge has already disappeared. The breakthrough arcs are also connected to the main skeleton.
The final path shows another potential issue. In this case, two breakthrough edges coincide, producing several arcs centered on the breakthrough location.
Hopefully, these examples illustrate some of the complexities you can encounter when it comes to external skeletons. In each case, I've had to refine my code, while testing that I haven't broken something else. Unit tests have been a great help here, and yes, altering my code caused simpler cases to break several times. Really frustrating! There's bound to be some path out there that I haven't considered yet, but at the moment I'm pleased with my results.
Out of interest, breakthrough points occur more frequently than you might expect. However, if you're just calculating small offsets, you may not notice that your code doesn't cope with them. One of the paths in my earlier post actually has a more complex external skeleton that is shown, but this was not obvious at first. It was only when I went back and reran my previous tests (after adding some new code) that the skeleton changed to something that I thought looked odd, but it was correct.
No comments:
Post a Comment