Exposé Layout Algorithm

Question

Tôi đang tạo một thứ gì đó để đặt các mục tương tự với những gì Mac OS X thực hiện với các cửa sổ trong Exposé. Nó thích nghi với tỷ lệ khung hình của các mục và tỷ lệ khung hình của khu vực có sẵn.

Về cơ bản, khu vực có sẵn được chia thành các hàng và cột. Một mục được đặt trong mỗi ô (giao điểm của một hàng và cột). Các mục phải duy trì tỷ lệ khung hình (ở đây width/height) mặc dù tỷ lệ khung hình của ô. Số lượng ô phải lớn hơn hoặc bằng số lượng mục. Trong trường hợp số lượng ô lớn hơn số lượng mục, hàng cuối cùng sẽ không được sử dụng đầy đủ. Mục tiêu là có càng nhiều khu vực sẵn có được sử dụng bởi các mặt hàng càng tốt. Tôi chắc chắn tỷ lệ khung hình của mỗi ô càng gần với tỉ lệ cỡ ảnh của mặt hàng càng tốt.

Các công việc sau tốt khi tỉ lệ diện tích có sẵn là tương đương với tỉ lệ màn hình của các hạng mục:

rows := round(sqrt(count)); 
columns := ceiling(sqrt(count)); 

đâu: count là số mặt hàng; round(x) vòng x với giá trị tích phân gần nhất, làm tròn các trường hợp nửa chừng cách xa 0; và ceiling(x) trả về giá trị tích phân nhỏ nhất không nhỏ hơn x.

Tôi biết Compiz sử dụng các thuật toán tương tự sau đó, nhưng nó không đưa vào tài khoản các tỷ lệ khía cạnh của các mặt hàng và khu vực có sẵn:

rows := floor(sqrt(count + 1)); 
columns := ceiling(count/rows); 

đâu: floor(x) trả về giá trị không thể thiếu lớn nhất không lớn hơn x .

Tôi gộp lại thuật toán O (n) sau đây để kiểm tra mọi kết hợp của hàng và cột và phù hợp nhất, nhưng chắc chắn có thuật toán O (1) vì nó tạo ra kết quả tương tự như đầu tiên (O (1)) thuật toán khi tỷ lệ khía cạnh của các mặt hàng và khu vực có sẵn đều giống nhau:

fit (itemCount, itemRatio, availableRatio) 
{ 
    bestRows := infinity; 
    bestColumns := infinity; 
    bestDiff := infinity; 

    for (rows := 1; rows <= count; rows += 1) 
    { 
     columns := ceiling(count/rows); 

     cellWidth := availableRatio/columns; 
     cellHeight := 1.0/rows; 
     cellRatio := cellWidth/cellHeight; 

     diff := abs(cellRatio - itemRatio); 

     if (diff < bestDiff) 
     { 
      bestRows := rows; 
      bestColumns := columns; 
      bestDiff := diff; 

      if (diff = 0) 
       break; 
     } 
    } 

    return (bestRows, bestColumns); 
} 

đâu: abs(x) trả về giá trị tuyệt đối của x.

Chú ý: Bạn có thể nhận thấy điều này không được tối ưu hóa ở tất cả

Vì vậy, cách tốt nhất để có diện tích có sẵn hầu hết sử dụng bởi các mặt hàng càng tốt là những gì? (Nói cách khác, làm thế nào để tìm thấy phù hợp nhất?)

Answer 1

Bạn có thể đóng gói các mặt hàng với

1. không có khoảng cách ngang
2. không có khoảng cách thẳng đứng

Ok, chúng ta hãy đóng gói mà không khoảng cách dọc.Sau đó, khoảng cách ngang là:

Gh = nrows * availRatio - ncolumns * itemRatio 

hoặc bằng văn bản với N

Gh = x * availRatio - N * itemRatio/x 

Gh gần 0 tại

x² = N * itemRatio/availRatio 
x = sqrt(N * itemRatio/availRatio) 

Bạn phải kiểm tra ceil (x) và sàn (x) và y = floor (N/x)

Đóng gói không có khoảng cách theo chiều ngang:

y = sqrt(N * availRatio/itemRatio) 

Bạn phải kiểm tra ceil (y) và sàn (y), và x = sàn (N/y)

Vì vậy, có đến 4 kết hợp để kiểm tra sự chênh lệch. Sau đó chọn điều đó với khoảng cách tích cực nhỏ nhất.

fit (itemCount, itemRatio, availableRatio) { 
    x := sqrt(itemcount * itemRatio/availableRatio); 
    x1 := floor(x); 
    y1 := ceil(itemCount/x1); 
    x2 := ceil(x); 
    y2 := ceil(itemCount/x2); 

    y := sqrt(itemcount * availableRatio/itemRatio); 
    y3 := floor(x); 
    x3 := ceil(itemCount/y3); 
    y4 := ceil(x); 
    x4 := ceil(itemCount/y4); 

    gap := y1 * availableRatio - x1 * itemRatio; 
    x := x1; 
    y := y1; 

    gap2 := y2 * availableRatio - x2 * itemRatio; 
    if (gap2 >= 0 && gap2 < gap || gap < 0) { 
     gap := gap2; 
     x := x2; 
     y := y2; 
    } 

    gap3 := x3 * itemRatio/availRatio - y3; 
    if (gap3 >= 0 && gap3 < gap || gap < 0) { 
     gap := gap3; 
     x := x3; 
     y := y3; 
    } 

    gap4 := x4 * itemRatio/availRatio - y4; 
    if (gap4 >= 0 && gap4 < gap || gap < 0) { 
     gap := gap4; 
     x := x4; 
     y := y4; 
    } 

    return (x, y); 
} 

Thay vì sử dụng khoảng cách, bạn cũng có thể sử dụng khu vực tối thiểu để quyết định vì hàng/cột cuối cùng có thể không được điền rất tốt.