#1 4. September 2009 Zuletzt von einem Moderator bearbeitet: 14. April 2017 Ich stehe zur Zeit vor einem Problem. Ich bin mir relativ sicher, dass es eine mathematische Lösungsweise für das Problem gibt, welche mir aber momentan nicht in den Sinn kommen mag. Zur verdeutlichung eine Skizze : Die Fläche A möchte ich mit Kreisen (abb.2) füllen, sprich die Fläche A soll ganz von Kreisflächen ausgefüllt werden. Dabei möchte ich aber so wenige Kreise wie möglich verbrauchen. Die Kreise haben einen gegebenen Radius R welcher nicht verändert werden darf ! Die Kreise dürfen dabei die Fläche A überschneiden. Die Schnittflächen der Kreise sollten also möglichst gering sein. Zudem sollten die Kreiszentren Z innerhalb der Fläche A liegen. Mein erster Gedanke war die Fläche A in Vierecke zu unterteilen und dann damit weiterzuarbeiten, jedoch hoffe ich darauf eine "schöne" Lösung zu finden. Hinweise würden mich sehr freuen ! + Multi-Zitat Zitieren
#2 4. September 2009 AW: Fläche mit Kreisen ausfüllen Öh, deinen Angaben zu folgekannst du das doch mittels eines einzigen Kreises schaffen ? Zentrum möglichst mittig in die Fläche a, und dann einfach den Radius erweitern, bis alles abgedeckt ist. grüz KK Ansonsten solltest du die Regeln etwas differenzieren + Multi-Zitat Zitieren
#3 4. September 2009 AW: Fläche mit Kreisen ausfüllen Entschuldigt die Unklarheiten, es sollen Kreise mit festen Radien sein, welche nicht verändert werden können. Diese Radien sind wesentlich kleiner als die Fläche A. + Multi-Zitat Zitieren
#4 4. September 2009 AW: Fläche mit Kreisen ausfüllen schneid die fläche a und die kreise maßstabsgetreu aus und leg dann den kreis so hin wie es dir am sinnvollsten vorkommt und mal dann mitm bleistifft drumherum... dann kannst solange probieren bist das beste raus hast... ne rechnung gibts dafür net und ne methode mit der du garantiert auf die kleinste anzhal kommst auch net... + Multi-Zitat Zitieren
#5 4. September 2009 AW: Fläche mit Kreisen ausfüllen würd es auch so machen. wie willst du den ne freiform-fläche in eine mathematische funktion packen? wäre es ein dreieck oder so. dann ist es kein problem, aber so nicht. viel spaß beim ausschneiden und probieren =) + Multi-Zitat Zitieren
#6 4. September 2009 AW: Fläche mit Kreisen ausfüllen Das war eigentlich genau der Ansatz den ich umgehen wollte :/. Ich lasse den Thread mal offen, vielleicht kommen ja noch geniale Einfälle. + Multi-Zitat Zitieren
#7 4. September 2009 AW: Fläche mit Kreisen ausfüllen Ich gehe davon aus das die Fläche A nicht überschritten werden darf. unter der premisse ist die Lösung unedlich da ein kreis die Ränder deiner Fläche A immer nur an genau einem Punkt ausfüllt. Und die Umrandung besteht aus unendlich vielen Punkten wenn man es genau nimmt. greetz + Multi-Zitat Zitieren
#8 4. September 2009 AW: Fläche mit Kreisen ausfüllen Wäre / ist es denn möglich wenn die Kreise die Fläche überschneiden dürfen? + Multi-Zitat Zitieren
#9 4. September 2009 AW: Fläche mit Kreisen ausfüllen wenn sich die kreise überschneiden dürfen, dann ja, andernfalls sind wir wieder bei der lösung von unendlich dennoch: hier eine optimale lösung zu finden ist nicht trivial. + Multi-Zitat Zitieren
#10 4. September 2009 AW: Fläche mit Kreisen ausfüllen Hast du mir dazu irgendwelche Informationen? Eine annährende Lösung wäre erstmal auch schon genug. Danke ! + Multi-Zitat Zitieren
#11 5. September 2009 AW: Fläche mit Kreisen ausfüllen genetische algorithmen dürften hier in vertretbarem aufwand zu einem optimum führen. für DAS optimum wirst du hingegen laaaange rechnen müssen + Multi-Zitat Zitieren
#12 6. September 2009 AW: Fläche mit Kreisen ausfüllen Teil die fläche a in verschiedene abschnitte auf und verwende dann integrale. ist doch kein problem.... + Multi-Zitat Zitieren
#13 6. September 2009 AW: Fläche mit Kreisen ausfüllen und das hilft genau was, bei der problemstellung eine fläche möglichts optimal mit kreisen zu füllen?! + Multi-Zitat Zitieren
#14 6. September 2009 AW: Fläche mit Kreisen ausfüllen Nochmal zu deiner Frage, das Problem ist nicht trivial lösbar und meines Wissens existiert dafür auch kein Algorithmus, das absolute Optimum zu finden. Da hilft nur sowas in der Art wie Brute-Force. Darüberhinaus existieren Algorithmen, die Näherungslösungen in deutlich weniger zeit finden. Diese sind allerdings immer noch viel zu aufwendig, sie per Hand durchzuführen. Das Erstaunliche bei solchen Problemen ist, dass der Mensch in sehr sehr kurzer Zeit mit winzigem Aufwand auf sehr gute Näherungslösungen kommt. Also wird wohl für dich das beste sein, einfach Kreise auszuschneiden und das selber so hinzuschieben wie es passt, wenn das nicht gerade ne Aufgabe in Informatik ist oder ihr dazu grad intensiv was gemacht habt. + Multi-Zitat Zitieren