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!
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
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.
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
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.
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.
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.
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...
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...
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.