mikrocontroller.net

Forum: Offtopic Ideale zufällige Verteilung von Kreisen


Autor: Jim (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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!

Autor: Frank Esselbach (Firma: Q3) (qualidat)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Jim (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Frank Esselbach (Firma: Q3) (qualidat)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Karl-heinz Strunk (cletus)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Jim (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Naja, die Zettel sind alle gleich groß. Ein Sack voll Mathe macht nix, 
ist beruflich, daher zieh ichs durch egal wie viel Aufwand dahinter 
steht.

Autor: Trickser (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Trickser (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
sorry "g=0" vor der Schleife ist natürlich murks.

Autor: Läubi .. (laeubi) Benutzerseite
Datum:

Bewertung
0 lesenswert
nicht 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...

Autor: Gast (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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...

Autor: Stefan P. (form)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Hier ging es schonmal um etwas ganz ähnliches: 
Beitrag "Kreise im Kreis"

Bitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail, Yahoo oder Facebook? Keine Anmeldung erforderlich!
Mit Google-Account einloggen | Mit Yahoo-Account einloggen | Mit Facebook-Account einloggen
Noch kein Account? Hier anmelden.