Jak opracować algorytm do rozmieszczania (skalowalnych) okien na ekranie tak, aby zajmował jak najwięcej miejsca?

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 sizei 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 $i$$(x, y, width, height)$

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.

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 . .$x_{max}\times y_{max}$

Dla każdego okna, , będziesz mieć zestaw zmiennych i ograniczenia$W_i$$x_i, y_i, h_i, w_i$

• $x_i,y_i,h_i,w_i\ge 0$
• $x_i + w_i \le x_{max}$
• $y_i + h_i \le y_{max}$
• Być może także pewne ograniczenia dotyczące minimalnego rozmiaru okien, np. i tak dalej.$h_i\ge 100$
• Ograniczenia aspektu: Jeśli współczynnik proporcji wynosi 3: 4, ograniczenie może być takie jak , gdzie jest małym niezerowym terminem błędu, który pozwala na rozmiary okien, ponieważ w innym przypadku nadmiernie ograniczysz problem.$4h_i - \epsilon \le 3 w_i \le 4 h_i + \epsilon$$\epsilon$

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:$W_i, W_j$$i\neq j$$W_j$$W_i$$(x,y)\in\{(x_j,y_j), (x_j+w_j,y_j), (x_j,y_j+h_j), (x_j+w_j,y_j+h_j)\}$

• $\neg(x_i \le x\le x_i + w_j \wedge y_i\le y \le y_i+h_j)$ .

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:

• $\sum_i (h_i + w_i)$

pisząc ograniczenie i informując Choco o maksymalizacji .$\mathit{cost}=\sum_i (h_i + w_i)$$\mathit{cost}$

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$$x_w, y_w, w_w, h_w$

Wejściem algorytmu jest ekran , który ma szerokość i wysokość oraz listę okien.$S$

Działa mniej więcej tak:

void fit(W, S, i, n, result)
    if i == n
        if S.score() < result.score()
            result = S
        return

    w = W[i]
    foreach x, y in S.coordinates()
        set w position to (x, y)
        while S.put(w) # check that w doesn't overlap with S's other windows and add it
            fit(W, S, i+1, n, result)
            S.windows.pop()
            w.grow()
        w.restoresize()

Jest kilka rzeczy, które należy poprawić:

• S.coordinates()jest teraz bardzo wolny. Powtarza wszystkie punkty S.width x S.heighti 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.$\sum_{w \in S.windows} (h_w \cdot w_w)$

• 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:

• zwraca listę współrzędnych, w których można ustawić dane okno bez nakładania się na inne
• wstaw okno w pozycji x, y (już sprawdzone, że się nie zachodzi)
• zwróć wszystkie okna