2008-11-04 23 views
19

मेरे पास 2 डी छवि डेटा के एन आइटम हैं जो आयताकार होंगे और मैं उन्हें यथासंभव कुशलतापूर्वक 2 बनावट की एक शक्ति में पैक करना चाहता हूं।आयताकार छवि डेटा को एक वर्ग बनावट में पैक करना

इन रेक्टों को पैक करने के लिए एल्गोरिदम का एक सरल गैर-कुशल और निष्पक्ष कार्यान्वयन करना आसान होगा, लेकिन मुझे यकीन है कि लोग इसे यथासंभव कुशलतापूर्वक स्थान के रूप में करने के लिए एल्गोरिदम के साथ आए हैं। मुझे लाइटमैप पैकिंग के विभिन्न संदर्भ मिल गए हैं जो कि मैं जो खोज रहा हूं उसके समान है, लेकिन लाइटमैपिंग के लिए एल्गोरिदम गैर-आयताकार छवियों को खाते में लेते हैं जो वास्तव में उन चीजों को जटिल करता है जो मुझे चाहिए।

क्या किसी के पास संकेत हैं? एल्गोरिदम या पेपर लेखकों के नाम मुझे Google चाहिए?

धन्यवाद।

उत्तर

5

1 डी में आपकी समस्या को बिन पैकिंग कहा जाता है। शायद यह आपकी खोज के लिए एक अच्छी शुरुआत है।

ध्यान दें कि जिस समस्या को आप हल करना चाहते हैं वह वास्तव में कठिन है (यह एनपी-हार्ड है)। तो आपको इष्टतम समाधान की खोज नहीं करनी चाहिए, लेकिन कुछ चालाक हेरिस्टिकल एल्गोरिदम।

मुझे लगता है कि 1 डी बिन पैकिंग के लिए नीचे-अप गतिशील प्रोग्रामिंग संभव है, लेकिन 2 डी मामले के लिए नहीं।

आप 1 डी समस्या को हल करके अपनी समस्या को सरल बनाने के बारे में सोच सकते हैं, जिससे 1 आयाम में कई (परिवर्तनीय आकार) स्लाइस में बनावट को काटने जैसे प्रतिबंध लग सकते हैं।

एक और संभावना इस पर मेटा-हेरिस्टिक ऑप्टिमाइज़ेशन चल रही है, जैसे विकासवादी एल्गोरिदम या कण स्वार अनुकूलन।

8

मुझे यह वर्णन करने की आवश्यकता है जो आप वर्णन करते हैं।

यह, पायथन कोड मैं प्रयोग किया जाता है यह अजगर कुकबुक में एक नुस्खा है:

Recipe 442299: pack multiple images of different sizes into one image

+0

यह कोड ऐसा नहीं लगता है कि यह एक इष्टतम समाधान की तलाश में है। ऐसा लगता है कि यह सभी छवियों को एक एकल बनावट में पैक करना चाहता है। – ypnos

1

मैं एक ऐसी ही समस्या थी, लेकिन मैं वर्गों पैकिंग किया गया था। इसे आज़माएं: http://www.mrashid.info/blog/stacking-squares-problem.php

सी ++ कोड बहुत ही सुरुचिपूर्ण नहीं है लेकिन कम से कम आपको इस समस्या से संपर्क करने के बारे में मूलभूत विचार मिलता है।

4

बहुत अच्छा और सरल पैकिंग एल्गोरिथ्म यहां पाया जा सकता: http://www.blackpawn.com/texts/lightmaps/

इसके कार्यान्वयन केवल सी के 200 लेता ++ लाइनों, अधिक नहीं (मुझे लगता है कि आप पहले से ही बिटमैप हेरफेर दिनचर्या है)।

इसके पीछे सिद्धांत के लिए जुक्का जिलानकी ("बिन पैक करने के लिए एक हजार तरीके") के लिए एक परिचय है।

पेपर का लेखक सी ++ लाइब्रेरी प्रदान करता है जो वास्तव में मेरे दृष्टिकोण से फूला हुआ है, लेकिन दूसरी ओर इसमें बहुत सारे विकल्प हैं और यह बहुत अच्छी तरह से प्रलेखित है।