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.
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.
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.
