एक्सपोज़ लेआउट एल्गोरिदम

Question

मैं कुछ ऐसा कर रहा हूं जो मैक ओएस एक्स एक्सपोज़ में विंडोज़ के साथ करता है। यह वस्तुओं के पहलू अनुपात और उपलब्ध क्षेत्र के पहलू अनुपात को अपनाना है।

असल में, उपलब्ध क्षेत्र पंक्तियों और स्तंभों में बांटा गया है। प्रत्येक सेल में एक आइटम लगाया जाता है (एक पंक्ति और स्तंभ का चौराहे)। कोशिकाओं के पहलू अनुपात के बावजूद वस्तुओं को उनके पहलू अनुपात (यहां width/height) बनाए रखना चाहिए। कोशिकाओं की संख्या वस्तुओं की संख्या से अधिक या बराबर होनी चाहिए। ऐसे मामले में जहां कोशिकाओं की संख्या वस्तुओं की संख्या से अधिक है, अंतिम पंक्ति का पूरी तरह से उपयोग नहीं किया जाएगा। लक्ष्य जितना संभव हो सके आइटमों द्वारा उपयोग किए जाने वाले उपलब्ध क्षेत्र का अधिक होना है। मुझे यकीन है कि प्रत्येक सेल के पहलू अनुपात के करीब आइटम के पहलू अनुपात के लिए बेहतर है।

निम्नलिखित अच्छी तरह से काम करता है जब उपलब्ध क्षेत्र के पक्ष अनुपात आइटम 'पहलू अनुपात के बराबर है:

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

कहाँ: count आइटम्स की संख्या है, round(x) राउंड x निकटतम अभिन्न मूल्य तक, शून्य से दूर आधे रास्ते के मामलों को गोल करना; और ceiling(x) सबसे छोटा अभिन्न मान x से कम नहीं देता है।

मैं Compiz रही है कि निम्नलिखित समान एल्गोरिथ्म का उपयोग करता है, लेकिन यह ध्यान में नहीं ले करता है वस्तुओं और उपलब्ध क्षेत्र के पहलू अनुपात:

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

कहाँ: floor(x) सबसे बड़ा अभिन्न मूल्य नहीं x से अधिक रिटर्न ।

मैंने निम्नलिखित ओ (एन) एल्गोरिदम को एक साथ रखा है जो पंक्तियों और स्तंभों के प्रत्येक संयोजन का परीक्षण करता है और सबसे अच्छा फिट ढूंढता है, लेकिन निश्चित रूप से ओ (1) एल्गोरिदम है क्योंकि यह पहले के समान परिणाम उत्पन्न करता है (ओ (1)) एल्गोरिथ्म जब वस्तुओं और उपलब्ध क्षेत्र के पहलू अनुपात एक ही कर रहे हैं:

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); 
} 

कहाँ: abs(x)x के निरपेक्ष मान देता है।

ध्यान दें: आप यह सब

तो पर अनुकूल नहीं है देख सकते हैं, क्या संभव के रूप में आइटम द्वारा उपयोग सबसे उपलब्ध क्षेत्र के लिए सबसे अच्छा तरीका क्या है? (दूसरे शब्दों में, कैसे मैं सबसे अच्छा फिट लगता है?)

Answer 1

आप

1. कोई क्षैतिज खाई
2. नहीं खड़ी की खाई

ठीक है के साथ आइटम पैक कर सकते हैं, के बिना पैक करते हैं लंबवत अंतरतब क्षैतिज खाई है:

Gh = nrows * availRatio - ncolumns * itemRatio 

या एन के साथ लिखा

Gh = x * availRatio - N * itemRatio/x 

Gh

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

पर 0 के करीब है आप प्लस्तर लगाना जाँच करने के लिए है (x) और मंजिल (एक्स) , और वाई = मंजिल (एन/एक्स)

क्षैतिज अंतराल के बिना पैकिंग उपज:

y = sqrt(N * availRatio/itemRatio) 

आप प्लस्तर लगाना (y) और फर्श (y) की जाँच करने के लिए है, और एक्स = मंजिल (एन/y)

तो खाई के लिए जाँच करने के लिए 4 संयोजन के लिए कर रहे हैं। फिर इसे सबसे छोटे सकारात्मक अंतर के साथ चुनें।

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); 
} 

इसके बजाय अंतराल का उपयोग कर के आप यह भी तय करना कम से कम क्षेत्र इस्तेमाल कर सकते हैं, अंतिम पंक्ति के बाद से/स्तंभ बहुत अच्छी तरह से नहीं भरा जा सकता है।