I'm trying to implement the straight skeleton algorithm as described by this paper: http://www.dma.fi.upm.es/personal/mabellanas/tfcs/skeleton/html/documentacion/Straight%20Skeletons%20Implementation.pdf

I am currently stuck trying to understand the author's description of the intersection point B as created from bisector of V, on page 4-5:

Page 4-5 of the paper

I am very confused by this description.

Point B can be characterized as having the same perpendicular distance to the straight line carrying the "opposite" line segment to the vertex V and from both straight lines containing the line segments starting at the vertex V . We have to find such an "opposite" line segment.

  • What exactly does opposite mean in this case?
  • Does "straight lines containing the line segments starting at the vertex V" refer to its adjacent edges of V?
  • Why does Figure 4 show a pre-constructed straight skeleton (the dashed line)? Or.. what is that even? I'm not sure what this diagram is supposed to show.

Please help thank you!


In this case, the edge opposite a vertex $V$ is the edge found by bisecting the interior angle at $V$ and travelling along that bisector through the polygon until an edge is reached. There seems to be an implicit assumption that you won't end up in the position of a square, where each vertex has no opposite edge because each vertex is, in fact, opposite another vertex.

You are right with your second statement; the straight lines containing the line segments starting at the vertex $V$ are indeed the adjacent edges of $V$. Note that in the figure $4a$) and $4b$) these lines are extended (as dotted lines) to show where the intersect the 'opposite' edge.

Figure $4$ is, I think, showing you how the skeleton is constructed, which is why the dotted line is there. Only the bits inside the shaded area are constructed using the point $B$; outside the shaded area they may change direction in order to meet up with the next constructed point (see the first Figure and compare it with the 'magnifications' of Figure $4$).

  • $\begingroup$ I am also working on the same paper and I don't think the opposite edge definition is that simple. In fact, the authors said it themselves that "Unfortunately a simple test of the intersection between a bisector starting at V and the currently tested line segment cannot be used." After trying out the intersecting method, I think you also need to figure out whether the point B is reside within the grayed out area. $\endgroup$ – Anh Tran Dec 24 '19 at 22:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.