Kartesisches Koordinatensystem mit Punkten bestücken

[WilliTheSmith]

Hallo,
ich suche aktuell nach einer Möglichkeit, ein kartesisches Koordinatensystem mit Punkten zu bestücken. Vorerst nur im 2-dimensionalen, später auch im 3-dimensionalen Raum. Die Punkte sollten zu den umliegenden Punkten einen Abstand von (z.B.) 10 - 100 Einheiten haben (Abstand ist also variabel) und sich um den Mittelpunkt 0|0 in alle Richtungen ausbreiten.

Ich bin schon den ganzen Morgen am grübeln und suchen, wie ich das am besten bewerkstellen könnte. Wenn da jemand eine Idee hat, würde ich mich freuen, wenn er mir diese mitteilt.

Gruß

 

[geislpxs]

Zufällig oder über Parameter variabel? Suchst du nach nem Programm, in dem das möglich ist, oder suchst du eine Lösung?
(matlab, fortran, oktave, excel,... sollten das, was ich denke was du beschreibst, hinbekommen )

 

[wertewandel]

ich würde zufällig punkte suchen lassen und dann prüfen ob sie in der nähe mindestens eines anderen punktes sind.

abstand zweier punkte: delta x²+delta y²=z² (der gute pythagoras funktioniert richtungsunabhängig aber leider auch über die ränder hinaus, aufpassen, deshalb delta x)
z sei zwischen 10 und 100.

einfach random (am besten in festen stufen damit sie nicht bis unendlich fliegen wenn dein maximaler punkt nur 500einheiten vom zentrum weg ist)
also am anfang: max-random=0+100 (0 wegen maximalem abstand eines punktes vom zentrum, 100 um auch nen punkt maximal zu ihm zuzulassen)
meinetwegen bei 60, also ist der oberwert der maximalen entfernung für den nächsten random 60+100.
landet der zweite bei 40 -> bleibt es bei 60+100 usw.

ist zwar kein gut skalierender code wenn du millionen von punkten hast, aber dafür landen punkte wirklich zufällig auf dem feld und damit auch wieder nah am ausgangspunkt. zudem kann man die prüfbedingungen leicht ändern und etwa ne minimale entfernung einfügen ohne viel nachzudenken oder den code umzustellen.

 

[Turas]

Was heisst um den Mittelpunkt in alle Richtungen ausbreiten? Ist der Raum beschränkt, auf den die Punkte verteilt werden sollen? Soll ein beschränkter Raum komplett mit solchen Punkten gefüllt werden oder reicht eine bestimmte Anzahl?

 

[WilliTheSmith]

@geislpxs: Es soll zufällig verteilt sein, mit der Einschränkung, dass die nächsten Nachbarn zwischen 10 und 100 Einheiten entfernt liegen. Der Grund hierfür ist, dass die Dichte nicht zu hoch oder niedrig wird.

Und ich suche nach einer Lösung für mein Problem, damit ich dieses in Programmcode umsetzen kann, sprich, einen Algorithmus.

@wertewandel: Werd mir das nochmal genauer ansehen, sieht auf dem ersten Blick schon mal nicht schlecht aus. Millionen von Punkte werden es zwar nicht, jedoch schon ein Paar 1000.

@Turas: Mittelpunkt heißt einfach das ich im Punkt 0|0 beginne und von dort an Punkte verteile. Der Raum ist nicht wirklich beschränkt, es sollen beispielsweise nur 1000 Punkte kreisrund verteilt werden mit den Abstand zu einem umliegenden Punkt von 10-100.

 

[gigges91]

Und womit möchtest du programmieren? Darf ich mal fragen, wofür du das ganze brauchst?

 

[geislpxs]

Der Abstand der Punkte soll zueinander variabel sein, während sich der Winkel auf 0/0 bezieht, wenn ich das richtig verstanden habe@wertewandel.
Wie sieht es mit dem Abstand zum Ursprung aus?
Als einfachste Lösung mit konstantem Abstand zum Ursprung sehe ich Kreisbahnen und Kugeloberflächen. Der Abstand der Punkte zueinander kann ja trotzdem dynamisch sein

edit: gerade die Antwort gesehen. Verteilung zufällig oder gleichmäßig. Frage nur, weil mein beim Randomwalk nicht wirklich wieder im Ausgangspunkt landet

 

[wertewandel]

Und ich suche nach einer Lösung für mein Problem, damit ich dieses in Programmcode umsetzen kann, sprich, einen Algorithmus.

und meine idee verstehst du nicht oder was gibts daran auszusetzen?
funktioniert sehr gut, wenn man ordentlich mit variablen arbeitet.

 

[WilliTheSmith]

@wertewandel: Ihr wart etwas schnell Gab nen edit

@gigges91: Die Programmiersprache ist eigentlich nicht von Relevanz, da man die meisten Algorithmen in den meisten Programmiersprachen ohne Probleme umsetzen kann. Aber wenn du schon fragst: Es wird wahrscheinlich C++, steht aber noch nicht fest.

@geislpxs: Mehr zufällig als gleichmäßig. Wobei ich nicht wirklich einen Unterschied erkenne, da bei zufälligen 1000 Punkten ja auch wieder eine Gleichmäßigkeit erkennbar sein sollte.

 

[geislpxs]

Würde ein Gitter mit einer Gitterkonstante von 10, bei dem bei jedem Punkt gewürfelt wird, ob er erscheint oder nicht ( es sei denn, der Abstand übersteigt 10 Gitterkonstanten zum Nächsten) den Anforderungen genügen?

 

[WilliTheSmith]

@geislpxs: Daran habe ich auch schon gedacht und ich bin dem auch nicht gänzlich abgeneigt. Würde eine andere Methode jedoch bevorzugen.

 

[wertewandel]

@wertewandel: Werd mir das nochmal genauer ansehen, sieht auf dem ersten Blick schon mal nicht schlecht aus. Millionen von Punkte werden es zwar nicht, jedoch schon ein Paar 1000.

na und, die dümmste lösung ist jeden punkt mit allen alten zu vergleichen. also auch 10000punkte sind kein problem auf modernen rechnern weil es jeweils nur eine gleichung ist die man lößt.
ansonsten müsste man anfangen cluster/sektoren sich auszudenken. neuer punkt wird cluster zugeordnet, es wird geprüft ob der randbereich die 4 sektorengrenzen überschreitet.
nein-> nur der sekor wird abgeklappert mit den punkten darin
ja-> der angrenzende sektor wird auch geprüft.


ist ne schöne lösung und ich hab keinen halben tag gegrübelt. wo ist meine belohnung?
zumal man den pythagoras auch in 3d benutzen kann.

 

[slaves]

hm. wieso kein Random Walk ?

 

[geislpxs]

Weil man mit RandomWalk nicht gleichmäßig, aber zufällig verteilt.... Hab damit im Studium auch rumspielen müssen.
Königsdisziplin wäre wohl Schema d=B*m (daten= B-matrix*Modell). Aber da fehlen mir momentan Skills
(Und dann war da noch was mit Norm, Fehlermatrix, Resolutionsmatrix,... und dann kann man bestimmt herrliche Punktwolken malen)

Den Winkel im Gitter auch zufällig machen? (Edit: in einem gewissen Winkelbereich, sonst ziehst du Kreise. Auch mit Random)
edit: Damit wären wir wir wieder beim Pythagoras. Nur mit mehr Punkten

 

[slaves]

@geislpxs: Es soll zufällig verteilt sein, mit der Einschränkung, dass die nächsten Nachbarn zwischen 10 und 100 Einheiten entfernt liegen. Der Grund hierfür ist, dass die Dichte nicht zu hoch oder niedrig wird.

Es soll doch zufällig verteilt sein?!

edit:

Und den Abstand kann man über die Schrittweite anpassen.

 

[wertewandel]

Es soll doch zufällig verteilt sein?!

ja, aber über die gesamte fläche und nicht nur zum letzten punkt.

 

[geislpxs]

Ah, Denkfehler. Winkel sind doof, man muss nur das Gitter feiner machen. Das mit dem Mindestabstand von 10 lässt sich ja trotzdem einbauen (Faktor abhängig von der Rasterung). Wenn man das fein genug macht, kann jeder Punkt zufällig erreicht werden.
Über die Parameter hast du dann Einfluss auf die Dichte und Wahrscheinlichkeiten

 

[benneq]

Also spontan fallen mir 2 Lösungsansätze für den 2-dim Raum ein:

1. Quadrat:
d.h. die Punkte werden nicht auf einem Kreis, sondern einem Quadrat verteilt. Man nimmt also (0/0) als Mittelpunkt und dann ein Koordinatensystem von -1000 bis +1000 auf x- und y-Achse.
Zur zufälligen Verteilung der Punkte nimmt man nun also 2 Zufallszahlen zwischen -1000 und +1000: x und y. Und vergleicht den Punkt (x/y) dann mit allen anderen vorhandenen Punkten. Und wenn der Abstand zwischen 10 und 100 ist, wird er der Liste der Punkte hinzugefügt.


2 Kreis:
d.h. die Punkte werden auf einem Kreis um den Ursprung (0/0) verteilt. Man legt also vorher den Radius fest (z.B. 1000).
Das ganze läuft dann so ab: Wähle zufällige Zahl zwischen 0 und 360 (oder statt Grad in Radiant). Diese Zahl bestimmt den Winkel um den Mittelpunkt (0/0). Und als zweite Zufallszahl wählt man den Abstand zum Mittelpunkt (d.h. zwischen 0 und dem oben festgelegten Radius). Jetzt lässt sich einfach der Punkt im Koordinatensystem berechnen - evtl. die Werte Runden, wenn man nur Ganzzahlen möchte.
Und dann wie oben: Mit allen anderen Punkten vergleichen, und wenn Abstand überall zwischen 10 und 100 liegt: Punkt der Liste hinzufügen.


Für den 3-dim Raum ist das Ganze natürlich sehr ähnlich. Für den Ansatz mit dem Quadrat, wählt man dann natürlich einen Würfel mit und 3 zufällig Koordinaten und statt des Kreises einfach eine Kugel

 

[WilliTheSmith]

@benneque: Du wirst es nicht glauben, aber ich habe gerade ein Testprogramm fertig gestellt, das genau nach deiner 2. Möglichkeit arbeitet, bis ins kleinste Detail Das einzige Problem ist halt, das die Punkte, die näher am Mittelpunkt sind, eine höhere Dichte aufweisen als die, die weiter weg sind. Aber das stört mich nicht weiter, ich finds so sogar besser!

Kleine Ergänzung aber noch: Alle Punkte müssen weiter als 10 Einheiten entfernt sein, und nicht zwischen 10-100 liegen. Ansonsten könnte ich ja gerade einmal vlt 10 Punkte eintragen. Und wenn man im voraus festlegt, wie viele Punkte eingetragen werden sollen(exklusive der Verworfenen) kann man auch die Dichte bestimmen.

An alle anderen: Danke für die zahlreichen Postings!

 

[Krik]

Nach so etwas ähnlichem habe ich vor einiger Zeit hier auch gefragt: https://www.computerbase.de/forum/t...nachbarschaft-nach-bestimmten-regeln.1155366/

Eine Lösung ist es, Voronoi zu verwenden. Das geht nicht nur im 2D-Raum sondern auch im 3D-Raum.

http://www.youtube.com/watch?v=djhO8IjbhoA

http://www.youtube.com/watch?v=z6oxjdrB6ok


Also kurz gefasst:
Mit einer beliebigen Random-Funktion (zB Perlin Noise, Simplex Noise) die Punkte verteilen. Diese dann in ein Voronoi-Diagramm einfügen und zB so lange mit Lloyds Algorithmus drüber gehen, bis die Punktwolke deinen Anforderungen entspricht.