layout - What is an algorithm to return free space in blocks of largest possible rectangles? -

अल्गोरिदम

इस लेआउट पर विचार करें:

 + ------ ------- + | | | | | + - + | | | ## | | | | ## | | | + - + ------ + | | ###### | | | ###### | + ------ + ------ + 

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

इस तरह:

 1 2 3 4 + ------------- + + - --- ------- + | ############# | | ### ###### | | ############# | | ### ###### | | + - + | | ### + ###### | | ### | | ###### | | ### | | ###### | | ### + ------ | | + - + | ### | ###### | | ### | ###### | + ---- + ------ + 

इनपुट

संलग्न कंटेनर की चौड़ाई और ऊंचाई (मेरे कोड में एक पृष्ठ।)

पहले से ही कब्जा आयत की सूची वे किसी भी रूप में हो सकते हैं जिसे आप चाहते हैं उदा। (X, y, width, height) या (x1, y1, x2, y2)

मैं फ़्लोट्स से काम कर रहा हूं, इसलिए एक गणितीय समाधान को प्राथमिकता दी जाएगी।

< आपके उदाहरण से ऐसा प्रतीत होता है कि आप ओवरलैप को बहिष्कृत करने के लिए नहीं कह रहे हैं (जैसे 1 और 2 में शीर्ष-बायां खंड है।) आम), तो शायद यह आपकी आवश्यकताओं के अनुरूप होगा:

1. कब्जा स्थान द्वारा पहचाने वाले कोनों के आधार पर आयतों में स्थान को विभाजित करें।

3. किसी भी व्यवस्थित क्रम का उपयोग करना (जैसे ऊपर से नीचे तक, बाएं से दाएं):

   3.1 मूल आयत का चयन करें और इसे जितनी दूर हो सके अन्य बुनियादी आयतों के साथ विस्तारित करें जिनके पास एक समान है।

   3.2। इस तरह के विस्तारित आयतों के सभी (अनूठे) सेट करें।

ध्यान दें कि यह खोज / निर्माण चरण 2 से "मूल आयत" पर आधारित है, और पॉइंट-बाय- पूरे स्थान पर इंगित करें, इसलिए प्रदर्शन को बेहतर होना चाहिए।