Wie viele Quadrate kann gepackt werden, in einen Kreis?

Entschuldige ich mich für das schreiben so eine lange Antwort. Mein Ansatz ist zu beginnen mit einem theoretischen maximum und garantiert ein minimum. Wenn Sie nähern sich dem problem, Sie können diese Werte verwenden, um zu bestimmen, wie gut jeder Algorithmus Sie verwenden. Wenn Sie sich vorstellen können, ein besseres minimum, dann können Sie das stattdessen benutzen.

Können wir definieren eine Obere Grenze für das problem, indem Sie einfach die Fläche des Kreises

Upper Limit = floor( (PI * (r pow 2)) /(L * L) )

Wobei L die Breite oder Höhe der Quadrate, die Sie packen und r ist der radius des Kreises, Sie packen die Quadrate in. Wir sind sicher, dies ist eine Obere Grenze, da a) wir müssen eine diskrete Anzahl von Boxen und b) wir nicht mehr Platz als die Fläche des Kreises. (Ein formaler Beweis würde irgendwo arbeiten entlang der Linien von " wir nehmen an, wir hatten einen Kasten als diese, dann ist die Summe der Fläche der Boxen größer sein müssten als die Fläche des Kreises).

Also mit einer oberen Grenze in der hand, wir können jetzt keine Lösung, gibt es für alle Kreise und nennen es eine minimale Lösung.

So, betrachten wir eine Lösung, die gibt es für alle Kreise, indem Sie einen Blick auf das größte Quadrat können wir fit in den Kreis.

Dem größten Platz können Sie fit in den Kreis hinein, hat 4 Punkte auf der perimiter, und hat eine Breite und Länge von sqrt(2) * radius (mit Satz des pythagoras und mit dem radius der Länge der kürzeren Kanten)

Also das erste, was wir bemerken, ist, dass, wenn sqrt(2) * radius kleiner ist als die dimension der Quadrate, dann können Sie nicht passen alle Plätze im Kreis, weil afterall, das ist der größte Platz passen.

Nun, wir können eine einfache Berechnung, um teilen dieses großen Platz in einem regelmäßigen Gitter von Quadraten mit L angegeben, was uns mindestens eine Lösung auf das problem. So haben Sie ein raster von sqaures innerhalb dieser maximalen Platz. Die Anzahl der Quadrate können Sie passen in eine Zeile dieses raster ist

floor((sqrt(2) * radius)/L)

Und so diese minimale Lösung behauptet, dass Sie können mindestens

Lower Limit = floor((sqrt(2) * radius)/L) pow 2

Anzahl der Quadrate innerhalb des Kreises.

So, in Fall, dass Sie verloren haben, alles, was ich Tat war nehmen Sie den größten Platz, ich könnte passen in den Kreis hinein, und dann packen Sie so viele Felder wie möglich in ein reguläres Gitter im inneren, dass, um mir mindestens eine Lösung.

Wenn du eine Antwort bekommen auf 0 für diese Phase ist, dann können Sie nicht passen alle Plätze innerhalb des Kreises.

Nun bewaffnet mit einem theoreitical maximum und ein absolutes minimum, Sie können beginnen, versuchen, jede Art von Heuristik-Algorithmus, wie Sie für die Verpackung Quadrate. Ein einfacher Algorithmus wäre, nur split mit dem Kreis, die in Zeilen und fit wie viele sqaures, wie Sie können in jeder Zeile. Sie können dann nehmen Sie diese mindestens als Leitlinie, um sicherzustellen, dass Sie kam mit einer besseren Lösung. Wenn Sie möchten, verbringen Sie mehr Rechenleistung auf der Suche nach einer besseren Lösung, verwenden Sie die theoretischen als Leitfaden für die, wie nahe man an die theoretisch besten.

Und wenn Sie sich dafür interessieren, könnten Sie herausfinden, was die maximale und minimale theoretische Prozentsatz der Deckung der Mindest-Algorithmus, den ich idenfied gibt Sie. Der größte Platz umfasst stets in einem festen Verhältnis (pi/4 oder über 78,5% der internen Fläche des Kreises glaube ich). So dass die maximale theoretische minimum liegt bei 78.5% decken. Und die minimale nicht-trivial (dh. nicht null) theoretische minimum ist, wenn man nur Platz für 1 Platz im inneren der größte Platz, was passiert, wenn die Plätze, die Sie sind in der Verpackung sind 1 größer als die Hälfte der Breite und Höhe des größten Platz können Sie fit in den Kreis. Im Grunde Sie nehmen nur 25% der das innere Quadrat mit 1 verpackt Quadrat, das heißt, Sie bekommen einen ungefähren Abdeckung von über 20%

InformationsquelleAutor Matt Esch

Können Sie packen so viele Felder, wie Sie in einem Kreis. Wenn Sie Zweifel an dieser Aussage, zeichnen Sie einen großen Kreis auf ein Stück Papier, zeichnen Sie ein Quadrat mit der Seitenlänge 10^(-18)m drin, wiederholen. Wenn man in der Nähe der Grenze des Kreises, starten, zeichnen von Quadraten mit der Seitenlänge von 10^(-21)m.

Also Ihr Erster Schritt muss sein, verfeinern Sie Ihre Frage und Ihr problem genauer.

InformationsquelleAutor High Performance Mark