Wie berechne ich gerade Skelette mit Python?

Gibt es ein Python-Paket, das eine Implementierung eines Straight Skeleton-Algorithmus bietet?

Ich bin mir bewusst, dass das Open Source (C ++) Projekt CGAL eine Implementierung enthält, aber es scheint, dass cgal-bindings dieses CGAL-Paket nicht enthält .

In jedem Fall würde ich eine reine Python-Implementierung bevorzugen, die ich an meine Bedürfnisse anpassen kann.

Eine Implementierung, die Polygone mit Löchern verarbeiten kann, ist zwar vorzuziehen, jedoch nicht unbedingt erforderlich.

Vielleicht können Sie pySkeleton von Olivier Teboul an Ihre Bedürfnisse anpassen .

Ich hatte keine Gelegenheit, mir den eigentlichen Code anzusehen, aber von dem, was er sagt, sollte es reines Python sein .

Sie können pySkeleton wie folgt verwenden:

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()

Sie erhalten ein Graph-Objekt mit Knoten und Bögen, auf das Sie einfach zugreifen können:

nodes = skeleton_graph.nodes
arcs = skeleton_graph.arcs

Wie in der pySkeleton-Datei readme.txt angegeben, müssen die Polygonscheitelpunkte im Uhrzeigersinn sein. Für Löcher innerhalb des Polygons müssen die Scheitelpunkte gegen den Uhrzeigersinn sein.

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

Anmerkung: Bei komplexeren Polygonen mit mehr als 100 Eckpunkten und Kanten ist pySkeleton nicht realisierbar. Außerdem erhalte ich für einige Polygone seltsame Ergebnisse. Ich gehe davon aus, dass es nicht in allen Fällen richtig funktioniert.

Trotzdem ein großes Dankeschön an Olivier Teboul für diese Bibliothek.