Bagaimana merancang algoritma untuk mengatur (resizable) windows pada layar untuk mencakup ruang sebanyak mungkin?

20

Saya ingin menulis sebuah program sederhana yang menerima satu set jendela (lebar + tinggi) dan resolusi layar dan menampilkan pengaturan dari jendela-jendela tersebut di layar sedemikian rupa sehingga windows mengambil ruang paling besar. Oleh karena itu dimungkinkan untuk mengubah ukuran jendela, sambil mempertahankan output size >= initial sizedan aspek rasio. Jadi untuk jendela , saya ingin algoritma mengembalikan tuple .i(x,y,width,height)

Saya percaya ini mungkin variasi dari 2D Knapsack. Saya sudah mencoba memeriksa hasil di web tetapi kebanyakan dari mereka memiliki banyak latar belakang (dan tidak ada implementasi) yang menyulitkan saya untuk mengikuti.

Saya kurang tertarik pada algoritma tercepat yang mungkin, tetapi lebih pada sesuatu yang praktis untuk kebutuhan spesifik saya.

daniel.jackson
sumber
1
Jika Anda mengubah ukuran jendela, Anda tidak "mempertahankan ukuran awalnya", hanya rasio aspeknya, saya kira.
Emre
1
Anda dapat mengubah ukuran satu jendela untuk menutupi layar, apa masalahnya?
2
Saya komentar kedua Saeed. Anda memerlukan batasan tambahan seperti ukuran minimal, tujuan meminimalkan jumlah resizing jika Anda ingin mengecualikan solusi sepele. Catatan: ahli matematika sepertinya menyebut masalah ubin tessellations .
Raphael
1
Mungkin lebih baik untuk mengatakan, Anda ingin memaksimalkan area jendela minimum yang dapat dilihat dan meminimalkan area jendela maksimum, tetapi konflik diperbolehkan atau tidak? Harap edit pertanyaan Anda untuk membuatnya bebas bug, memikirkan pernyataan masalah saat ini tidak mudah.
2
@ daniel.jackson: Dia menyarankan Anda harus berjuang untuk konstelasi di mana jendela terkecil adalah sebesar mungkin, yaitu Anda tidak memiliki jendela yang sangat kecil. Secara matematis, Anda dapat mengatakan Anda memaksimalkan dengan W himpunan windows. minwWsize(w)W
Raphael

Jawaban:

9

Meskipun pertanyaan Anda tidak mengatakannya, saya berasumsi bahwa Anda tidak ingin windows tumpang tindih.

Salah satu pendekatan untuk masalah ini adalah dengan menggunakan pemecah kendala seperti Choco . Seseorang cukup menuliskan batasan-batasan yang menyandikan masalah Anda, menyetel pemecah untuk bertindak dengan cara yang cerdas, dan kemudian membiarkannya berjalan. Ini berarti bahwa semua pemikiran yang perlu Anda lakukan akan dihabiskan untuk menemukan cara pengkodean masalah yang baik, bukan merancang algoritma dan melakukan pemrograman dan penyetelan. Ini jawaban parsial untuk membantu Anda memulai.

Asumsikan bahwa ukuran layar adalah .xmax×ymax

Untuk setiap jendela, , Anda akan memiliki satu set variabel dan kendalax i , y i , h i , w iWixi,yi,hi,wi

  • xi,yi,hi,wi0
  • xi+wixmax
  • yi+hiymax
  • Mungkin juga beberapa kendala pada ukuran minimal windows, mis. dan sebagainya.hi100
  • Batasan aspek: Jika rasio aspek adalah 3: 4, batasannya bisa kira-kira seperti , di mana ϵ adalah beberapa istilah kesalahan kecil yang tidak nol untuk memungkinkan jendela yang tidak sempurna ukuran, karena kalau tidak Anda akan lebih kendala masalah.4hiϵ3wi4hi+ϵϵ

Sekarang Anda perlu merawat tumpang tindih jendela. Untuk setiap pasangan windows, , di mana i j , Anda akan menghasilkan kendala seperti berikut ini, yang menangkap bahwa tidak ada sudut W j muncul dalam W i . Untuk ( x , y ) { ( x j , y j ) , ( x j + w j , y j ) , ( x j , yWi,WjijWjWi , menghasilkan kendala:(x,y){(xj,yj),(xj+wj,yj),(xj,yj+hj),(xj+wj,yj+hj)}

  • .¬(xixxi+wjyiyyi+hj)

Kendala yang ditentukan sejauh ini hanya menggambarkan jendela non-tumpang tindih yang tidak tumpah di sisi layar, yang memenuhi beberapa batasan ukuran minimal, dan yang mempertahankan rasio aspek mereka.

Untuk mendapatkan kecocokan yang baik, Anda perlu menentukan metrik yang menangkap artinya menjadi tata letak yang baik. Satu kemungkinan adalah menganggap bahwa Anda ingin menjaga ukuran jendela kira-kira sama dan / atau bahwa Anda ingin meminimalkan "ruang putih". Saya tidak berpikir bahwa ini dapat dispesifikasikan menggunakan Choco, tetapi dimungkinkan dengan pemecahan kendala lainnya (orang lain mungkin dapat membantu di sini).

Choco memang memungkinkan seseorang untuk memaksimalkan wrt ke fungsi objektif yang ditentukan sebagai variabel tunggal. Berdasarkan ide ini, Anda dapat memaksimalkan hal berikut:

  • i(hi+wi)

cost=i(hi+wi)cost

Dave Clarke
sumber
Ini terlihat menjanjikan dan saya pasti akan bermain dengan Choco untuk melihat bagaimana ini bekerja, dan seberapa cepat.
daniel.jackson
Tapi mengapa ungkapan itu yang umum? Saya pikir Anda dapat menyebut kendala sebagai ketidaksetaraan linear, yang berarti bahwa apa yang Anda miliki adalah program linear vanilla.
Suresh
@ Suresh: Jangan ragu untuk menjelaskan. Saya tidak segera tahu caranya.
Dave Clarke
1

Saya mulai menulis prototipe untuk solusi brute force, yang diharapkan dapat dioptimalkan ke titik di mana itu akan praktis.

Wwxw,yw,ww,hw

S

Ini bekerja kira-kira begitu:

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()

Ada beberapa hal yang harus diperbaiki:

  • S.coordinates()sangat lambat sekarang. Iterates semua poin dalam S.width x S.heightdan memeriksa apakah masing-masing berada di salah satu jendela S.

  • S.put()memeriksa apakah parameternya tumpang tindih dengan sisa jendela S dengan melakukan tes yang disebutkan dalam jawaban Dave. Mungkin ini bisa diperbaiki dengan menggunakan pohon interval ?

  • S.score()wS.windows(hwww)

  • W

Saat ini saya mencoba untuk mencari tahu struktur data yang sesuai untuk mewakili layar dan jendelanya, ia perlu mendukung pertanyaan ini:

  • mengembalikan daftar koordinat tempat jendela yang diberikan dapat diposisikan tanpa tumpang tindih dengan yang lain
  • masukkan jendela pada posisi x, y (sudah diverifikasi tidak tumpang tindih)
  • kembalikan semua jendela
daniel.jackson
sumber