Ideale zufällige Verteilung von Kreisen

Jim Gast #1117887
Lesenswert?
• ▲
▼ 
Hi!

Kennt jemand von euch einen guten Algorithmus um Kreise mit einem 
gewissen mittleren Absand möglichst ideal, d.h. viele auf einer Fläche 
überlappungsfrei anzuordnen? Ich habe z.B. 20 Kreise und die sollen auf 
einem A4 Blatt zufällig verteilt ausgedruckt werden, aber sie sollen 
sich nicht überschneiden und ich möchte dass der Algorithmus bis zu 
hohen Packungsdichten funktioniert. Eine Lösung wäre ja, zu versuchen 
zufällig Orte zu wählen und zu schauen ob im Radius schon ein anderer 
ist, aber das erreicht niemals eine optimalePackungsdichte sondern 
blockiert sich ab einer bestimmten Zahl selbst.

Thx!
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
Frank E. (Firma: Q3) #1117894
Lesenswert?
• ▲
▼ 
Ich verstehe nicht ganz, warum du auf den Zufall so viel Wert legst. 
Ansonsten nennt sich das, was du suchst

- "Zuschnitt-Problem",
- "Zuschnitt-Optimierung"
- oder auch "bin packing".

Allerdings laufen alle derartigen Lösungen, die ich dazu kenne, auf 
längliche (1D), rechteckige (2D) oder kubische (3D) Objekte hinaus. Eine 
spezielle Lösung für Kreise habe ich noch nicht gesehen.  Evtl. musst du 
erstmal mit einer Quadrat-Lösung volieb nehmen ...

Frank
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Jim Gast #1118190
Lesenswert?
• ▲
▼ 
Du wirst lachen, eigentlich brauch ichs für Quadrate (kleine Bereiche in 
denen etwas gerendert wird am Bildschirm). Die sollen aber halt 
pseudozufällig angeordnet sein, also wie Klebezettel an der Wand. Nicht 
in einem Gitter und die Zahl der "Zettel" soll spezifizierbar sein. Die 
vorhandenen sollen aber den Platz auf der Wand optimal nutzen.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Frank E. (Firma: Q3) #1118262
Lesenswert?
• ▲
▼ 
Ok, dann musst du den "Objekt-Bestand", d.h. die Liste der zu 
plazierenden Objekte, vorher bilden und in einem Puffer ablegen. Das 
Befüllen dieser Liste kann ja per Zufall erfolgen, während der 
Optimierungsprozess jedoch läuft, muss diese konstant bleiben.

Aber ich muss dich warnen, das ist ein strammer Sack voll Mathematik ...

Guck' mal hier:

http://www.math.tu-dresden.de/~capad/
http://www.math.tu-dresden.de/~capad/cpd-ti.html

Frank
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Karl-heinz S. #1118308
Lesenswert?
• ▲
▼ 
War das nicht sogar ein NP-Problem?

Also von Kreise auf Quadrate zu schließen ist mies, damit verschenkst du 
wieder Platz.

Wenn es nicht so auf die hundertprozentige Dichte ankommt, würde ich 
einfach versuchen wollen, die Quadrate einfach so anzuordnen. Also 
zufällig. Wenns nicht passt, halt an einer anderen Stelle in einem 
anderen Winkel.

Das ganze 1000 mal pro Zettel probieren. Wenn es dann immer noch nicht 
passt, abbrechen und einen kleineren Zettel probieren, bis keine Zettel 
mehr übrig sind.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Trickser Gast #1118675
Lesenswert?
• ▲
▼ 
Parkettiere Deine Fläche vollständig mit Deinen "Zetteln". Diese Zettel
trägst Du dann in eine Liste mit ihren Koordinaten ein.

l = Laenge der Liste = max. Anzahl Zettel
g = gewünschte Anzahl darzustellender Zettel <= l
i = Laufvariable
random() gibt ein Zufallswert aus dem Bereich [0,...,1) aus.

g = 0;
i = 0;
do
{
if (random()<=0.5){g--; "waehle Element aus" Liste[i]; i = i+1 mod l;}
}
while(g);

So erscheinen die gewählten Zettel gleichverteilt.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Läubi .. Persönliche Seite #1118698
Lesenswert?
• ▲
▼ 
Also ganz simpel könntest du es doch so machen:

Du unterteilst (je nach Anzahl der Zettel) die Fläche erstmal in ein 
"Schachbrett". Je nach Anzahl der Zettel sind die Kästchen natürlich 
unterschiedlich groß.
Innerhalb dieser Kästchen bestimmst du pro zettel eine (zufällige) 
Postion sodass der Zettel noch "drin" liegt.

Dann sind die Zettel immer gleichmäßig über die ganze Fläche verteilt, 
und der "Raum" für die verteilung wird nur enger wenn weniger Platz 
ist...
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Gast Gast #1118865
Lesenswert?
• ▲
▼ 
Ein Kollege hatte ne gute Idee: ein simuliertes Gas. Man steckt einfach 
so viele "Moleküle" rein, die sich gegenseitig elastisch abstoßen, bis 
es voll genug ist und hält die Simulation dann zu einem beliebigen 
Zeitpunkt an. Das probier ich mal aus...
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren