2012-01-16 5 views
7

जैसा कि शीर्षक पहले से कहता है कि मुझे सी/सी ++ सोर्सकोड या एक लाइब्रेरी की आवश्यकता है जिसका उपयोग मैं 2 डी आयताकार आकारों के साथ बिन पैकिंग समस्या को हल करने के लिए कर सकता हूं जहां बिन आयताकार भी है और आयतों को भी बेहतर फिट करने के लिए 90 डिग्री कोणों से घूर्णन किया जा रहा है । मेरे पास पहले से ही सभी आवश्यक मान हैं, इसलिए मुझे कोई ऑनलाइन पैकिंग एल्गोरिदम की आवश्यकता नहीं है।क्या एक आयताकार बिन (वर्ग नहीं) और घूर्णन के साथ 2 डी बिन पैकिंग को हल करने के लिए कोई सी ++ स्रोत/lib है?

मुझे केवल एक lib मिला जो स्क्वायर बिन से संबंधित है और घूर्णन के बिना जो मेरी आवश्यकताओं के लिए वास्तव में पर्याप्त कुशल नहीं है।

मैं वास्तव में एक आयताकार बिन और रोटेशन को संभालने वाले सी/सी ++ की सराहना करता हूं।

धन्यवाद।

पीएस: गणना के लिए आवश्यक समय महत्वपूर्ण नहीं है, केवल नतीजा है।

पी पी एस: यह ..., सी या सी ++ हो गया है और मैं कुछ भी उपयोगी खोज stackoverflow नहीं मिला

+0

लगभग दोहराना प्रश्न: http://stackoverflow.com/questions/8637785/difficult-2d-bin-packing-algorithm-to-place-a-rectangle-in-xy-location/8638099#8638099 – Lalaland

उत्तर

11

http://clb.demon.fi/files/RectangleBinPack.pdf कुंजी है। यह 2 डी बिन पैकिंग पर संदर्भ है।

आप अपनी ज़रूरत को पूरा करने के लिए वहां एल्गोरिदम में से एक को संशोधित करने में सक्षम हो सकते हैं। मुझे संदेह है कि रोटेशन की आवश्यकता है, एल्गोरिदम बहुत उन्नत हैं जैसे वे हैं।

यह (https://github.com/Lalaland/PixelPacker/blob/master/src/algoMaxRects.cpp) मैक्सरेक्ट्स एल्गोरिदम को कार्यान्वित करने का एक उदाहरण है।

उपयोग करने के लिए अगले आयत का चयन करते समय आपको शायद एल्गोरिदम के शीर्ष पर संशोधन करना होगा। बस यह पूरी सूची के माध्यम से साइकिल चलाने के साथ आयताकारों के विभिन्न अभिविन्यास को भी देखें।

+0

हाय, धन्यवाद आपके उत्तर के लिए। क्या आप कृपया घूर्णन के लिए जांच को लागू करने के लिए कहां और क्या परिवर्तन आवश्यक हैं, इस पर थोड़ा और विस्तार कर सकते हैं? – HardCoder

+1

आप यहां लेखक का कोड भी ढूंढ सकते हैं: https://github.com/juj/RectangleBinPack – Brian

4

मैं कुछ सप्ताह पहले इस सूत्र पाया, स्किम जवाब में पीडीएफ पढ़ने, और लेखकों कोड के साथ चारों ओर toying के बाद, मैं एक पुनर्लेखन का जो अधिक मेरी जरूरतों (बनावट एटलस पैकिंग)

अनुकूल किया - अगर किसी और रुचि रखता है ... https://github.com/chris-stones/BinPack2D

  • उपयोगकर्ता प्रस्तुत आयतों (मूल फ़ाइल नाम, आदि)
  • पैक कई डिब्बे (GL_EXT_texture_array 2 डी बनावट एटलस सरणी के लिए) के साथ एक डाटा-संरचना बंडल करने की अनुमति दें

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

कोई दस्तावेज नहीं है, हेडर फ़ाइल के शीर्ष पर exampleProgram() देखें।

+0

अच्छा कार्यान्वयन, क्रिस। कोड बहुत साफ है और पैकिंग उच्च गुणवत्ता का है। ब्रूट फोर्स चौराहे परीक्षण हालांकि, एक काफी प्रदर्शन हॉग है। परीक्षणों की संख्या को कम करने के लिए किसी प्रकार का केडी-पेड़ होना फायदेमंद हो सकता है।प्रदर्शन में सुधार करने का एक और तरीका प्रति कैनवास आयताकारों की संख्या को कम करने के लिए केवल छोटे कैनवास आकारों का उपयोग करना होगा। –

संबंधित मुद्दे