Debo - Fr 14.09.07 11:18
Titel: Optimierung // möglichst viele Kreise in ein Rechteck stanze

---

Hallo,

Mein Problem:

Wie platziere ich möglichst viele gleiche Kreise auf einer Fläche?


Meine Idee:

Ich erstelle mir eine 2Dimensionale Matrix in der jedes Feld 1mm zählt (genauigkeit 1mm).

Nun setzte ich den ersten Kreis soweit wie möglich in eine obere Ecke (angenommen links oben).

Wie definiere ich einen Kreis in meiner Matrix? Ich könnte jeder Zelle meiner Matrix 2 Werte zuteilen: "frei" oder "besetzt", je nachdem ob die Zelle zu einem Kreis gehört oder nicht, aber wie setzte ich einen Kreis bzw. welche Zellen muss ich dafür als "besetzt" markieren. Der Radius sei frei wählbar.

Weiterhin muss ein Sicherheitsabstand von 5mm oder 5 Zellen um den Kreis gesetzt werden, damit Kreise sich nicht tangieren und am Rand das gleiche.

Nun dachte ich mir, lasse ich einfach eine Schleife laufen, die nun versucht von jeder Zelle aus einen Kreis zu "stanzen". Wenn ein anderer Kreis oder der Sicherheitsabstand geschnitten wird, wird kein Kreis gesetzt und man geht zur nächsten Zelle und probiert es da weiter, bis man jede Zelle durch hat.

Zuerst möchte ich die Fläche berechnen: Effektive-Nutzfläche=(Breite-2*Abstand)*(Länge-2*Abstand)
Die Fläche,die durch einen Kreis wegfällt wäre: pi*(r-(abstand/2))²

Nur leider hab ich grad keine Ahnung wie ich das in ein Programm packe.

Danke schonmal im vorraus.

Gruß, Debo.

Wonko - Fr 14.09.07 11:32

---

Hallo,

geht es Dir um das "Wie-programmiere-ich-es" oder "Wie-müssen-sie-angeordnet-sein"?
Erste Frage: k.A.; zweite: "hexagonal dichteste Kugelpackung".

Die Fläche ist bestimmt pi*(r+(abstand/2))² und nicht Deine Formel, oder?

Wenn der Abstand zwischen jedem Kreis und zw. Kreis und Rand gilt, kannst Du ihn auch gleich zum Radius zählen, geht dann vielleicht einfacher. Entsprechend musst Du dann auch Dein Rechteck verkleinern. Berichtige mich, wenn ich auf die Schnelle einen Denkfehler habe.

Grüße

Debo - Fr 14.09.07 11:48

---

Ja du hast recht.

Was mich interessiert ist: "Wie berechne das?" , wenn ich das weiß, werde ich es in ein Programm packen können.

Oder man lässt erst das Programm die Anordnungen machen und berechnet dann die Flächen.

Ich hab bei beiden Lösungen keinen Ansatz.

Wonko - Fr 14.09.07 14:32

---

Bestimmt interessant aber nicht ganz einfach, sicher sogar schwierig.
Bei wikipedia gibt es unter Theorie der endlichen Kugelpackungen [http://de.wikipedia.org/wiki/Theorie_der_endlichen_Kugelpackungen] einen Abschnitt "Mathematischer Hintergrund" und dort wiederum "Endliche Kreispackungen", dort gibt es u.a. ein pdf, das für dich lesenswert sein könnte. Nützlich vielleicht auch: http://de.wikipedia.org/wiki/Keplersche_Vermutung
Ich hoffe, das hilft Dir weiter.