Straight-Skeleton Algorithmus, Probleme mit Split-Events

PatrickWG

Hallo zusammen,

ich arbeite gerade an einer Implementation des Straight-Skeleton-Algorithmus und hänge gerade an der Berechnung der Split-Events. Die Edge-Events berechne ich einfach über Schnittpunktberechnungen der Winkelhalbierenden im R2. Für die Split-Events würde ich gerne das Verfahren von Eppstein verwenden, der diese Events im R3 berechnet (beschrieben hier:
http://compgeom.cs.uiuc.edu/~jeffe/pubs/pdf/cycles.pdf
). Im Prinzip berechnet man für jede Kante des Eingabepolygons eine Ebene mit einer Steigung von 45° in Bezug auf die Ebene des Eingabepolygons. Anschließend bestimmt man den Schnittpunkt der Winkelhalbierenden (ebenfalls mit einer Steigung von 45°) des Reflex-Vertex mit allen Kanten-Ebenen. Soweit so gut, ich bekomme meine Schnittpunkte, weiß aber nicht, wie ich dann mit diesen weiterarbeite. Kern des Algorithmus ist ja die Bestimmung der Distanz des auftretenden Events, bei Edge-Events ist das der senkrechte Abstand des Schnittpunktes zur adjazenten Kante, bei Split-Events soll dagegen gelten, dass der Abstand zur durchstoßenen Kante gleich dem Abstand zu den adjazenten Kanten des Reflex-Vertex ist, das krieg ich aber einfach nicht raus bei meinen Berechnungen...irgendwo werde ich da einen Denkfehler haben, vielleicht könnt ihr mir sagen, wo das wäre...

Dank euch,
Patrick

PatrickWG

Vielleicht war die Fragestellung zu speziell, dann versuch ichs mal etwas allgemeiner. Wie würdet ihr den Straight-Skeleton-Algorithmus angehen? Man findet in der Literatur Basis-Algorithmen, die auf Schnittpunktberechnungen der Winkelhalbierenden für Edge-Events basieren und ein einfacheres, aber nicht immer korrektes Verfahren für die Berechnung der Split-Events beschreiben. Allerdings möchte ich auf längere Sicht den Algorithmus auf gewichtete Kanten umstellen, darum ist das Ganze etwas schwieriger. Ich bin bei meiner endlosen Suche über diese Seite

http://twak.blogspot.com/2009/05/engineering-weighted-straight-skeleton.html

gestolpert, die im Prinzip genau das macht, was ich vorhabe, habe da aber Probleme, die sequentielle Abfolge der Schritte in jeder Iteration rauszulesen. Vielleicht seht ihr da ja mehr?

Was ist eigentlich deine Problemstellung? Hier kennt offensichtlich keiner den "Straight-Skeleton Algo".

Du willst das Skelett eines 2D Polygons herausfinden? Da hätte ich dir eine einfachere Lösung!

PatrickWG

Hey,

mein Problem ist eine klassische Anwendung des Straight Skeleton-Algorithmus. Ich will ein Dach für einen beliebigen Grundriss (der Grundriss ist die Eingabe in den Algorithmus, kann sowohl konvex, als auch nicht-konvex sein, sowie Löcher enthalten) berechnen. Da wird man in der gängigen Literatur auf Straight-Skeleton verwiesen. Der Einfachheit halber ist das Eingabepolygon planar, somit kann man das Ganze zunächst tatsächlich als 2D-Problem betrachten.

cschaedl

Hey Patrick,

ich bin auch gerade bei der Implementierung des Straight Skeleton Algorithmus und stecke ebenfalls am nichtkonvexen Fall fest an der Stelle des Split Events.

Hast die Implementierung fertigstellen können?

Grüße
Christopher

sorry, my german isn't so good

code.google.com/p/campskeleton/

for an implementation in java. Consecutive events are difficult, but the answer is in the code!

- twak

PatrickWG

Hey Christopher,

ich bin inzwischen ein Stück weitergekommen, u.a. aufgrund des Codes, den Twak geshared hatte (das ist der Campskeleton-Code). Ich bin bei meinen Versuchen irgendwann weg von dem Ansatz der 45°-Ebene und habe es mit der ursprünglichen Implementation der Split-Events versucht, wie sie auch von Felkel et al. vorgeschlagen wird. Das Verfahren funktoniert (nicht in allen Fällen, aber deckt schon einiges ab), und hat den Vorteil, dass es Distanz ebenso definiert wie bei Edge-Events. Damit bekam ich für Split-Events ganz gute Ergebnisse. Allerdings war mir mein Code etwas zu wirr, so dass ich mich an eine eigene Implementation des Ansatzes von Twak gemacht habe (schau mal auf diese Google-Code-Page), der Code ist leider relativ schwer nachvollziehbar, aber er hat da einen Blog, auf dem er seine Versuche mit dem Algorithmus beschreibt. Kernidee der ganzen Sache ist es, die Bestimmung der Events auf einen einheitlichen Berechnungsansatz zurückzuführen, das sind seine Height-Events. Was er macht, ist die Schnittpunktberechnung von jeweils 3 Ebenen. Der Vorteil der ganzen Sache gegenüber dem klassischen Ansatz ist die Tatsache, dass man hier Kantengewichte gut mit der Steigung der Ebenen verrechnen kann.
Im Prinzip tut man das Folgende:

- für je 2 adjazente Ebenen (gebildet durch die Polygonkanten und mit einer Steigung heraus aus dem Polygon, die bsw. durch die Kantengewichte festgelegt wird) testet man auf Schnitte mit allen anderen Ebenenkanten im Polygon
- wegen der Ebenensteigung hat man konzeptionell einen Sweep-Plane-Ansatz, darum ist die Distanz definiert über die Höhe (wenn du ein planares Polygon in der XY-Ebene hast, hatlt der Wert der z-Koordinate am Schnittpunkt)
- dann geht man im Prinzip so vor, wie bei Felkels Implementation, Events der Reihe nach, Nachbarupdates etc.
- Twak unterscheidet dabei nicht mehr zwischen Split-, Edge- oder Vertex-Events, ich habe die Unterscheidung wieder eingeführt, weil es die Nachbarschaftsupdates erleichtert

Im Prinzip folgt also dieser Ansatz genau der Logik von Felkel, allerdings verwendet es einen einheitlichen Berechnungsansatz für die unterschiedlichen Eventarten, erlaubt Kantengewichte und beschreibt direkt die Dachform. Ich bin aktuell noch dabei, das Ganze robuster zu machen (der Algorithmus leidet leider stark unter Floating-Point-Rundungsproblemen). In der Praxis denke ich aber, dass die Grundrisse, die ich dem Verfahren gebe, deutlich einfacher sein werden, als meine aktuellen Testformen. Sobald ich da was habe, was ich guten Gewissens teilen kann, stell ichs online!

Hoffe, das hat dir ein bisschen weitergeholfen?
Gruß,
Patrick

doudou

Hallo Patrick,

Haben Sie bereits Erfolge mit der Implementierung? Ich wollte ursprünglich einen Ersatz für MAT (Medial Axis Transformation) finden.

Viele Grüße!

Doudou