विभाजन छोटे लोगों (2 डी पैकिंग)

Question

को बड़ा आयत मैं एल्गोरिथ्म जो छोटे लोगों को बड़ा स्थिर आकार आयत विभाजन की जरूरत है। मेरे लिए एक आदर्श क्रियान्वयन ऐसा दिखाई:

struct RECT 
{ 
    int l,t,r,b; 
}; 

class BigRect 
{ 
public: 
    // width and height of big rect 
    BigRect(unsigned width, unsigned height); 

    // returns -1 if rect cannot be allocated, otherwise returns id of found rect 
    int GetRect(unsigned width, unsigned height, RECT &out); 

    // returns allocated rect to big rectangle 
    void FreeRect(int id); 
}; 

void test() 
{ 
    BigRect r(10, 10); 

    RECT out; 
    r.GetRect(4, 4, out); // rect found ({0,0,4,4} for example), returns 1 
    r.GetRect(5, 5, out); // rect found ({4,0,9,5} for example), returns 2 

    r.GetRect(6, 6, out); // no place found for rect, returns -1 
    r.FreeRect(2);  // add {4,0,9,5} back to rect 

    r.GetRect(6, 6, out); // rect found (4,0,10,6) 
} 

तो मैं GetRect और FreeRect तरीकों के लिए एल्गोरिथ्म की जरूरत है। किसी भी विचार और लिंक की सराहना की जाएगी।

Answer 1

आप जो करने का प्रयास कर रहे हैं वह ऑनलाइन 2 डी बिन पैकिंग है। यह ऑनलाइन है क्योंकि आप उन्हें बड़ी तस्वीर में पैक करने का प्रयास करने से पहले अपने सभी छोटे चित्रों को हाथ में नहीं रखते हैं। इसके अलावा कुछ छोटी तस्वीरें "विलुप्त हो जाएंगी" और उनकी जगह मुक्त हो जाएगी। दूसरी तरफ, एक ऑफ़लाइन एल्गोरिदम आपको चीजों को करने की अनुमति देता है जैसे कि उन्हें पैक करने से पहले अपनी छोटी तस्वीरों को सबसे छोटे से छोटे से क्रमबद्ध करें।

यहां एक लेख है जो 2 डी पैकिंग में कला की स्थिति का सर्वेक्षण करता है: Survey on two-dimensional packing। यह काफी सैद्धांतिक है।

यह आलेख A New Upper Bound on 2D Online Bin Packing ऑनलाइन 2 डी पैकिंग एल्गोरिदम का वर्णन करने वाले अन्य लेखों को उद्धृत करता है। गेमिंग की दुनिया में

लोग के रूप में आप कर एक ऐसी ही समस्या है; वे इसे बनावट पैकिंग या texture atlas कहते हैं। हालांकि, वे ऑफ़लाइन एल्गोरिदम का उपयोग करते हैं।

जॉन रैटक्लिफ़ बनावट पैकिंग पर एक blog article तैनात। https://gamedev.stackexchange.com/questions/2829/texture-packing-algorithm