Java library for creating straight skeleton?

Question

I have as an input a 2D polygon with holes, and I need to find it's straight skeleton, like in the picture:

http://www.cgal.org/Manual/3.2/doc_html/cgal_manual/Straight_skeleton_2/exterior_skeleton.png

Maybe there is a good Java library for it?

And if not, can you point me to the good explanation of the algorithm, so I could implement it myself? (I haven't found good resources on Google)

Answer 1

See http://www.sable.mcgill.ca/~dbelan2/roofs/roofs.html which contains an applet.

Answer 2

You may be able to use the JTS Topology Suite. It is a very capable library that I've used on a number of projects - never for straight skeleton, but it may be possible.

Answer 3

Can I ask u what is your purpose for finding Straight skeleton? Is it personal or commercial? I would be interested in knowing how you r using it to solve real time problems? I do have a java library that does that. My algorithm is listed here http://web.stcloudstate.edu/rsarnath/skeleton/definition.htm

Answer 4

I wrote this a little while back. Not sure if it's robust enough. https://github.com/twak/campskeleton

(edited for 2018...)

Answer 5

Edit: Ah. I see that "Straight Skeleton" is a technical term. The wikipedia article references several algorithms. Have you looked at those?

---

As I understand it, you have a (convex?) polygon. From it, you subtract 1 or more (potentially non-convex) polygons. You want to turn the result into a set of polygons without holes. Are there extra rules that you're trying to apply?

I have a hard time coming up with a set of rules from the example that you provided. The outer polygons are non-convex; so it doesn't seem like you're trying to find a convex set to represent the result (which is a relatively common task).

If you could use the breakdown shown below, the algorithm is pretty simple. Can you clarify?