Java library for creating a direct skeleton?

Question

I have a 2D polygon with holes as input, and I need to find its rectilinear skeleton, as 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 give me a good explanation of the algorithm so that I can implement it myself? (I did not find good resources on Google)

Answer 1

I wrote this a little back. Not sure if he is enough enough. http://code.google.com/p/campskeleton/

Website here: http://dcs.gla.ac.uk/~tkelly/bits/wss/launch.jnlp

Answer 2

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

Answer 3

Edit: Ah. I see that “ Straight Skeleton is a technical term. The Wikipedia article refers to several algorithms. Have you looked at them?

---

As I understand it, you have a (convex?) Polygon. 1 or more (potentially non-convex) polygons are subtracted from it. You want to turn the result into many polygons without holes. Are there any additional rules that you are trying to apply?

I find it difficult to find the ruleset from the example you provided. External polygons are not convex; therefore, it does not seem to you that you are trying to find a convex set to represent the result (which is a relatively common task).

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

Answer 4

You can use the JTS Topology Suite . This is a very capable library that I used in a number of projects - never for a direct skeleton, but it is possible.

Answer 5

May I ask u what is your goal to find a straight skeleton? Is it personal or commercial? I would be interested to know how you use it to solve problems in real time? I have a Java library that does this. My algorithm is listed here http://web.stcloudstate.edu/rsarnath/skeleton/definition.htm