फिक्स्ड त्रिज्या सर्कल

Question

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

Ze समस्या

Y से एक आयत, एक्स को देखते हुए हलकों की न्यूनतम राशि को खोजने एन एक निश्चित साथ दिया त्रिज्या आर, आयताकार के हर हिस्से को पूरी तरह से कवर करने के लिए आवश्यक है।

---

मैं इसे हल करने के तरीकों के बारे में सोचा है, लेकिन मैं निश्चित नहीं है। यदि प्रत्येक सर्कल एक आंतरिक आयत को परिभाषित करता है, तो R^2 = Wi^2 + Hi^2, जहां Wi और Hi प्रत्येक सर्कल i द्वारा कवर किए गए व्यावहारिक क्षेत्र की चौड़ाई और ऊंचाई हैं। सबसे पहले मैंने सोचा कि मुझे के लिए i = j के लिए Wj के बराबर Wi बनाना चाहिए। इस तरह, मैं मुख्य आयताकार (Wi/Hi = X/Y) के बराबर चौड़ाई/ऊंचाई अनुपात बनाकर समस्या को सरल बना सकता हूं। इस तरह, N=X/Wi। लेकिन XY या इससे भी अधिक के मामले में यह समाधान निश्चित रूप से गलत है।
दूसरा विचार यह था कि किसी भी i के लिए Wi = Hi। इस तरह, वर्ग अंतरिक्ष को सबसे कुशलता से भरते हैं। हालांकि अगर एक बहुत ही संकीर्ण पट्टी बनी हुई है, तो इसे भरने के लिए आयताकारों का उपयोग करने के लिए यह अधिक अनुकूल है, या बेहतर अभी तक - इससे पहले कि आखिरी पंक्ति के लिए आयतों का उपयोग करें।
तब मुझे एहसास हुआ कि कोई भी विचार इष्टतम नहीं है, क्योंकि मैं हमेशा इसे करने के बेहतर तरीके ढूंढ सकता हूं। यह हमेशा अंतिम के करीब होगा, लेकिन अंतिम नहीं होगा।

संपादित
कुछ मामलों में (बड़ा आयत) hexagons में शामिल होने में शामिल होने वर्गों की तुलना में एक बेहतर समाधान होने लगते हैं। तिपतिया घास हेक्सागोनल बनाम:

आगे संपादित
यहाँ 2 तरीकों की तुलना की गई। हेक्सागोनल, बड़े सतहों के लिए, जाहिर है, बेहतर है। मुझे लगता है कि जब आयत पर्याप्त छोटा होता है, आयताकार विधि अधिक कुशल हो सकती है। यह एक झटका है। अब, तस्वीर में आप बाईं ओर 14 मंडलियां देखते हैं, और दाईं ओर 13 मंडल देखते हैं। हालांकि सतह एक सर्कल की तुलना में बहुत अधिक (डबल) अलग है। ऐसा इसलिए है क्योंकि बाईं ओर वे कम ओवरलैप करते हैं, इस प्रकार कम सतह को बर्बाद कर देते हैं।

सवाल अभी भी बनी हुई:

1. नियमित षट्भुज पैटर्न ही सही है? या मुख्य आयत के कुछ हिस्सों में कुछ समायोजन किए जाने चाहिए।
2. क्या नियमित कारणों को "अंतिम समाधान" के रूप में उपयोग न करने के कारण हैं?
3. क्या इस प्रश्न का उत्तर भी है? :)

Answer 1

जब सर्कल को मध्य में पांचवें सर्कल के साथ चार पत्ते वाले क्लॉवर के रूप में निपटाया जाता है, तो एक सर्कल R * 2 * R के बराबर क्षेत्र को कवर करेगा। इस व्यवस्था में, प्रश्न बन जाता है: R * 2 * R के क्षेत्र को कवर करने वाली कितनी मंडल W * H के क्षेत्र को कवर करती हैं?, या N * R * 2 * R = W * H। तो N = W * H/R * 2 * R।

Answer 2

एक्स और वाई के लिए आर की तुलना में बड़ी, हेक्सागोनल (हनीकोम्ब) पैटर्न इष्टतम के करीब है। एक्स-दिशा में मंडलियों के केंद्रों के बीच की दूरी sqrt(3)*R है। वाई-दिशा में पंक्तियों के बीच की दूरी 3*R/2 है, इसलिए आपको लगभग X*Y/R^2 * 2*/(3*sqrt(3)) मंडलियों की आवश्यकता है।

आप एक वर्ग पैटर्न का उपयोग करते हैं, क्षैतिज दूरी बड़ा है (2*R), लेकिन ताकि आप X*Y/R^2 * 1/2 के बारे में हलकों आवश्यकता होगी ऊर्ध्वाधर दूरी, बहुत छोटे (R) है। चूंकि 2/(3*sqrt(3) < 1/2, हेक्सागोनल पैटर्न बेहतर सौदा है।

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

अपने विशिष्ट सवालों के संदर्भ में की तुलना में छोटे होते हैं:

1. हेक्सागोनल पैटर्न पूरे विमान का एक इष्टतम कवर है। एक्स और वाई परिमित के साथ, मुझे लगता है कि बेहतर परिणाम प्राप्त करना अक्सर संभव होता है। मामूली उदाहरण तब होता है जब ऊंचाई त्रिज्या से कम होती है। उस स्थिति में आप सर्कल को प्रत्येक पंक्ति के आगे ले जा सकते हैं जब तक कि सर्कल की प्रत्येक जोड़ी के अंतरण बिंदुओं के बीच की दूरी वाई।

2. नियमित पैटर्न होने से समाधान पर अतिरिक्त प्रतिबंध लगाए जाते हैं, और इसलिए इष्टतम समाधान उन प्रतिबंधों के तहत उन प्रतिबंधों को हटाया जा सकता है। आम तौर पर, कुछ हद तक अनियमित पैटर्न बेहतर हो सकते हैं (mbeckish से जुड़े पृष्ठ देखें)।

3. उसी पृष्ठ पर उदाहरण सभी विशिष्ट समाधान हैं। अधिक सर्कल के साथ समाधान कुछ हद तक हेक्सागोनल पैटर्न जैसा दिखता है। फिर भी, एक बंद-फॉर्म समाधान प्रतीत नहीं होता है।

Answer 3

This साइट पर एक अलग कोण से समस्या पर हमला करता है: यह देखते हुए एन इकाई हलकों, सबसे बड़ा वर्ग वे कवर कर सकते हैं क्या है?

जैसा कि आप देख सकते हैं, क्योंकि मंडलियों की संख्या में परिवर्तन होता है, इसलिए कवर पैटर्न भी होता है।

आपकी समस्या के लिए, मेरा मानना ​​है कि इसका तात्पर्य है: विभिन्न आयताकार आयाम और सर्कल आकार विभिन्न इष्टतम कवर पैटर्न को निर्देशित करेंगे।

Answer 4

हेक्सागोन हीरा से बेहतर है। प्रत्येक इकाई के अंतर्गत आने वाले वृत्त के प्रतिशत क्षेत्र पर विचार करें:

#!/usr/bin/env ruby 

include Math 

def diamond 
    # The distance from the center to a corner is the radius. 
    # On a unit circle, that is 1. 
    radius = 1 

    # The edge of the nested diamond is the hypotenuse of a 
    # right triangle whose legs are both radii. 
    edge = sqrt(radius ** 2 + radius ** 2) 

    # The area of the diamond is the square of the edge 
    edge ** 2 
end 

def hexagon 
    # The hexagon is composed of 6 equilateral triangles. 
    # Since the inner edges go from the center to a hexagon 
    # corner, their length is the radius (1). 
    radius = 1 

    # The base and height of an equilateral triangle whose 
    # edge is 'radius'. 
    base = radius 
    height = sin(PI/3) * radius 

    # The area of said triangle 
    triangle_area = 0.5 * base * height 

    # The area of the hexagon is 6 such triangles 
    triangle_area * 6 
end 

def circle 
    radius = 1 
    PI * radius ** 2 
end 

puts "diamond == #{sprintf "%2.2f", (100 * diamond/circle)}%" 
puts "hexagon == #{sprintf "%2.2f", (100 * hexagon/circle)}%" 

और

$ ./geometrons.rb 
diamond == 63.66% 
hexagon == 82.70% 

इसके अलावा, नियमित hexagons उच्चतम शिखर बहुभुज है कि एक regular tessellation of the plane फार्म हैं।

Answer 5

मेरी गणना के अनुसार सही जवाब है:

D=2*R; X >= 2*D, Y >= 2*D, 
N = ceil(X/D) + ceil(Y/D) + 2*ceil(X/D)*ceil(Y/D) 

विशेष मामले में अगर के लिए एक्स/डी और वाई/डी 0 के बराबर है, तो

N = (X + Y + X*Y/R)/D 

Case 1: R = 1, X = 2, Y = 2, then N = 4 

Case 2: R = 1, X = 4, Y = 6, then N = 17 

Case 3: R = 1, X = 5, Y = 7, then N = 31 

शेष आशा है कि यह मदद करता है।