"Punktwolke" erstellen?

**chip**

Hi,

ich würde gerne eine Punktwolke erstellen. Sprich so etwas: http://justinandrewjohnson.com/sites/default/…status_side.png

Allerdings NICHT als grafische Ausgabe sondern lediglich als Datensatz in einer Datenbank in der die X und Y Koordinaten der Punkte gespeichert sind sowie, wie auf dem Bild zu sehen, die Verbindung der am nähesten zwei Nachbarn.

Sprich also:

Tabelle Punkte: id, y, x
Tabelle Verbindung: Punkte_id_1, Punkte_id_2

Ich hatte zuerst überlegt ob das ganze irgendwie über Fraktale, wie es ja schon einige Beispiele hier im Forum gibt, zu realisieren ist, allerdings enden Fraktale ja auch am Ende in einer Symmetrie und ich brauch ja ein "Chaos".

Hat jemand einen Ideenansatz?

**AspirinJunkie**

Soll die Punktwolke ein Muster haben oder einfach nur zufällig?
Die Tabelle "Punkte" ist im zufälligen Fall ja schnell per Random in einer Schleife schnell erstellt.
P.S: wenn es eine Punktwolke wie im Bild werden soll brauchst du noch zu x und y eine dritte Koordinate.

Für die Nearest-Neighbour-Suche sollte man dann unbedingt auf entsprechende Algorithmen statt Brute-Force zurückgreifen (vor allem kd-Baum basierte Methoden).
Schnell geht es mit der FLANN-Bibliothek. Für diese hab ich mal einen rudimentären Wrapper geschrieben: >>FLANN in AutoIt<<.

**chip**

Zitat von AspirinJunkie

Soll die Punktwolke ein Muster haben oder einfach nur zufällig?
Die Tabelle "Punkte" ist im zufälligen Fall ja schnell per Random in einer Schleife schnell erstellt.
P.S: wenn es eine Punktwolke wie im Bild werden soll brauchst du noch zu x und y eine dritte Koordinate.

Für die Nearest-Neighbour-Suche sollte man dann unbedingt auf entsprechende Algorithmen statt Brute-Force zurückgreifen (vor allem kd-Baum basierte Methoden).
Schnell geht es mit der FLANN-Bibliothek. Für diese hab ich mal einen rudimentären Wrapper geschrieben: >>FLANN in AutoIt<<.

So in dem Bildbeispiel zufällig.
Stimmt soweit hatte ich noch garnicht gedacht :D.
Warum noch einen dritte Koordinate?

Danke ich schau mir das FLANN mal an.

**AspirinJunkie**

Zitat von chip

Warum noch einen dritte Koordinate?

handelt es sich nicht um eine 3D-Punktwolke in dem Bild?

Ansonsten schaue ich mir gerade die Karte an und stelle fest, dass gar nicht nur die jeweils nächsten Nachbarn verbunden sind sondern "willkürlich" die Punkte verbunden sind.
Nach welchem System die Punkte untereinander verbunden sind ist dort nicht wirklich ersichtlich.
Desweiteren sind im Grunde alle Punkte mit allen (über jeweils andere Punkte) verbunden.

Um diesen zu erreichen fällt mir spontan folgender Algorithmus ein:

Betrachten wir die Punktwolke als Graph bei dem erstmal alle Punkte untereinander verbunden sind. (also mit einer vollbesetzten Adjazenmatrix).
Dann picken wir einen zufälligen Punkt als "Ziel" heraus.
Für alle anderen Punkte wird der kürzeste Pfad zu diesem Punkt ermittelt - alle anderen Verbindungen werden gelöscht.
Jeder Punkt im Graphen ist dann nur mit jeweils einem verbunden aber in der Gesamtheit ohne Lücke.

Yaerox

Zitat von chip

~~Warum noch einen dritte Koordinate?~~

~~Ich denke @AspirinJunkie meint mit 3ter Koordinate die Verbindung zum "Nearest-Neighbour" damit du eben kein "Brute-Force" machen musst.~~

Sry hatte nur die ersten 3 Beiträge als ich die Antwort schrieb.

**chip**

Zitat von AspirinJunkie

handelt es sich nicht um eine 3D-Punktwolke in dem Bild?
Ansonsten schaue ich mir gerade die Karte an und stelle fest, dass gar nicht nur die jeweils nächsten Nachbarn verbunden sind sondern "willkürlich" die Punkte verbunden sind.
Nach welchem System die Punkte untereinander verbunden sind ist dort nicht wirklich ersichtlich.
Desweiteren sind im Grunde alle Punkte mit allen (über jeweils andere Punkte) verbunden.

Um diesen zu erreichen fällt mir spontan folgender Algorithmus ein:

Betrachten wir die Punktwolke als Graph bei dem erstmal alle Punkte untereinander verbunden sind. (also mit einer vollbesetzten Adjazenmatrix).

Dann picken wir einen zufälligen Punkt als "Ziel" heraus.

Für alle anderen Punkte wird der kürzeste Pfad zu diesem Punkt ermittelt - alle anderen Verbindungen werden gelöscht.

Jeder Punkt im Graphen ist dann nur mit jeweils einem verbunden aber in der Gesamtheit ohne Lücke.

Nein ist keine 3D-Punktwolke.

Einige willkürliche Verbindungen gibt es aber für meine Zwecke brauch ich diese nicht.

Meinst du also Pfandfindungsalgorithmus (z.b. A*) wobei die Entfernung der Punkte zueinander die Gewichtung ist?

**AspirinJunkie**

Zitat von chip

Meinst du also Pfandfindungsalgorithmus (z.b. A*) wobei die Entfernung der Punkte zueinander die Gewichtung ist?

Ja. Ich bin zwar nicht so der Graphenexperte aber spontan hätte ich für diesen Anwendungsfall Dijkstra dem A* vorgezogen.

Wobei: Wenn ich noch länger drüber nachdenke wäre das Ergebnis ja ein minimaler Spannbaum.
Da hab ich noch den Algorithmus von Kruskal im Kopf. Sicherlich wird es da aber mittlerweile effektivere Algorithmen geben.
Ja vermutlich kommst du besser, wenn du einen minimalen Spannbaum ermittelst.

**chip**

Ja du hast recht Dijkstra ist hier wohl besser. Hatte mal in PHP genutzt mal schauen ob ich das Script noch finde. Hättest du vielleicht noch eine Idee wie ich bei dem Randomerzeugen der Punkte es anstellen könnte, dass es vom Zentrum ausgehend immer weniger Punkte werden?

Also als Beispiel ich habe Koordinatensysten 3000x3000 auf dem 9000 Punkte entstehen sollen und zwar vom Zentrum also Punkt 1500x1500 nach außen gehend immer weniger.

**AspirinJunkie**

Zitat von chip

Hättest du vielleicht noch eine Idee wie ich bei dem Randomerzeugen der Punkte es anstellen könnte, dass es vom Zentrum ausgehend immer weniger Punkte werden?

Klar - statt einer Gleichverteilung eine andere Zufallsverteilung nehmen. Z.B. eine Normalverteilung:

AutoIt

Global $a_Zentrum[] = [1500.0, 1500.0]
Global $a_Points[9000][2]
Global $f_StdDev = 500.0 ; Standardabweichung für Normalverteilung


Global $a_Rndom


; Punktwolke erstellen
For $i = 0 To UBound($a_Points) - 1
	$a_Rndom = Random_Normal(.0, $f_StdDev)
	$a_Points[$i][0] = $a_Zentrum[0] + $a_Rndom[0]
	$a_Points[$i][1] = $a_Zentrum[1] + $a_Rndom[1]
Next


; Punkte ausgeben:
For $i = 0 To UBound($a_Points) - 1
	ConsoleWrite(StringFormat("% 4d: %-7.2f, %-7.2f\n", $i+1, $a_Points[$i][0], $a_Points[$i][1]))
Next




; #FUNCTION# ======================================================================================
; Name ..........: Random_Normal()
; Description ...: Gibt ein Array mit 2 normalverteilten Zufallsvariablen zurück
; Syntax ........: Random_Normal(Const $f_Mittelwert, Const $f_Standardabweichung)
; Parameters ....: Const $f_Mittelwert         - Mittelwert der Normalverteilung
;                  Const $f_Standardabweichung - Standardabweichung der Normalverteilung
; Return values .: Success: Array mit 2 normalverteilten Zufallsvariablen
;                  Failure: Ich mache keine Fehler!
; Author ........: AspirinJunkie
; =================================================================================================
Func Random_Normal(Const $f_Mittelwert, Const $f_Standardabweichung)
	Local $I, $f_H1, $f_H2, $f_QuadSum, $f_I


	Do
		$f_H1 = (2* Random(0, 1) - 1)
		$f_H2 = (2* Random(0, 1) - 1)
		$f_QuadSum = ($f_H1*$f_H1 + $f_H2 * $f_H2)
	Until $f_QuadSum <= 1


	$f_I = Sqrt((-2*log($f_QuadSum )) / $f_QuadSum )


	Local $aZ[] = [$f_Standardabweichung * $f_H1 * $f_I + $f_Mittelwert, $f_Standardabweichung * $f_H2 * $f_I + $f_Mittelwert]
	Return $aZ
EndFunc

Alles anzeigen

**chip**

Geil, genau das hab ich gemeint. Du bist klasse!