Chciałbym napisać prosty program, który akceptuje zestaw okien (szerokość + wysokość) oraz rozdzielczość ekranu i wyświetla układ tych okien na ekranie, aby okna zajmowały najwięcej miejsca. Dlatego można zmienić rozmiar okna, zachowując output size >= initial size
i proporcje. Tak więc dla okna chciałbym, aby algorytm zwrócił krotkę .( x , y , w i d t h , h e i g h t )
Wierzę, że może to być odmiana plecaka 2D. Próbowałem przeglądać wyniki w Internecie, ale większość z nich miała dużo tła (i żadnej implementacji), co utrudniało mi śledzenie.
Mniej interesuje mnie najszybszy możliwy algorytm, ale bardziej coś, co jest praktyczne dla mojej konkretnej potrzeby.
algorithms
computational-geometry
packing
user-interface
daniel.jackson
źródło
źródło
Odpowiedzi:
Chociaż twoje pytanie tego nie mówi, zakładam, że nie chcesz, aby okna nakładały się na siebie.
Jednym podejściem do tego problemu jest użycie solvera ograniczającego, takiego jak Choco . Wystarczy zapisać ograniczenia kodujące problem, dostroić solver do działania w sprytny sposób, a następnie pozwolić mu działać. Oznacza to, że całe myślenie, które musisz zrobić, zostanie poświęcone na znalezienie dobrego sposobu na zakodowanie problemu, a nie na opracowanie algorytmu oraz wykonanie programowania i strojenia. Oto częściowa odpowiedź na początek.
Załóżmy, że rozmiar ekranu to . .xmax×ymax
Dla każdego okna, , będziesz mieć zestaw zmiennych i ograniczeniaWi xi,yi,hi,wi
Teraz musisz zadbać o nakładanie się okien. Dla każdej pary okien, , gdzie , wygenerujesz ograniczenia takie jak poniżej, które wychwytują, że żaden narożnik pojawia się w . Dla , wygeneruj ograniczenie:Wi,Wj i≠j Wj Wi (x,y)∈{(xj,yj),(xj+wj,yj),(xj,yj+hj),(xj+wj,yj+hj)}
Ograniczenia określone do tej pory opisują tylko okna, które nie zachodzą na siebie, ale nie rozlewają się po bokach ekranu, spełniają pewne ograniczenia dotyczące minimalnego rozmiaru i zachowują proporcje.
Aby uzyskać dobre dopasowanie, musisz określić metrykę, która uchwyci, co to znaczy być dobrym układem. Jedną z możliwości jest założenie, że chcesz, aby okna były mniej więcej równe pod względem wielkości i / lub że chcesz zminimalizować „białe znaki”. Nie sądzę, że można to określić za pomocą Choco, ale może to być możliwe przy innym rozwiązaniu ograniczeń (ktoś inny może tu pomóc).
Choco pozwala zmaksymalizować wrt do funkcji celu określonej jako pojedyncza zmienna. W oparciu o ten pomysł można zmaksymalizować następujące elementy:
pisząc ograniczenie i informując Choco o maksymalizacji .cost=∑i(hi+wi) cost
źródło
Zacząłem pisać prototyp rozwiązania brutalnej siły, które, mam nadzieję, można zoptymalizować do punktu, w którym będzie to praktyczne.
Po pierwsze, niektóre definicje: Niech będzie zbiorem wszystkich okien. Każde okno składa się z dla współrzędnych x, y oraz szerokości i wysokości. Okno jest inicjowane z minimalną szerokością i wysokością.W w xw,yw,ww,hw
Wejściem algorytmu jest ekran , który ma szerokość i wysokość oraz listę okien.S
Działa mniej więcej tak:
Jest kilka rzeczy, które należy poprawić:
S.coordinates()
jest teraz bardzo wolny. Powtarza wszystkie punktyS.width x S.height
i sprawdza, czy każdy znajduje się w jednym z okien S.S.put()
sprawdza, czy jego parametr pokrywa się z resztą okien S, wykonując test wymieniony w odpowiedzi Dave'a. Może można to poprawić za pomocą drzew interwałów ?S.score()
obecnie zwraca który jest po prostu obszarem wszystkich okien. Musi uwzględniać inne zmienne, aby tworzyć lepsze układy.Powyższa funkcja musi wypróbować wszystkie permutacje aby uzyskać najlepszy możliwy wynik.W
Obecnie próbuję znaleźć odpowiednią strukturę danych do reprezentowania ekranu i jego okien, musi on obsługiwać te zapytania:
źródło