छोटे वर्ग/आयताकारों के साथ एक वर्ग को कैसे भरें?

Question

काम पर मेरे कार्यालय में, हमें दीवारों को पेंट करने की अनुमति नहीं है, इसलिए मैंने वर्गों और आयतों को फ्रेम करने का फैसला किया है, उन्हें कुछ अच्छा कपड़े लगाया है, और उन्हें दीवार पर व्यवस्थित किया है।

मैं एक विधि लिखने की कोशिश कर रहा हूं जो मेरे इनपुट आयाम (9 'x 8' 8 ") और न्यूनतम/अधिकतम आकार (1 'x 3', 2 ', 4', आदि ..) उत्पन्न करेगा दीवार को भरने के लिए वर्गों और आयतों का एक यादृच्छिक पैटर्न। मैंने इसे हाथ से करने की कोशिश की, लेकिन मुझे जो लेआउट मिला है उससे मैं खुश नहीं हूं, और जब भी मैं लेआउट को 'यादृच्छिक' करना चाहता हूं तो इसमें लगभग 35 मिनट लगते हैं। ।

Answer 1

एक समाधान x * y वर्गों के साथ शुरू करने के लिए और बेतरतीब ढंग से आयत बनाने के लिए एक साथ वर्गों विलय है:

स्यूडोकोड कुछ ऐसा दिखाई देगा। आप एल्गोरिदम को छोटे आयतों के भार से समाप्त होने से अलग आकार के वर्गों के लिए अलग-अलग भार देना चाहेंगे (यानी बड़े आयताकारों को शायद बड़े होने तक विलय के लिए उठाए जाने का अधिक अवसर होना चाहिए)।

Answer 2

आप एक शुद्ध कार्यक्रमों की समस्या पर बात कर रहे हैं;) नामक तकनीक बिन पैकिंग छोटी से छोटी क्षेत्र संभव में डिब्बे के एक नंबर पैक करने के लिए कोशिश करता है कि नहीं है वहाँ सामग्री का भार वहाँ बाहर है:

http://en.wikipedia.org/wiki/Bin_packing_problem

http://mathworld.wolfram.com/Bin-PackingProblem.html

http://www.cs.sunysb.edu/~algorith/files/bin-packing.shtml

तो तुम यादृच्छिक वर्गों का एक लोड बना सकते हैं और एक बिन पैकर के माध्यम से इसे चलाने के अपने पैटर्न उत्पन्न करने के लिए 'सकता है'।

मैंने खुद को एक बिन पैकिंग एल्गोरिदम लागू नहीं किया है, लेकिन मैंने इसे एक नाइके वेबसाइट के लिए एक सहयोगी द्वारा देखा है। शुभकामनाएं

Answer 3

चूंकि आप आयताकारों का आकार चुन सकते हैं, यह एक कठिन समस्या नहीं है।

मैं कहना चाहता हूँ कि आप के रूप में सरल कुछ कर सकते हैं:

 
    Pick an (x,y) coordinate that is not currently inside a rectangle. 
    Pick a second (x,y) coordinate so that when you draw a rectangle between 
     the two coordinates, it won't overlap anything. The bounding box of 
     valid points is just bounded by the nearest rectangles' walls. 
    Draw that rectangle. 
    Repeat until, say, you have 90% of the area covered. At that point you 
     can either stop, or fill in the remaining holes with as big rectangles 
     as possible. 

यह अंक की पीढ़ी parametrize, और फिर एक आनुवंशिक एल्गोरिथ्म बनाने के लिए दिलचस्प हो सकता है। फिटनेस फ़ंक्शन यह होगा कि आपको व्यवस्था कितनी पसंद आएगी - यह आपके लिए सैकड़ों व्यवस्थाएं तैयार करेगी, और आप उन्हें 1-10 के पैमाने पर रेट करेंगे। इसके बाद यह सबसे अच्छा ले जाएगा और उनको ट्विक कर देगा, और तब तक दोहराएगा जब तक आपको एक ऐसी व्यवस्था न मिल जाए जो आपको वाकई पसंद है।

Answer 4

बिन पैकिंग या स्क्वायर पैकिंग?

बिन पैकिंग: http://www.cs.sunysb.edu/~algorith/files/bin-packing.shtml

स्क्वायर पैकिंग: http://www.maa.org/editorial/mathgames/mathgames_12_01_03.html

यह वास्तव में अधिक एक पुराने स्कूल यादृच्छिक वर्ग चित्रकला डेमो की तरह, 8-बिट कंप्यूटिंग दिनों के लगभग, खासकर यदि आप ओवरलैप कोई आपत्ति नहीं है लगता है । लेकिन यदि आप विशेष रूप से geeky होना चाहते हैं, यादृच्छिक वर्ग बनाएँ और पैकिंग समस्या के लिए हल करें।

Answer 5

एक Treemap

Answer 6

मैं सब कुछ में एक सर्पिल धीरे-धीरे चल रहा है। किसी भी बिंदु पर आप एक बिंदु है जहां अपने समाधान 'के अयोग्य' साबित हुआ है पहुंच जाते हैं तो उत्पन्न होगा (आईई तरह लगता है, किसी भी वर्ग में नहीं डाल सकते शेष मध्य में बाधाओं को पूरा करने के लिए), पहले के मसौदे पर जाएं और कुछ स्क्वायर बदलें जब तक कि आपको एक सुखद समाधान न मिल जाए।

public Board GenerateSquares(direction, board, prevSquare) 
{ 
    Rectangle[] rs = generateAllPossibleNextRectangles(direction, prevSquare, board); 
    for(/*all possible next rectangles in some random order*/)){ 
     if(board.add(rs[x]){ 
      //see if you need to change direction) 
      Board nBoard = GenerateSquares(direction, board, rs[x]); 
      if(nBoard != null) return nBoard; //done 
      else board.remove(rs[x]); 
     } 
    } 
    //all possibilities tried, none worked 
    return null; 
} 

}

Answer 7

मेरा सुझाव है: एक बहुभुज की स्थापना चार कोने के साथ आकार (maxside तक) आयत गांठ बदलती में खाया जा करने के लिए द्वारा

प्रारंभ:

public double[] fillBoard(double width, double height, double maxside) { 
    double[] dest = new int[0]; 
    double[] poly = new int[10]; 
    poly[0] = 0; poly[1] = 0; poly[2] = width; poly[3] = 0; 
    poly[4] = width; poly[5] = height; poly[6] = 0; poly[7] = height; 
    poly[8] = 0; poly[9] = 0; 
    ... 
    return dest; /* x,y pairs */ 
} 

फिर एक यादृच्छिक शिखर चुनते हैं, बहुभुज लाइनों को खोजने लाइन के 2 एक्स अधिकतम (समावेशी) के भीतर। सभी क्षैतिज रेखाओं के सभी लंबवत रेखाओं और वाई मानों के x मान खोजें। मानों के बीच मूल्यों के लिए रेटिंग जेनरेट करने के लिए प्रत्येक एक्स और वाई मान, और समीकरणों को चुनने की "भलाई" के लिए रेटिंग बनाएं। गुडनेस को शेष बहुभुज में रेखाओं की संख्या को कम करने के रूप में मापा जाता है। छद्म-यादृच्छिक जनरेटर का उपयोग करते हुए दो एक्स निर्देशांक या दो वाई निर्देशांक के बीच मानों की प्रत्येक सीमा के लिए तीन विकल्प उत्पन्न करें। अच्छे विकल्पों की ओर झुकाव भारित औसत आधार पर एक्स के जोड़े और वाई मानों की जोड़ी को रेट करें और चुनें। पॉली सरणी से अपना आकार काटकर और आयत सरणी में आयताकार निर्देशांक जोड़कर सूची में नए आयताकार को लागू करें।

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

संपादित

संभावित ओवरलैप समाप्त करने के लिए कुछ हिट परीक्षण करते हैं। और टाइपिंग शुरू करने से पहले कुछ पालक खाएं। ;)

Answer 8

एक और विचार:

1. Randomly generate points on the wall 
    Use as many points as the number of rectangles you want 
    Introduce sampling bias to get cooler patterns 
2. Build the kd-tree of these points 

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

(देखें: http://en.wikipedia.org/wiki/Kd-tree)

संपादित करें: बस JTreeMap को देखा, लग रहा है इस तरह एक सा क्या अपने कर रही है।

Answer 9

फिलिप बेऔडॉइन उत्तर का निर्माण।

अन्य भाषाओं में ट्रेमैप कार्यान्वयन हैं जिनका आप उपयोग भी कर सकते हैं। रूबी में RubyTreeMap साथ आप

require 'Treemap' 
require 'Treemap/image_output.rb' 

root = Treemap::Node.new 0.upto(100){|i| root.new_child(:size => rand) } 

output = Treemap::ImageOutput.new do |o| 
    o.width = 800 
    o.height = 600 
end 

output.to_png(root, "C:/output/test.png") 

कर सकता है लेकिन यह आयत क्रमबद्ध करता है, तो यह बहुत यादृच्छिक नहीं लगती है, लेकिन यह एक शुरुआत हो सकता है। Rubytreemap.rubyforge.org/docs/index देखें।अधिक जानकारी के लिए एचटीएमएल

Answer 10

1. इनपुट क्षेत्र को परिभाषित करें;
2. पूरी ऊंचाई के माध्यम से कई यादृच्छिक क्षैतिज स्थानों पर लंबवत रेखाएं बनाएं;
3. पूरी चौड़ाई के माध्यम से कई लंबवत स्थितियों पर क्षैतिज रेखाएं खींचे;
4. मनमानी मात्रा से कुछ "कॉलम" ऊपर या नीचे शिफ्ट करें;
5. शिफ्ट कुछ "पंक्तियाँ" बाएं या दाएं मनमाना राशि के आधार पर (यह पूर्ण क्षैतिज तेजी प्राप्त करने के लिए कुछ कोशिकाओं का उप-विभाजन के लिए आवश्यक हो सकता है,
6. निकालें तेजी के रूप में सौंदर्य की दृष्टि से आवश्यक

यह ग्राफिकल विधि करने के लिए समानताएं है। Brian's answer