I have been trying to find an easy to understand straight skeleton implementation for a simple, concaved, polygon with holes. The best paper I can find on this is: http://www.dma.fi.upm.es/personal/mabellanas/tfcs/skeleton/html/documentacion/Straight%20Skeletons%20Implementation.pdf
However, I got quite confused with the flow of the algorithm. Let just consider the easier case: a convex polygon.
- In step 1c, after finding out the nearer bisector intersection, the author store that intersection into a priority queue, according to the distance to the line that contains edge $e_i$. My question is, does this mean EVERY edge will have a priority queue? If this is not the case, what is $e_i$ that the author referred to?
- In step 2, and I assuming that every edge would have a priority queue, which edge does the author start with first? And when the author mentioned "continue on the step 2", does that mean continue the current loop iteration or move to the next iteration?
On that note, if anyone know a similar algorithm that has been implemented in Matlab, that would be great too.
Best Answer
$1$. It's a single priority queue. a) Because there are at most two bisectors per vertex and it wouldn't make sense to have a priority queue for at most two items. b) Because step $2$ speaks of “the priority queue” without referring to an edge. The edge $e_i$ referred to in step $1 (c)$ is defined in step $1 (b)$.
$2$. This is badly phrased. From the fact that step $2 (c)$ outputs three skeleton arcs before “continuing on the step $2$” and step $2 (d)$ would output two of those again, it seems that “continue” here is meant in the sense in which it's used in some programming languages, namely, start the next iteration of step $2$ from the top instead of moving on to step $2(d)$; but I'm not $100\%$ sure about that one.