12

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.

Farid Cheraghi
  • 8,773
  • 1
  • 23
  • 53
underdark
  • 84,148
  • 21
  • 231
  • 413
  • 1
    Have you tested pySkeleton or Skeletron? – Farid Cheraghi Mar 04 '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 04 '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 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 07 '18 at 12:35

2 Answers2

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.

Kersten
  • 9,899
  • 3
  • 37
  • 59
3

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.

poechtma
  • 31
  • 3