Hallo Holger, hallo Leser,
vielleicht hast du Recht, ich dachte es würde die Sache leichter machen, wenn ich den "Mathe-Teil" auslassen würde, aber du hast Recht, man sollte schon wissen, was das Ding eigenltich machen soll ;)
Jetzt hatte ich etwas Zeit die Beschreibung zu dem Code rauszusuchen. Ich müsste den Code allerdings noch erweitern, ich brauche nämlich nicht nur das Polygon selbst sondern den Umfang, bzw. die Länge der Hülle, dass sollte aber eine getrennte Baustelle werden. Ich habe mit VBA syntaxtechnisch wenig Erfahrung und in der Programmiersprache des Code gar keine, daher hoffe ich auf Tipps oder Hinweise bzgl. der Umsetzung. Geht diese Konstruktion/Logik so in VBA? Falls ja dann versuche ich sie funktion für funktion nachzubauen, aber falls aufgrund von variablentypen oder funktionsrückgabewerte (bsp. kein array möglich), rekursion und Gültigkeit von Variablen...Probleme entstehen könnten, wäre es sehr hilfreich das im Vorfeld zu berücksichtigen und einen workaround zu finden...
Danke jedenfalls für das Interesse!
Jan
|
Algorithmus Graham-Scan
|
|
Eingabe: |
Array p mit n Punkten |
|
Ausgabe: |
Array p derart umgeordnet, dass die ersten h Einträge die Ecken des konvexen Hüllpolygons sind |
|
Methode: |
-
bestimme Punkt q mit minimaler y-Koordinate;
-
subtrahiere q von allen Punkten des Arrays (so dass q selbst zum Nullpunkt wird);
-
sortiere die Punkte des Arrays nach ihrem Winkel, und bei gleichem Winkel nach ihrem Abstand zum Nullpunkt (der Punkt q wird zu p0);
-
addiere q zu allen Punkten des Arrays (so dass die ursprünglichen Punkte wiederhergestellt werden);
-
// durchlaufe die Punkte und überbrücke konkave Ecken:
setze i = 3 und k = 3;
solange k<n
-
vertausche pi und pk;
-
solange pi-2 pi-1 pi nicht konvex
-
vertausche pi-1 und pi;
-
setze i = i – 1;
-
setze i = i + 1 und k = k + 1;
setze h = i;
|
Der Algorithmus hat die kleine Unschönheit, dass die letzte Ecke des berechneten konvexe Hüllpolygons eine 180°-Ecke sein kann (vgl. Bild 2). Wenn dies stört, ist es einfach, diese noch zu entfernen.
Die Methode isLess der Klasse Point implementiert einen solchen Vergleich. Sie wird in der Sortierfunktion des Graham-Scan-Algorithmus benutzt.
Die folgende Klasse GrahamScan implementiert den Graham-Scan-Algorithmus. Der Aufruf erfolgt mit
GrahamScan c=new GrahamScan();
h=c.computeHull(p);
|
Hierbei ist p ein Array von Punkten. Als Ergebnis der Berechnung werden die Punkte im Array so umgeordnet, dass die ersten hPunkte die Ecken des konvexen Hüllpolynoms in umlaufender Reihenfolge bilden.
Die weiteren Funktionen sind Hilfsfunktionen. Die Funktion exchange(i, j) vertauscht zwei Punkte im Array. Die FunktionmakeRelTo(p0) rechnet alle Punkte des Arrays relativ zu p0 als Nullpunkt um. Die Funktion indexOfLowestPoint() sucht den Punkt mit kleinster y-Koordinate, oder bei mehreren Punkten mit kleinster y-Koordinate, von diesen den Punkt mit kleinster x-Koordinate. Als Ergebnis wird die Position des Punktes im Array zurückgegeben. Die Funktion isConvex(i) testet, ob die Punkte pi-1 pi pi+1 eine konvexe Ecke eines Polygonzuges darstellen. Für das Sortieren der Punkte wird Quicksort verwendet.