सर्कल में कितने वर्ग पैक किए जा सकते हैं?

Question

आकार के कितने वर्ग × त्रिज्या आर के एक वृत्त में पैक किया जा सकता है?

मुझे समाधान की आवश्यकता नहीं है। मुझे बस एक शुरुआती विचार की ज़रूरत है।

Answer 1

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

हम बस वृत्त के क्षेत्रफल का उपयोग करके समस्या के लिए एक ऊपरी सीमा निर्धारित कर सकते हैं

Upper Limit = floor((PI * (r pow 2))/(L * L)) 

कहाँ एल चौड़ाई या वर्गों आप पैकिंग कर रहे हैं की ऊंचाई है और r वृत्त की त्रिज्या है आप वर्गों को पैक कर रहे हैं। हमें यकीन है कि यह एक ऊपरी सीमा है क्योंकि ए) हमारे पास बक्से की एक अलग संख्या होनी चाहिए और बी) हम सर्कल के क्षेत्र की तुलना में अधिक जगह नहीं ले सकते हैं। (एक औपचारिक सबूत कहीं भी काम करेगा, मान लीजिए कि हमारे पास इससे एक और बॉक्स था, तो बक्से के क्षेत्र का योग सर्कल के क्षेत्र से अधिक होगा)।

तो हाथ में ऊपरी सीमा के साथ, अब हम सभी हलकों के लिए मौजूद कोई भी समाधान ले सकते हैं और इसे न्यूनतम समाधान कहते हैं।

तो, आइए सर्कल के अंदर फिट होने वाले सबसे बड़े वर्ग को देखकर सभी हलकों के लिए मौजूद समाधान पर विचार करें।

सबसे बड़ा वर्ग आप मंडली के भीतर फिट कर सकते हैं perimiter पर 4 अंक है, और एक चौड़ाई और sqrt(2) * radius की लंबाई

(कम किनारों की लंबाई के लिए पाइथागोरस प्रमेय का उपयोग कर और त्रिज्या का उपयोग करके) है तो सबसे पहले हम ध्यान देते हैं कि यदि sqrt(2) * radius आपके वर्गों के आयाम से कम है, तो आप सर्कल में किसी भी वर्ग को फिट नहीं कर सकते हैं, क्योंकि बाद में, यह सबसे बड़ा वर्ग है जिसे आप फिट कर सकते हैं।

अब हम इस बड़े वर्ग को आपके द्वारा निर्दिष्ट एल का उपयोग करके वर्गों के नियमित ग्रिड में विभाजित करने के लिए एक सीधा गणना कर सकते हैं, जो हमें समस्या का कम से कम एक समाधान देगा। तो आपके पास इस अधिकतम वर्ग के अंदर स्क्वायर का ग्रिड है। वर्गों की संख्या आप इस इस ग्रिड से एक पंक्ति में फिट कर सकते हैं

floor((sqrt(2) * radius)/ L) 

है और इसलिए इस न्यूनतम समाधान का दावा है आप मंडली के भीतर वर्गों के कम से कम

Lower Limit = floor((sqrt(2) * radius)/ L) pow 2 

संख्या हो सकता है।

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

यदि आपको इस चरण के लिए 0 पर उत्तर मिलता है तो आप सर्कल के अंदर किसी भी वर्ग को फिट नहीं कर सकते हैं।

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

और यदि आप इसके बारे में परवाह करते हैं, तो आप कम से कम न्यूनतम एल्गोरिदम I कवर किए गए कवर के अधिकतम और न्यूनतम सैद्धांतिक प्रतिशत को काम कर सकते हैं। सबसे बड़ा वर्ग हमेशा एक निश्चित अनुपात (पीआई/4 या सर्कल के आंतरिक क्षेत्र का लगभग 78.5% मुझे लगता है) को कवर करता है। तो अधिकतम सैद्धांतिक न्यूनतम 78.5% कवर है। और न्यूनतम गैर-तुच्छ (यानि शून्य) सैद्धांतिक न्यूनतम तब होता है जब आप केवल सबसे बड़े वर्ग के अंदर 1 वर्ग फिट कर सकते हैं, जो तब होता है जब आप जो वर्ग पैक कर रहे हैं, वह आधा चौड़ाई से बड़ा है और आप सबसे बड़े वर्ग की ऊंचाई कर सकते हैं सर्कल में फिट असल में आप 1 पैक वाले वर्ग के साथ आंतरिक वर्ग के 25% से अधिक लेते हैं, जिसका अर्थ है कि आपको लगभग 20%

Answer 2

आप सर्कल में जितना चाहें उतने वर्गों को पैक कर सकते हैं। यदि आप इस कथन पर संदेह करते हैं, तो कागज के टुकड़े पर एक बड़ा सर्कल खींचें, फिर इसके अंदर एक लंबाई को 10^(- 18) मीटर के साथ खींचें, दोहराएं। जब आप सर्कल की सीमा के पास जाते हैं, तो 10^(- 21) मीटर की तरफ की लंबाई वाले वर्गों को रेखांकित करना प्रारंभ करें।

तो आपका पहला कदम आपके प्रश्न को परिशोधित करना और अपनी समस्या को और सटीक रूप से अवश्य देना चाहिए।

Answer 3

सोचा था की कुछ मिनट के बाद अंधेरे में बस एक गोली मार दी ...

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

मुझे आशा है कि यह समझ में आता है ... यह मेरे सिर में है और यह स्पष्ट करने के लिए :)

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

Answer 4

midpoint circle algorithm जैसे कुछ का उपयोग करके सर्कल को रास्टराइज़ करें। भरे पिक्सल की संख्या सर्कल में फिट वर्गों की संख्या है। बेशक, चूंकि आप वास्तव में पिक्सेल भर नहीं रहे हैं, बस उन्हें गिनते हैं, इसमें सर्कल की परिधि के लिए आनुपातिक समय लेना चाहिए, न कि इसके क्षेत्र में।

आपको रास्टरराइज़ेशन के लिए त्रिज्या को सावधानी से चुनना होगा, ताकि आप केवल पिक्सल की गणना कर सकें जो सर्कल के अंदर सख्ती से हैं।

संपादित करें: यह बिल्कुल सही नहीं हो सकता है, क्योंकि यह संभव है कि ग्रिड में उप-पिक्सेल ऑफसेट लागू करने से परिणाम बदल सकता है। मैं यहां जवाब छोड़ दूंगा क्योंकि यह एक सटीक समाधान के लिए एक उपयोगी प्रारंभिक बिंदु प्रदान कर सकता है।