Fiete - Mi 03.02.16 15:22
Titel: konvexe Hülle einer Punktmenge

---

Das Programm ermittelt die konvexe Hülle einer Punktmenge(max.99 Punkte).
Die Lösung wird grafisch angezeigt.

Gruß Fiete

Horst_H - Mi 03.02.16 19:25

---

Hallo,

Oh, von 1988:
http://www.entwickler-ecke.de/viewtopic.php?t=82988
Da im Quelltext ständig Winkel berechnet werden, frage ich mich, ob das der Graham_Scan-Algorithmus [https://de.wikipedia.org/wiki/Graham_Scan] ist,

Gruß Horst

Fiete - Do 04.02.16 12:05

---

Moin Horst_H,

Zitat:

Oh, von 1988:

Es gab eine Aufgabe im BWInf 1987, nannte sich Goldgräberclaim.
Der Algorithmus sieht so aus: 1) suche linksuntersten Punkt
2) suche nächst äußersten Punkt, gibt es mehrere minimale Punkte, dann den am weitsten entfernten nehmen
Dies wird so lange durchgeführt, bis der Startpunkt erreicht ist.
Gruß Fiete

Horst_H - Fr 05.02.16 08:18

---

Hallo,

dann ist das wohl so etwas wie der Jarvis-March-Algorithmus [http://www.iti.fh-flensburg.de/lang/algorithmen/geo/jarvis.htm], dort sind noch andere Verfahren erklärt Konvexe Hülle [http://www.iti.fh-flensburg.de/lang/algorithmen/geo/convex.htm] (Dort wird auch beschrieben, das man den Winkel gar nicht so aufwändig berechnen muss, mit Wurzel und Divisionen)
Das Verfahren ist ja bei einer Punktewolke sehr schnell, da ja nur wenige ( h ) Punkte/Linien die konvexe Hülle bilden.Es wird also h*n mal gerechnet.
Ich fand besonders schön, wie die Punkte auf Aufstand erzeugt werden, indem getestest wird, ob an der Stelle auf dem Bild schon ein roter Punkt des vorherigen Kreises um einen Punkt ist.So braucht man keinen Speicher anlegen, um dafür zu sorgen.
Zum Beipiel indem man ein zweidimensionales Feld

anlegt und freie Punkte daraus wählt und mit Radius hochskaliert.Aber das sieht dann wieder zu gerastert aus.Man könnte auch Raster aus Sechsecken machen.Ich schweife ab...

Gruß Horst