के लिए कुशल पैकिंग एल्गोरिदम मैं पैकिंग एल्गोरिदम की तलाश में हूं जो एक नियमित बहुभुज को आयतों और दाएं त्रिकोणों में कम करेगा। एल्गोरिदम को जितना संभव हो उतने आकारों का उपयोग करने का प्रयास करना चाहिए और इसे लागू करने के लिए अपेक्षाकृत आसान होना चाहिए (चुनौती की कठिनाई को देखते हुए)।नियमित बहुभुज
यदि संभव हो, तो इस प्रश्न का उत्तर सुझाए गए एल्गोरिदम में उपयोग की जाने वाली सामान्य हेरिस्टिक्स को समझाया जाना चाहिए।
मुझे लगता है कि उत्तर नियमित बहुभुज के लिए काफी सरल है।
समरूपता की धुरी खोजें, और प्रत्येक चरम और उसके दर्पण के बीच एक रेखा खींचें। यह बहुभुज को trapezoids में विभाजित करता है। प्रत्येक trapezoid एक आयताकार और दो दाएं त्रिकोण में बदल दिया जा सकता है।
यह साबित करके आप कुछ अतिरिक्त क्रेडिट प्राप्त कर सकते हैं कि इससे न्यूनतम संख्या में टाइल्स पैदा होते हैं। :) – Svante
अब मुझे विश्वास है कि यह वास्तव में इष्टतम है :-) – Mau
नहीं। यह हमेशा इष्टतम नहीं है। उदाहरण के लिए x = 0 धुरी के समानांतर दो तरफ एक नियमित हेक्सागोन लें। फिर यह एल्गोरिदम 2 आयत और 4 दाएं त्रिकोण उत्पन्न करता है, लेकिन 1 आयताकार और 4 त्रिकोण पर्याप्त होंगे। फिर भी समाधान शायद काफी अच्छा और लागू करने में आसान है। – abc
यह विशेष रूप से आयताकार + सही त्रिभुज नहीं है, लेकिन टेस्सेलिंग बहुभुज में देखने के लिए एक अच्छा शोध बिंदु Voronoi Diagrams and Delaunay Triangulations और here और here है।
वास्तव में, यदि "बस ठीक त्रिकोण" पर्याप्त है, इन आप के लिए त्रिकोणाकार की गारंटी है, और आप हमेशा दो समकोण त्रिभुज में किसी भी त्रिकोण विभाजित कर सकते हैं, यदि आप वास्तव में उन की जरूरत है। या आप सही त्रिकोणों और दाएं त्रिकोणों से कुछ आयताकार बनाने के लिए त्रिकोणों की "टिप्स" काट सकते हैं।
आप ear-clipping भी कोशिश कर सकते हैं, या तो मूल रूप से व्यापक रूप से, यदि आप जानते हैं कि आपके पास नियमित रूप से नियमित बहुभुज हैं, या "सबसे बड़ा उत्तल चंक" बंद कर रहे हैं। फिर, सही त्रिकोण बनाने के लिए प्रत्येक शेष त्रिभुज को दो में विभाजित करें।
polygon http://static.eruciform.com/images/polygon.png
आप एक तरह से और फिर दूसरे व्यापक एक समलम्ब बनाने के लिए द्वारा कम टूटता है बनाने के लिए कोशिश करते हैं और इसे दूसरे तरीके से विभाजित किया जा सकता है, लेकिन आप तो सुनिश्चित करें कि आपके झाडू लाइन hasn बनाने के लिए एक चेक करना है किसी और रेखा को किसी जगह पर पार नहीं किया। आप हमेशा व्यावहारिक रूप से फ्रैक्टल के साथ भी कान-क्लिप कर सकते हैं।
हालांकि, यह कभी-कभी बहुत पतले त्रिकोण बनाता है। आप हेरिस्टिक्स कर सकते हैं, जैसे किनारे के साथ लगातार क्लिपिंग करने के बजाय, "सबसे बड़ा ले लो", लेकिन ओ (एन^2) के पास आने में अधिक समय लगता है। डेलाउने/वोर्नोई कम स्लिम त्रिकोण के साथ ज्यादातर मामलों में इसे और अधिक तेज़ी से कर देगा।
बिल्कुल आयताकार और दाएं त्रिकोण होना चाहिए। मुझे पता है कि यह अजीब लगता है, लेकिन यह एक उपयोगकर्ता की आवश्यकता है। – Steve
अपडेट किया गया। आप किसी भी त्रिभुज को सही त्रिकोण और आयत में आसानी से बदल सकते हैं। – eruciform
डेलाउने त्रिकोण यहां आदर्श नहीं हैं क्योंकि वे बीच में अतिरिक्त, अनावश्यक बिंदुओं को पेश करते हैं। उन आंतरिक बिंदुओं में से प्रत्येक को आसन्न बहुभुज वर्टेक्स में "खींचा जा सकता है" और आपको त्रिभुजों के एक छोटे से सेट के साथ छोड़ दिया जाता है। –
आप कुछ बचे हुए पीछे छोड़कर the largest rectangle that can fit in the polygon "काटने" का प्रयास कर सकते हैं। जब तक आप त्रिकोणीय टुकड़ों के साथ समाप्त नहीं हो जाते, तब तक बचे हुए आयतों के आयतों को काटते रहें। फिर, यदि आवश्यक हो तो आप उन्हें दो दाएं त्रिकोण में विभाजित कर सकते हैं। मुझे नहीं पता कि यह हमेशा समाधान प्रदान करेगा जो आपको कम से कम आयत और सही त्रिभुज देगा।
मुझे लगता है कि यह एक अच्छा विचार नहीं है: पहले आयत के साथ जितना संभव हो सके उतना क्षेत्र खाने से आपको "सबसे आसान" आकार के साथ छोड़ने वाला नहीं है। – Mau
यह स्पष्ट नहीं था कि उनकी आवश्यकताओं क्या थी। कम से कम कुल आकार या कम से कम आकार का क्षेत्र ... – eruciform
हालांकि नियमित बहुभुज के लिए, यह आपको अभी भी "अच्छे" आकार देगा। दोबारा, मुझे नहीं पता कि यह आपको "सबसे इष्टतम" समाधान देगा या नहीं। –
यह एल्गोरिदम कक्षा या कंप्यूटर ग्राफिक्स कक्षा के लिए है? – eruciform
यह कक्षा के लिए नहीं है। मैं स्कूल में नहीं हूँ – Steve
असल में, मैं किसी ऐसे व्यक्ति को देने के इच्छुक हो सकता हूं जो आईफोन, मैक डेस्कटॉप और .NET के लिए प्रोग्राम कर सकता है, तो सवाल का जवाब दे सकता है। ;) – Steve