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

20

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.

daniel.jackson
źródło
1
Jeśli zmieniasz rozmiar okna, nie „utrzymujesz jego początkowego rozmiaru”, tylko współczynnik proporcji, jak sądzę.
Emre,
1
Możesz zmienić rozmiar jednego okna, aby zasłonić ekran, na czym polega problem?
2
Popieram komentarz Saeeda. Potrzebujesz dodatkowych ograniczeń, takich jak minimalne rozmiary, aby zminimalizować sumę zmian rozmiaru, jeśli chcesz wykluczyć trywialne rozwiązania. Nota bene: matematycy nazywają teselacje problemami kafelkowymi .
Raphael
1
Być może lepiej jest powiedzieć, że chcesz zmaksymalizować minimalny widoczny obszar okna i zminimalizować maksymalny widoczny obszar okna, ale konflikty są dozwolone, czy nie? Edytuj swoje pytanie, aby było wolne od błędów, myślenie o bieżącym opisie problemu nie jest łatwe.
2
@ daniel.jackson: Sugeruje, abyś dążył do konstelacji, w której najmniejsze okno jest tak duże, jak to możliwe, tzn. nie masz naprawdę małych okien. Matematycznie można powiedzieć, że maksymalizujesz z W zestawem okien. minwWsize(w)W
Raphael

Odpowiedzi:

9

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 ograniczeniaWixi,yi,hi,wi

  • xi,yi,hi,wi0
  • xi+wixmax
  • yi+hiymax
  • Być może także pewne ograniczenia dotyczące minimalnego rozmiaru okien, np. i tak dalej.hi100
  • 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.4hiϵ3wi4hi+ϵϵ

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,WjijWjWi(x,y){(xj,yj),(xj+wj,yj),(xj,yj+hj),(xj+wj,yj+hj)}

  • ¬(xixxi+wjyiyyi+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:

  • i(hi+wi)

pisząc ograniczenie i informując Choco o maksymalizacji .cost=i(hi+wi)cost

Dave Clarke
źródło
To wygląda obiecująco i na pewno będę grać z Choco, aby zobaczyć, jak to działa i jak szybko.
daniel.jackson
Ale po co to tak ogólnie wyrażać? Myślę, że możesz sformułować ograniczenia jako nierówności liniowe, co oznacza, że ​​masz waniliowy program liniowy.
Suresh
@Suresh: Zapraszam do opracowywania. Nie od razu widzę, jak to zrobić.
Dave Clarke,
1

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ą.Wwxw,yw,ww,hw

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.wS.windows(hwww)

  • 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
daniel.jackson
źródło