Punkte gleichmaessig verteilen

[heinz]

Hallo Zusammen,

ich bin mal wieder auf der Suche nach einer Methode um ein Problem zu loesen.

Aufgabenstellung:
Ich moechte eine bestimmte Menge von, sagen wir z.B. 100, Punkten auf einer vorgegebenen Flaeche (2D) zufaellig zu verteilen.

Die Bedingung dabei ist, dass ein vorbestimmter Mindestabstand eingehalten werden soll.
Das heisst, jeder Punkt muss mindestens einen Abstand von X zu allen anderen haben.

Ich habe mir bereits eine Loesung "gebastelt", die immer wieder die Liste der Positionen der Punkte durchgeht und Punkte die sich zu nah an einem
anderen Punkt befinden in die entgegengesetzte Richtung bewegt. So lange bis sich keiner mehr bewegt.

Allerdings weiss ich mittlerweile das es oft fuer solche Aufgaben eine "einfachere" mathematische Loesung gibt.
Fuer dieses Aufgabe auch?

Ich waere fuer alle Vorschlaege oder Anregungen dankbar.

Gruss, heinz

[Meillo]

Ich habe mir bereits eine Loesung "gebastelt", die immer wieder die Liste der Positionen der Punkte durchgeht und Punkte die sich zu nah an einem
anderen Punkt befinden in die entgegengesetzte Richtung bewegt. So lange bis sich keiner mehr bewegt.

Einen fertigen Algorithmus fuer das Problem kann ich dir nicht bieten. Aber vielleicht eine Optimierung fuer deinen Ansatz:

Mir scheint, du erzeugst 100 Punkte und faengst dann an die zu ``ruetteln'', bis das Ergebnis der Abstandsbedingung entspricht. Wenn die Flaeche eng gepackt ist, wird so ein Vorgang vermutlich noetig sein. Falls die Flaeche aber spaerlich gepackt ist, koenntest du auch schon beim Setzen der Punkte gleich die Abstaende fuer den zu setzenden Punkt pruefen und nur diesen einen reinruetteln oder zufaellig neu platzieren, bis die Abstaende passen. Dann must du am Ende ggf. gar nicht mehr ruetteln und haettest insgesamt wohl weniger Abstandsvergleiche. Nur falls es bei dicht gepackten Flaechen Faelle geben kann, bei denen die bisher gesetzten Punkte den Platz unguenstig blockieren, dann muesste man auch in dem Fall am Ende nochmal alles ruetteln. (Ich hab nicht durchdacht, ob es so Faelle geben kann.)

Jedenfalls finde ich die Problemstellung interessant. Halte uns bitte auf dem Laufenden.

[Tintom]

Verständnisfrage: Der Threadtitel sagt "gleichmäßig verteilen" aber in einem Beitrag schreibst du, dass ein Mindestabstand nicht unterschritten werden soll. Bedeutet das, dass der Abstand auch variieren kann/darf?

[Meillo]

Verständnisfrage: Der Threadtitel sagt "gleichmäßig verteilen" aber in einem Beitrag schreibst du, dass ein Mindestabstand nicht unterschritten werden soll. Bedeutet das, dass der Abstand auch variieren kann/darf?

Im Text steht auch, dass sie zufaellig verteilt sein sollen. Daraus schliesse ich, dass es kein regelmaessiges Muster sein soll. Das ``gleichmaessig'' ist wohl nur umgangsprachlich, nicht wissenschaftlich gemeint.

[heinz]

Hallo nochmal,

erstmal, vielen Dank fuer Eure Antworten und dem Interesse an meinem "Problem".

schon beim Setzen der Punkte gleich die Abstaende fuer den zu setzenden Punkt pruefen und nur diesen einen reinruetteln oder zufaellig neu platzieren, bis die Abstaende passen.

Das ist ein guter Vorschlag.
Ich werde wohl mal "hingehen" und den Teil meines Programms extrahieren und in ein neues Programm "umwandeln", um besser
damit experimentieren zu koennen.
Danke fuer den Tipp.

Verständnisfrage: Der Threadtitel sagt "gleichmäßig verteilen" aber in einem Beitrag schreibst du, dass ein Mindestabstand nicht unterschritten werden soll. Bedeutet das, dass der Abstand auch variieren kann/darf?

Meillo Hat das richtig erfasst, es geht darum auf einer 2D-Karte eine Menge von Punkten zu verteilen die
nur als Praemisse haben, einen Mindestabstand nicht zu unterschreiten.
Die gleichmaessigkeit ueber die Flaeche ist dabei nebensaechlich.

Die Ausdehneung der 2D-Karte ist natuerlich begrenzt.
Eine groessere Menge von Punkten benoetigt daher logischerweise auch eine groessere Karte.

Ich denke auch, dass sich automatisch eine Art von Gleichverteilung entwickeln wird, wenn man die Anzahl der Punkte auf
die Kartengroesse abstimmt...


Gruss, heinz

[MSfree]

Ich würde die Zeichenfläche virtuell kacheln, die Kachelgröße würde ich auf das ein- bis zweifache des minimalen Abstand setzen.

Jeder neue Punkt bekommt dann einfach eine Indexnummer und dieser Indexnummer wird in die passende Kachel gespeichert. Mit Hilfe der Nachbarkacheln kann man dann nur die Punkte suchen, für die eine Entfernungsprüfung nötig ist. Alle anderen Punkte, die nicht in einer der acht Nachbarkacheln liegen, sind automatisch weiter als der Minimalabstand entfernt.

Zumindest läßt sich so der Suchaufwand ganz erheblich reduzieren und man muß nicht mehr jeden bereits vorhanden Punkt abklappern und auf seine Distanz prüfen.

[Meillo]

Um hier MSfrees Post aufzugreifen:

Ich bin davon ausgegangen, dass bei jeder Generierung eine zufaellig andere Verteilung rauskommen soll. Falls das, wie du schreibst, nebensaechlich ist, dann kann man sie ja auch einfach schematisch positionieren: Einfach links oben anfangen und dann reihenweise mit Mindestabstaenden positionieren. Oder die Flaeche gleichmaessig in die passende Anzahl von Kacheln teilen und jeweils in deren Mitte einen Punkt setzen. Das so erzeugte Muster ist aber schematisch. Da du bisher bereits so viel Aufwand in deiner Umsetzung betreibst kann ich mir kaum vorstellen, dass so eine schematische Anordnung in Frage kommt.

Vielleicht kannst du zum Setting noch ein bisschen mehr schreiben, damit wir uns das besser vorstellen koennen.

- Wie sehr zufaellig muessen die Punkte verteilt sein?

- Wie sehr gleichmaessig verteilt muessen sie sein?

- Wie sehr schematisch darf die Anordnung sein?

- Wie voll, d.h. dicht gepackt, ist die Flaeche?

Je nachdem wie die Antworten lauten, waere es beispielsweise auch moeglich die Punkte nicht ganz zufaellig zu setzen, sondern eine Kombination aus einer Art Raster fuer die Mindestabstaende und darin Bereichen mit Zufall fuer die tatsaechliche Platzierung zu verwenden. Das waeren Massnahmen, um Verteilungen zu erzeugen, die kein Zurechtruetteln und kein mehrfaches Platzieren von Punkten bis sie passen benoetigen.

Was moeglich ist haengt aber eben davon ab, welche Anforderungen die Umsetzung genuegen muss.

[heinz]

Ich würde die Zeichenfläche virtuell kacheln

Auch ein interessanter Ansatz... Danke.

Um hier MSfrees Post aufzugreifen:

Ich bin davon ausgegangen, dass bei jeder Generierung eine zufaellig andere Verteilung rauskommen soll. Falls das, wie du schreibst, nebensaechlich ist, dann kann man sie ja auch einfach schematisch positionieren:

Du hast das schon richtig verstanden. Bei jeder Generierung eine zufaellig andere Verteilung.

Sorry, ich habe mich wohl nicht richtig ausgedrueckt.
Ich verstand unter "Gleichmaessig" etwas anderes als unter "Zufaellig".

Mein Verstaendnis:
Gleichmaessig=
Alle punkte immer an den gleichen stellen (eine art Raster) mit dem minimalen Abstand zum Naechsten.

Zufaellig=
Alle Punkte irgendwo auf der Karte mit dem minimalen Abstand zum Naechsten.

(Deshalb mag ich persoenlich auch die schriftliche Kommunikation nicht so sehr, zu viele Missverstaendnisse...
Ich priorisiere eher die Kommunikation von Mensch zu Mensch. Entschuldigt bitte meine schriftlichen Defizite...)

Nochmaliger Versuch: (Danke fuer die Stichpunkte...)

- Wie sehr zufaellig muessen die Punkte verteilt sein?

Bei jedem neuen Aufruf der Funktion soll eine neue "einmalige" Verteilung der Punkte herauskommen.

- Wie sehr gleichmaessig verteilt muessen sie sein?

Das ist nebensaechlich.
Wichtig ist der Mindestabstand und das die Punkte auf die Karte passen.
(Gegebenenfalls wird die Karte leicht vergroessert oder die Anzahl der Punkte leicht verringert...
siehe >Wie voll, d.h. dicht gepackt, ist die Flaeche?<)

- Wie sehr schematisch darf die Anordnung sein?

Das ist ebenfalls nicht so wichtig.
Wichtig ist, das jedesmal eine andere Anordnung heraus kommt.

- Wie voll, d.h. dicht gepackt, ist die Flaeche?

Das ist unterschiedlich.
Es gibt eine bestimmte Menge an Punkten und eine bestimmte groesse der Karte.
Da es moeglich ist, dass die Anzahl der Punkte mit einem bestimmten Abstand nicht auf die Karte passt
dachte ich mir, entweder die Karte leicht zu vergroessern oder den Abstand leich zu verringern.
Aber das ist nur ein Ausnahmezustand.
Wichtig ist, die Punkte auf der Karte zu verteilen, ohne den minderstabstand zu unterschreiten.

Ich hoffe, dass es jetzt etwas klarer wurde...

Danke fuer Eure Geduld.
Gruss, heinz

[Meillo]

Wenn eine schematische Anordnung egal ist, dann mach es vielleicht so:

Teile die Flaeche in soviele gleichgrosse Rechtecke/Kacheln auf wie du Punkte unterbringen musst. Dann setze in jede Kachel einen Rahmen von der Breite des halben Mindestabstandes. In die verbleibende Flaeche setzt du dann zufaellig einen Punkt.

Dieser Ansatz braucht nur einen Durchgang. Er hat ein Zufallselement und verteilt die Punkte ungefaehr gleichmaessig auf die ganze Flaeche. Der Nachteil ist, dass das erzeugte Muster schematisch aussehen wird (wenn die Flaeche eng gepackt ist) und es ein ``Abstandsgitter'' ohne Punkte gibt. Dagegen kann man schon noch ein bisschen optimieren, aber es wird nicht so wild wie bei deinem geruettelten Ansatz. Dafuer ist die Generierung viel weniger Aufwand und kommt immer definiert zu einem Ergebnis. Da kommt's halt drauf an, welche Aspekte dir wie wichtig sind.

[eggy]

Code: Alles auswählen

 
#!/usr/bin/python3

# aufruf mit  "./script.py > bild.pbm" 
# ansehen mit "display bild.pbm"

from random import randrange

from math import ceil

ANZAHLPUNKTE = 200
RESERVE = ANZAHLPUNKTE / 10  # man braucht nen paar mehr, damit die flaeche gleichmaessig zufaellig gefüllt bleibt, das koennte man anders besser machen, aber so ist es einfacher
WIDTH = 1000
HEIGHT = 300
ABSTANDMIN = 10
WAHRSCHEINLICHEKIT = 10 # wie wahrscheinlich ist es dass ein pixel erscheint


punkte = 0 
liste = []

# erzeuge verteilung als liste
while punkte < ANZAHLPUNKTE + RESERVE:
    pixel = 0
    if randrange(WAHRSCHEINLICHEKIT) == 1 :
            pixel = 1
            punkte +=1 
    liste.append (pixel)

#erstelle bild:
#berechne noetigen abstand
benoetigtebildpunkte = WIDTH * HEIGHT
faktor = ceil(benoetigtebildpunkte / len(liste)) 
if faktor < ABSTANDMIN:
    faktor = ABSTANDMIN

zeile = 0
anzahlzeilen = 1
stop = False

#output pbm header:

print ("P1") # magic number for pbm
print ("#bild.pbm") # comment
print (str (WIDTH) + " " + str( HEIGHT))

for punkt in liste:
    if stop:
        break
    zeile +=1
    print (punkt, end = "")
    n = 0
    while n < faktor:
        print (0, end = "")
        n +=1
    if zeile == WIDTH :
        while n < faktor:
            print()
            anzahlzeilen +=1
        zeile = 0
    if anzahlzeilen == HEIGHT:
        stop = True

ist nicht perfekt, nen paar Sachen könnte man besser machen, wie z.B. am Ende noch ein gewichtetes zufäiliges hoch- und runterschieben aller Spalten, damit das Leerzeilengitter kaschiert wird. Für seriöse Anwendungen wie Crypto taugt der Code definitiv nicht, für ne Sternenkarte für nen Spiel (das wars doch, oder?) sollte es aber ausreichen.

pbm ist das einfachste Bildformat, das ich kenne, winziger header sonst nur ja/nein http://netpbm.sourceforge.net/doc/pbm.html
mit convert kannst Du daraus jedes beliebige andere Format erzeugen, oder selbst nen richtigen Export einbauen

[eggy]

Falls der gewünschte Wert von Punkte genau stimmen muss: nicht gleich printen sondern erstmal ein Array erstellen und dann durchzählen wieviele Punkte ausgegeben worden wären und an jeweils zufälliger Stelle sooft 1 zu 0 ändern bis es stimmt

[detix]

das erinnert mich irgendwie an Voronoi, allerdings umgekehrt...
https://de.wikipedia.org/wiki/Voronoi-Diagramm

[schwedenmann]

Hallo

@Heinz

Meillo Hat das richtig erfasst, es geht darum auf einer 2D-Karte eine Menge von Punkten zu verteilen die
nur als Praemisse haben, einen Mindestabstand nicht zu unterschreiten.
Die gleichmaessigkeit ueber die Flaeche ist dabei nebensaechlich.

bist du dir mit der letzetn Ausge sicher ?

ich würde annehmen, die Aufgabe beinhaltet max. Anzahl von Punkten in der Fläche bei einem Mindesabstand, sagen X=1

Ansonsten gibst du 10 Punkte an, die soltten deine obigen Angaben locker erfüllen, aber das ist math. betrachtet kein Problemchen

Afaik gibt es ein ähnliches math. Problem (max. Anzhal von Farbpunkten) mit farbigen Punkten die auf einer Fkläche verteilt werden sollen, bei einem Mindestabstand X = 1 oder x= 2, wobei 2 nebeneinanderliegende punkte nicht dieselbe Farbe habne dürfen.

mfg
schwedenmann

[reox]

Du kannst das auch als Graphenproblem auffassen und dann die Force-Atlas Methode verwenden (glaube die heißt auch anders): https://github.com/gephi/gephi/wiki/Force-Atlas-2
Jede Kante ist dann eine Feder. Die Federn versuchen in Ruhelage zu gelangen, also der gesuchten mittleren Länge.

Ich würde es folgendermaßen machen: Du setzt zufällig, zB Gleichverteilt, n Punkte auf der Ebene. Dann erstellst du mittels Delaunay die Kanten. Die Verschiebung u jeder Feder ist die euklidische Länge der Kante zwischen zwei Punkten minus der Ruhelage x. Die Ruhelänge x gibst du vor.
Dh du kannst schreiben u = |p2-p1| - x (wenn p2 und p1 die Ortsvektoren der Punkte 2 und 1 sind, |x| ist die Länge des Vektors). Die Kraft an jeder Feder ist jetzt F=k*u, wobei du k einfach gleich 1 setzen kannst. dH die Kraft die jede Feder ausübt ist proportional zur Verschiebung, also zur Abweichung der Ruhelänge.
Die wirklich spannende Aufgabe ist es jetzt, iterativ die Knoten so zu verschieben, so dass die Summe der Kräfte im System 0 wird (Gleichgewichtslage).
Wie gesagt, da würde ich mal die Algorithmen zur Graphenerzeugung konsultieren. den Rand der Fläche musst du jedenfalls miteinbeziehen und dort ebenfalls Knoten positionieren. Was sonst passiert ist, dass alle Knoten an den Rand geschoben werden.
Ich vermute, dass du das Problem mit einem Optimierer lösen kannst. Stelle die Knotenverschiebungen als Vektor dar, zb [x1, x2, x3, ..., xn, y1, y2, y3,..., yn, z1, z2, z3, ..., zn]. Der Vektor hat also d*n Zeilen, wobei d die Dimension deiner Ebene ist (üblicherweise 2 oder 3). Wenn du tatsächlich immer in einer Ebene arbeitest, ist es vermutlich empfehlenswert das Problem immer in den R² zu legen - damit minimierst du effektiv die Anzahl der Parameter.
Jetzt berechnest du die neue Knotenverschiebung über den optimierer und als Metrik verwendest du die Summe der Federnkräfte.

Ich glaub ich versuch das mal zu implementieren Schauen wir mal was rauskommt.

edit: moment: Ohne Beschränkung wird das immer auf eine Kugelform hinauslaufen. Ok, man darf vermutlich nicht Delaunay verwenden sondern muss nur Knoten im Umkreis nehmen oder so... Die nächste Frage ist ob bei einer Ebene die groß genug ist, dies nicht immer genau zu einem Rechteckmuster oder einer Kugelpackung wird.

[heinz]

Erstmal, vielen Dank fuer Eure Antworten.

Habe mich jetzt mal soweit durchgearbeitet und ein wenig herumprobiert.

Teile die Flaeche in soviele gleichgrosse Rechtecke/Kacheln auf wie du Punkte unterbringen musst...

Der Vorschlag von MSfree scheint da auch sehr aehnlich zu sein und ich hab das mal umgesetzt.
Du hast recht, die Geschwindigkeit ist Top aber das Ergebnis ist dann doch etwas zu gleichfoermig.
Dieses Bild kam dabei heraus:

192 Punkte, Mindestabstand 40 px

#!/usr/bin/python3
# aufruf mit "./script.py > bild.pbm"

Vielen Dank fuer den Aufwand den Du auf Dich genommen hast.
Habe die Werte:

Code: Alles auswählen

WIDTH = 1024
HEIGHT = 768
ABSTANDMIN = 50

Angepasst und das Bild Invertiert. Ergebnis:

Mir scheint das der Abstand oft zu klein ist.
Ich habe die Funktionsweise noch nicht durchschaut aber ich werde mal etwas damit "herumspielen".

das erinnert mich irgendwie an Voronoi, allerdings umgekehrt...

Ich bin mir nicht sicher, ob ich verstehe wie Du das meinst...

bist du dir mit der letzetn Ausge sicher ?
ich würde annehmen, die Aufgabe beinhaltet max. Anzahl von Punkten in der Fläche bei einem Mindesabstand, sagen X=1
Ansonsten gibst du 10 Punkte an, die soltten deine obigen Angaben locker erfüllen, aber das ist math. betrachtet kein Problemchen

Sorry, ich bin im erklaeren nicht so gut.
Es ging mir nicht darum ein mathematisches Problem zu loesen sondern nur eine einfachere Methode fuer diese Aufgabe zu finden.
Wenn ich Dich richtig verstehe, gehst Du davon aus die Aufgabe sei:
Bestimme die max. Anzahl von Punkten die, mit einem Mindestabstand von X, auf eine definierte Flaeche passen.
Doch darum ging es mir eigentlich nicht.
Wie eggy schon richtig vermutet hat, geht es mir um die Erstellung einer zufaelligen Sternenkarte fuer ein Spiel.
Und ja, bei 10 Punkten hatte ich auch noch keine Probleme...

Du kannst das auch als Graphenproblem auffassen und dann die Force-Atlas Methode verwenden...

Ich habe Deine Antwort jetzt 3 mal gelesen und das ist mir eindeutig zu hoch...
Trotzdem vielen Dank fuer die Muehe.


Zuletzt habe ich auch noch an der "Ruettel-Methode" etwas "rumgeschraubt" und das kam dabei heraus:

Auch hier 200 Punkte
Mindestabstand = 50 px
und ein Min.Randabstand von 20 px

Werde noch etwas weiter herumexperimentieren...

Gruss, heinz

[Meillo]

Wie eggy schon richtig vermutet hat, geht es mir um die Erstellung einer zufaelligen Sternenkarte fuer ein Spiel.

Das Szenario zu kennen hilft weiter, weil somit klar ist, dass jede Art von Rasterartigkeit unpassend ist.

Meine Ueberlegungen machen eher wenig Sinn. Ich hatte mehr ein Szenario in einem Fertigungsprozess im Sinn, wo Stempel auf Flaechen druecken oder so.

Das Ergebnis von eggys Script finde ich bisher am besten:


Warum aber ueberhaupt der Mindestabstand? Am realen Himmel gibt es ja auch Cluster und freie Flaechen. Reiner Zufall sollte doch ganz gut passen. (Dann noch die Sterne unterschiedlich gross machen, die Groessen aber nicht gleichverteilt, sondern mit wenigen Grossen und vielen Kleinen. Und mit Farbtoenen ins Geldbliche, Roetliche und Blaeulich-Weisse.)

Da du ein universelles Problemszenario hast, koennte ich mir auch vorstellen, dass es dafuer bereits fertige Algorithmen gibt, die realitaetsnahe Sternenhimmel generieren koennen. Vielleicht suchst du mal nach ``generate night sky'' oder etwas in der Art.

[MSfree]

Der Vorschlag von MSfree scheint da auch sehr aehnlich zu sein und ich hab das mal umgesetzt.
Du hast recht, die Geschwindigkeit ist Top aber das Ergebnis ist dann doch etwas zu gleichfoermig.

So hatte ich das aber nicht gemeint.

Meine Idee war, die Koordinaten natürlich völlig zufällig zu erzeugen. Die Kachelung ist nur dazu gedacht, den Suchraum einzuschränken.

Bei n Punkten mußt du nämlich n*(n-1)/2 Vergleiche durchführen, weil du immer den neuen Punkt mit allen bereits vorhandenen Punkten vergleichen mußt.

Sortierst du die zufällig erzeugten Puntke aber in eine Kachelstruktur ein, dann mußt du den neuen Punkt nur mit den Punkten der betroffenen und den Punkten aus den Nachbarkacheln vergleichen. Dadurch reduziert sich die Anzahl der nötigen Vergleiche erheblich.

Es dürfen also durchaus mehrere Punkte in einer Kachel sein und es darf auch leere Kacheln geben.

[heinz]

Das Szenario zu kennen hilft weiter, weil somit klar ist, dass jede Art von Rasterartigkeit unpassend ist.

Bei solchen Aufgaben vermeide ich manchmal schon zu Beginn ganz konkret zu werden, da so auch oft Vorschlaege
kommen die einem neue Denkanstoesse geben oder auch fuer andere Probleme nuetzlich sind.
Sorry dafuer...
Ausserdem gibt es durchaus auch 4X Weltraumspiele die so eine gerasterte Karte anbieten.
(Wahlmoeglichkeit der Galaxieform: Spirale, Ellyptisch, Gerastert, ...)

Das Ergebnis von eggys Script finde ich bisher am besten:

Ja, das sieht gut aus. Alledings stimmt da etwas mit den Abstaenden noch nicht (zu klein).
Trotz ABSTANDMIN = 50
Werde nachher nochmal versuchen zu verstehen wie/was eggy da gemacht hat...

Warum aber ueberhaupt der Mindestabstand? Am realen Himmel gibt es ja auch Cluster und freie Flaechen. Reiner Zufall sollte doch ganz gut passen.

Dafuer gibt es mehrere Gruende.

1. Ueberlappende Systeme lassen sich nicht richtig mit der Maus anklicken.
(Ein grosser Stern ueberdeckt einen kleinen...)

2. Jedes System hat auch einen Namen der nicht mit anderen Namen oder Systemen ueberlappen sollte.

3. Bei Zufaelliger positionierung koennen Cluster entstehen die einen grossen Vorteil gegenueber anderen Spielern bedeuten.
Stell Dir vor ein Spieler hat zu beginn 5 oder mehr Systeme die er mit seinen Raumschiffen erreichen kann.
Ein anderer vlt. nur 1 System oder gar keines...

Es soll halt ein Spiel werden und kein Abbild der Realitaet...

(Dann noch die Sterne unterschiedlich gross machen, die Groessen aber nicht gleichverteilt, sondern mit wenigen Grossen und vielen Kleinen. Und mit Farbtoenen ins Geldbliche, Roetliche und Blaeulich-Weisse.)

Das kommt auf jeden Fall. Klasse O, B, A, F, G, K und M Sterne, Mehrfachsysteme, Neutronensterne, schwarze Loecher, ...
Das mit den Punkten ist nur zu Testzwecken. Es ging mir nur um die eigentliche Methode...
(Einzelne Pixel sind ja auch sehr schwer mit der Maus zu treffen... )

Da du ein universelles Problemszenario hast, koennte ich mir auch vorstellen, dass es dafuer bereits fertige Algorithmen gibt, die realitaetsnahe Sternenhimmel generieren koennen. Vielleicht suchst du mal nach ``generate night sky'' oder etwas in der Art.

Die gibt es sicher.
Ich konnte jetzt auf die Schnelle allerdings nur beispiele finden die den realen Sternnenhimmel darstellen.
Ich werde aber noch ein wenig weitersuchen.
Ein guter Tipp, danke dafuer...

So hatte ich das aber nicht gemeint.

Oh, Sorry, da habe ich Deinen Vorschlag wohl gruendlich missverstanden.
Du meintest eine Optimierung der Laufzeit, um eine solche Flaeche zu erstellen.
Darueber hatte ich mir noch gar keine grossen Gedanken gemacht...
Ich haette wohl doch eher darauf hinweisen sollen dass es sich dabei um ein Spiel handelt und die Methode
immer nur einmal zu Beginn (Start des Spiels) benoetigt wird.
Vielen Dank fuer Deine Anregungen in diese Richtung.

Gruss, heinz

[Meillo]

Das Szenario zu kennen hilft weiter, weil somit klar ist, dass jede Art von Rasterartigkeit unpassend ist.

Bei solchen Aufgaben vermeide ich manchmal schon zu Beginn ganz konkret zu werden, da so auch oft Vorschlaege
kommen die einem neue Denkanstoesse geben oder auch fuer andere Probleme nuetzlich sind.
Sorry dafuer...

Du musst dich nicht entschuldigen. Dein Gedanke hinter dem Vorgehen finde ich gut nachvollziehbar. Er hat einiges fuer sich.

Ich finde den Thread im Uebrigen spitze.

Warum aber ueberhaupt der Mindestabstand? Am realen Himmel gibt es ja auch Cluster und freie Flaechen. Reiner Zufall sollte doch ganz gut passen.

Dafuer gibt es mehrere Gruende.

1. Ueberlappende Systeme lassen sich nicht richtig mit der Maus anklicken.
(Ein grosser Stern ueberdeckt einen kleinen...)

2. Jedes System hat auch einen Namen der nicht mit anderen Namen oder Systemen ueberlappen sollte.

3. Bei Zufaelliger positionierung koennen Cluster entstehen die einen grossen Vorteil gegenueber anderen Spielern bedeuten.
Stell Dir vor ein Spieler hat zu beginn 5 oder mehr Systeme die er mit seinen Raumschiffen erreichen kann.
Ein anderer vlt. nur 1 System oder gar keines...

... einfach super, hier mir selber zuzuschauen, wie ich immer wieder Fehlannahmen treffe und sie korrigieren muss. Ich finde das klasse, weil es hier um nichts geht. Wir sind ja zum Vergnuegen hier, und auch du, heinz, willst alternative Ideen zulassen, brainstormen und dazulernen. In einer normalen Job-Situation waere das was hier passiert aber verheerend. Wir wuerden massenhaft Zeit verschwenden und unnoetige Arbeit machen, anstatt direkt zum Ziel kommen, weil wir schlampig kommunizieren. Das soll bitte nicht als Kritik an heinz verstanden werden! Er hat schon geschrieben, dass er schlecht erklaeren kann, aber vor allem ist es gar nicht sein Ziel auf schnellstem, geradlinigem Weg ans Ziel zu kommen. Leider passiert es viel zu oft, dass die Dinge so ablaufen wie hier, *obwohl* man auf schnellstem Weg ans Ziel kommen will. Ich habe solche Faelle einige Male erlebt. Die Gruende koennen verschiedener Art sein, der Ablauf ist aber oft aehnlich. Hier war es nun wieder so: Ich wusste zwar inzwischen, dass es sich um ein Spiel handelt, dachte aber, dass es nur um den Hintergrundsternenhimmel geht, den man aus irgendwelchen Gruenden lieber generieren statt als Bild einlegen will. Nun muss ich feststellen, dass es stattdessen um die Spielkarte selbst geht, was eine voellig andere Sache ist. Die Anforderung der Mindestabstaende macht nun, wo ich die Erklaerungen sehe, voellig Sinn. Das war zuvor aber nicht klar. Das Problem war, dass man von mir Hinweise, Einschaetzungen, Tipps, Vorgehen wollte fuer etwas von dem ich so gut wie gar nicht wusste was es eigentlich ist. Ich bin also wie im Nebel umhergeirrt, habe versucht mir eine Vorstellung vom Szenario zusammenzufantasieren und darauf basierend Vorschlaege zu machen. Mehrmals habe ich feststellen muessen, wie abwegig sie waren ... nur weil ich eben nicht wissen konnte um was es eigentlich geht.

Man koennte das alles frustrierend finden (und heinz koennte sich dafuer entschuldigen wollen). Ich finde es aber voll spannend, weil mich solche Prozesse in der zwischenmenschlichen Kommunikation, gerade auch in IT-Projekten interessieren. Wenn man sich diesen Thread aber in einem Produktivprojekt, bei dem man moeglichst schnell voran kommen will, vorstellt (und heinz' besonderes (und durchaus nachvollziehbares) Vorgehen mal ignoriert) dann bietet er eine tolle Fallstudie, aus der man eine Menge zum Formulieren von Anforderungen lernen kann.

In diesem Sinne, danke heinz, fuer diesen nicht nur inhaltlich sondern auch kommunikationswissenschaftlich interessanten Thread.

Wir muessen das nicht weiter vertiefen, ich wollte euch nur auf diesem Blickwinkel hinweisen.


Inhaltlich bin ich schon ganz gespannt wie's weiter geht!

[heinz]

@Meillo

*lach* Vielen Dank fuer Dein Posting...

Es ist schoen zu sehen dass einem auch in der heutigen Zeit immer wieder Menschen begegnen die einem nicht gleich alle Fehler, Schwaechen oder Ticks die man hat um die Ohren hauen.

Freundschaftliche Gruesse, heinz

[eggy]

Ich mag solche Threads auch sehr gerne, wie die Sachen aus den Scriptingbereich, man hat mal die Möglichkeit sich auf komplett freiwilliger Basis mit interessanten kleinen abgegrenzten Problemen zu beschäftigen, und bekommt, wenn's gut lief, ne handvoll komplett anderer Ansätze frei Haus geliefert.
Ist mal was anderes als sonst:
a) Du hast selbst nen Problem - dann interessiert Dich "die" Lösung. Manchmal, aber selten, auch mehrere, aber in jedem Fall kochst Du in Deiner eigenen Suppe rum und siehst selten über den Tellerrand dabei
b) Das eigentliche Problem ist viel zu komplex um vom eingeschlagenen Weg abzurücken, selten versucht man mal Ansätze abseits des Funktionierenden
c) Du hast das Problem auf der Arbeit, dann ist auch nur sehr selten Zeit fürs Erkunden von alternativen Wegen, Lösung her und ab zum nächsten Problem
d) Du hast die Aufgabe in der Schule/Studium, dann sind die Probleme zwar auch oft abgegrenzt und lösbar, aber oft ist der Zwang dabei, es zum Thema passend zu bearbeiten (Sprache/Kontext vorgeschrieben) und oftmals ist es auch eine leider doch recht langweilige/enge Aufgabenstellung, die nur wenig Freiraum für kreative Lösungen lässt
Da ist sowas hier doch mal was anderes.

Ich hatte nach dem Lesen gestern Abend nur kurz über mögliche Ansätze nachgedacht, hab ne Nacht drüber geschlafen und heute morgen einfach mal runtergeschrieben, was mir im Schlaf durch den Kopf gegangen ist. Dass das nur nen Schnellschuss war, sieht man ja am Code. Mit mehr Zeit würd ichs wahrscheinlich komplett anders machen. Und ja Delauni und vorallem Voronoi sind mir auch als ersten in den Blick gekommen. Der nächste Gedanke ging Richtung Floyd ... und dann dacht ich, dass muss doch auch einfacher gehen und bin morgens bei dem Code da rausgekommen. Mit mehr Zeit wird es nur wieder komplizierter, also lieber nicht weiter drüber nachdenken

@heinz: Die Idee war übrigens erstmal nen kleines Bild mit gewünscht vielen dunklen Pixeln zufällig zu erzeugen, und das dann durch Einfügen von Abständen auf Zielgröße aufzupusten. Wie man sieht, sind im Code noch kleine Fehler (statt dem mehrfachen print() müssten Leerzeilen aus Nullen eingefügt werden, die Variable fürs break ist ziemlich überflüssig, Spaltenverschiebung würde sinnvoll sein, damit man die Gitter nicht sieht, etc).
Auf jedenfall war's ganz interessant, da mal etwas drüber nachzudenken und von daher
@heinz für etwas lockeres Hirnfutter.

[heinz]

@eggy

Auch Dir nochmals Danke fuer Deine kreative Idee und auch fuer die Erwaehnung des Grafikformat .pbm
Das kannte ich ebenfalls noch nicht.
Bisher hatte ich solch einfache Grafiken aus Scripten heraus immer mittels >convert -draw "point X,Y"< erledigt.
.pbm ist da sehr oft um einiges einfacher zu Handhaben und wesentlich schneller.
Wieder was neues gelernt, Danke!

Wie man sieht, sind im Code noch kleine Fehler

Absolut kein Problem. Ich wollte auch eigentlich keine komplette Loesung, die ich dann einfach per Copy/Paste in mein
Programm uebernehmen kann.
Ich bin meist nur auf der Suche nach kreativen Ideen, um eine andere Herangehensweise fuer meine Probleme zu finden.
Und eine solche hast Du auf jeden Fall geliefert!
("Selber Basteln" macht doch am meisten Spass...Und ja, ich stehe gluecklicherweise nicht unter Zeitdruck...)

Und aus dem selben Grund, den Du auch beschrieben hast:

aber in jedem Fall kochst Du in Deiner eigenen Suppe rum und siehst selten über den Tellerrand dabei

suche ich immer mal wieder hier im Forum einen Rat zu meinen aktuellen "Basteleien".
(Und finde ihn auch immer wieder...)

> @heinz für etwas lockeres Hirnfutter.

*grins* Freut Euch schon mal auf meine naechsten Probleme...


Freundschaftliche Gruesse, heinz

[Meillo]

Auch Dir nochmals Danke fuer Deine kreative Idee und auch fuer die Erwaehnung des Grafikformat .pbm
Das kannte ich ebenfalls noch nicht.
Bisher hatte ich solch einfache Grafiken aus Scripten heraus immer mittels >convert -draw "point X,Y"< erledigt.
.pbm ist da sehr oft um einiges einfacher zu Handhaben und wesentlich schneller.
Wieder was neues gelernt, Danke!

Den letzten Satz kann ich gleich wiederholen.

Ich habe sowas bisher zumeist via SVG gemacht, das kann man einfach generieren weil es lesbarer Text ist. Beim Debuggen sieht man auch direkt was Sache ist. Dann habe ich die Ergebnisse in ein passendes Zielformat umgewandelt.