11

Is there a Python package which provides an implementation of a Straight Skeleton algorithm?

I'm aware that the open source (C++) project CGALcontains an implementation but it seems like cgal-bindings doesn't include this CGAL package.

In any case, I would prefer a pure Python implementation which I could modify/extend to suit my needs.

While an implementation that can handle polygons with holes would be preferable, it's not strictly necessary.

  • 1
    Have you tested pySkeleton or Skeletron? – Farid Cheraghi Mar 4 '15 at 19:48
  • I tried pySkeleton. The GUI application didn't work for me and I haven't found time yet to check if the code is salvageable – underdark Mar 4 '15 at 19:49
  • import polygon vertices = [(0,0), (0,5), (5,5), (5,0)] edges = [(0,1), (1,2), (2,3), (3,0)] p = polygon.Polygon(vertices, edges) skeleton_graph = p.straight_skeleton() __________________________________________________ While executing above i got the following error: _________ Traceback (most recent call last): File "C:\pySkeleton\pySkeleton\test.py", line 6, in <module> p = polygon.Polygon(vertices, edges) File "C:\pySkeleton\pySkeleton\polygon.py", line 44, in init self.vertices = map(Point,vertices) TypeError: __init__() takes exactly 3 arguments (2 given) – ramesh May 7 '18 at 12:35
6

Maybe you can modify pySkeleton by Olivier Teboul to suit your needs.

I haven't had the chance to look at the actual code but from what he says it should be pure Python.

2

You can use pySkeleton as follows:

from pySkeleton import polygon

vertices = [(0,0), (0,5), (5,5), (5,0)]
edges = [(0,1), (1,2), (2,3), (3,0)]

p = polygon.Polygon(vertices, edges)
skeleton_graph = p.straight_skeleton()

You get a Graph-Object with Nodes and Arcs, which you can access simply by:

nodes = skeleton_graph.nodes
arcs = skeleton_graph.arcs

As it says in the pySkeleton readme.txt, the polygon vertices needs to be in clockwise-order. For holes within the polygon, vertices needs to be in counter clockwise-order.

vertices = [(25.0, 15.0), (45.0, 15.0), (45.0, 35.0), (25.0, 35.0), # polygon
            (30.0, 20.0), (30.0, 30.0), (40.0, 30.0), (40.0, 20.0)] # hole in polygon

edges = [(0, 1), (1, 2), (2, 3), (3, 0), # polygon
         (4, 5), (5, 6), (6, 7), (7, 4)] # hole in polygon

Remark: For more complex polygons with 100+ vertices and edges pySkeleton is unfeasibly slow. Besides that I receive strange results for some polygons. I assume that it does not work correctly in all cases.

Nonetheless, big thanks to Olivier Teboul for this library.

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.