Ile kwadratów można spakować do koła?

Question

Ile kwadratów o rozmiarze a × a można zapakować w okrąg o promieniu R?

Nie potrzebuję rozwiązania. Potrzebuję tylko początkowego pomysłu.

Answer 1

Przepraszam za napisanie tak długiej odpowiedzi. Moje podejście to zacząć od teoretycznego maksimum i gwarantowanego minimum. Kiedy podejmiesz problem, możesz użyć tych wartości, aby określić, jak dobry jest każdy używany algorytm. Jeśli możesz wymyślić lepsze minimum, możesz użyć tego zamiast tego.

Możemy zdefiniować górny limit problemu po prostu za pomocą obszaru okręgu

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

gdzie L jest szerokość lub wysokość kwadratów jesteś pakowania i R jest promieniem okręgu ty pakują kwadraty do. Jesteśmy pewni, że jest to górny limit, ponieważ a) musimy mieć dyskretną liczbę pól ib) nie możemy zajmować więcej miejsca niż obszar koła. (Formalny dowód działałby gdzieś na wzór założenia, że ​​mamy jeszcze jedno pole niż to, wtedy suma pola pól będzie większa niż powierzchnia koła).

Tak więc z górnym limitem w ręku możemy teraz zastosować dowolne rozwiązanie dla wszystkich kręgów i nazwać to rozwiązaniem minimalnym.

Rozważmy rozwiązanie dla wszystkich kręgów, patrząc na największy kwadrat, który możemy zmieścić wewnątrz kręgu.

Największy plac można zmieścić wewnątrz okręgu ma 4 punkty na perimiter i ma szerokość i długość sqrt(2) * radius (przy użyciu twierdzenia Pitagorasa i stosując promień o długości krótszych krawędziach)

Pierwszą rzeczą, na którą zwracamy uwagę, jest to, że jeśli sqrt(2) * radius jest mniejszy niż rozmiar twoich kwadratów, to nie możesz dopasować żadnych kwadratów do koła, ponieważ ostatecznie jest to największy kwadrat, jaki możesz zmieścić.

Teraz możemy wykonać proste obliczenia, aby podzielić ten duży kwadrat na regularną siatkę kwadratów przy użyciu podanego L, co da nam przynajmniej jedno rozwiązanie problemu. Masz więc siatkę kwadratów wewnątrz tego maksymalnego kwadratu. Liczba kwadratów można zmieścić w jednym rzędzie z tym tej siatki jest

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

A więc ta minimalna rozwiązanie zapewnia, że ​​można mieć przynajmniej

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

liczbę kwadratów wewnątrz okręgu.

Więc na wypadek, gdybyś się zgubił, wszystko co zrobiłem, to wzięcie największego kwadratu, który zmieściłbym się w kręgu, a następnie spakowanie jak największej liczby kwadratów do zwykłej siatki wewnątrz, co dałoby mi przynajmniej jedno rozwiązanie.

Jeśli uzyskasz odpowiedź na poziomie 0 dla tego etapu, to nie możesz dopasować żadnych kwadratów wewnątrz okręgu.

Teraz uzbrojony w teoretyczne maksimum i absolutne minimum, możesz zacząć próbować dowolnego heurystycznego algorytmu, który chcesz do pakowania kwadratów. Prostym algorytmem byłoby po prostu podzielić krąg w wiersze i dopasować tyle wierszy, ile można do każdego wiersza. Możesz wtedy wziąć to minimum za wskazówkę, aby upewnić się, że wymyśliłeś lepsze rozwiązanie. Jeśli chcesz poświęcić więcej mocy obliczeniowej na szukanie lepszego rozwiązania, użyj teorii jako wskazówki, jak blisko jesteś do teoretycznego najlepszego.

I jeśli ci na tym zależy, możesz sprawdzić, jaki jest maksymalny i minimalny teoretyczny procent pokrycia minimalnego algorytmu, który zidentyfikowałem. Największy kwadrat zawsze obejmuje stały stosunek (pi/4 lub około 78,5% wewnętrznego obszaru koła, jak sądzę). Maksymalne teoretyczne minimum to 78,5% pokrycia. Minimalne, nie trywialne (tj. Niezerowe) teoretyczne minimum to wtedy, gdy można zmieścić tylko 1 kwadrat wewnątrz największego kwadratu, co ma miejsce, gdy kwadraty, które pakujesz, są większe niż połowa szerokości i wysokości największego kwadratu, który możesz pasuje do koła. Zasadniczo zajmujesz nieco ponad 25% wewnętrznego kwadratu z 1 wypełnionym kwadratem, co oznacza, że ​​otrzymujesz przybliżoną pokrywę około 20%.

Answer 2

Możesz zapakować dowolną liczbę kwadratów w kółko. Jeśli wątpisz w to stwierdzenie, narysuj duże kółko na kawałku papieru, a następnie narysuj kwadrat o boku długości 10^(- 18) m, powtórz. Kiedy zbliżysz się do granicy koła, zacznij rysować kwadraty o boku długości 10^(- 21) m.

Twoim pierwszym krokiem musi być precyzyjniejsze sformułowanie pytania i dokładniejsze określenie problemu.

Answer 3

Po prostu strzał w ciemno po kilku minutach myślenia ...

Co jeśli pracował z połową okręgu i podwoił ją na końcu. Zacznę od siatki kwadratów o długości średnicy i szerokości promienia, zasadniczo pokrywającej półkole. Następnie sprawdź wszystkie 4 rogi każdego kwadratu i upewnij się, że ich współrzędne znajdują się w promieniu koła. Wymagałoby to oczywiście wykreślenia okręgu i kwadratów na jakimś układzie współrzędnych lub siatce.

Mam nadzieję, że to ma sens ... To w głowie i wydaje się nieco trudne do wyartykułowania :)

EDIT: Po narysowaniu go, myślę, że ta metoda będzie działać przy odrobinie szczypanie. Wyrównuję kwadraty wzdłuż średnicy, ale przesuwać pierwszy, aż pasuje. Ustaw go na miejscu i zacznij układać kolejne kwadraty obok niego, aż przestaną pasować. Przejdź do krawędzi tej linii kwadratów i powtarzaj te same kroki, aż rzędy kwadratów osiągną promień.

Answer 4

Rasteryzuj kółko za pomocą czegoś podobnego do midpoint circle algorithm. Liczba wypełnionych pikseli to liczba kwadratów, które możesz zmieścić w kole. Oczywiście, ponieważ w rzeczywistości nie wypełniasz pikseli, po prostu je licząc, to powinno zająć czas proporcjonalny do obwodu koła, a nie jego obszaru.

Musisz ostrożnie wybrać promień rasteryzacji, aby liczyć tylko piksele znajdujące się wewnątrz kręgu.

Edytuj: Może to nie być dokładnie poprawne, ponieważ możliwe jest, że zastosowanie przesunięcia subpikselowego do siatki może zmienić wynik. Zostawię tutaj odpowiedź, ponieważ może to stanowić użyteczny punkt wyjścia dla dokładnego rozwiązania.