छेद और चौराहे के लिए आयताकारों का संग्रह कैसे जांचें?

Question

मैं आयताकारों और छेदों के लिए - x और y रेंज के लिए Google guavas रेंज का उपयोग करके "तुलनीय" जावा क्लास द्वारा "आयताकार" जावा क्लास द्वारा कार्यान्वित एक संग्रह (जावा ट्रीसेट) की जांच करने का एक तरीका खोज रहा हूं। मुझे पता है कि केडी-पेड़ का उपयोग करने का विकल्प हो सकता है, लेकिन मुझे नहीं पता कि इस तरह के केडी-पेड़ को कैसे बनाया जाए (आयताकारों के लिए यह 4 डी होना चाहिए, है ना?) और समस्या को हल करने के लिए कैसे करें (चौराहे , छेद)।

सॉर्टिंग वाई-अक्ष पर एक्स-अक्ष को प्राथमिकता देता है।

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

Answer 1

इस प्रकार की समस्या को हल करने के लिए बहुत से दृष्टिकोण हैं, प्रत्येक अलग-अलग पेशेवरों और विपक्ष के साथ। - अगर दो आयतों एक दूसरे को काटना, वहाँ एक ओवरलैप है

आयत जोड़ी चौराहे + क्षेत्र योग

आयतों की प्रत्येक जोड़ी में देखो: यहाँ उनमें से कुछ हैं। आयताकार क्षेत्रों को जोड़ें और जांच करें कि क्या राशि कैनवास क्षेत्र से मेल खाती है - यदि क्षेत्र मेल नहीं खाते हैं, तो एक अंतर है।

चित्रकारी

यह दृष्टिकोण आप का उल्लेख किया है: एक 2 डी सरणी अपने कैनवास के आयाम है कि पैदा करते हैं। फिर, आयताकारों पर पुनरावृत्त करें और उन्हें सरणी में "पेंट" करें।

इस दृष्टिकोण के लिए एक अनुकूलन संपीड़न समन्वय है। मान लीजिए कि आपके आयताकार हैं [(10,20), (15,25)] और [(7,3), (15, 25)]। आप अलग-अलग एक्स-निर्देशांक (7, 10, 15) देख सकते हैं और उन्हें (0, 1, 2), और विशिष्ट वाई-निर्देशांक (3, 20, 25) पर रीमेप कर सकते हैं और उन्हें रीमेप कर सकते हैं (0, 1, 2)। फिर, आपको आयतों के साथ छोड़ा जाता है [(1, 1), (2, 2)] और [(0,0), (2,2)], इसलिए आपको केवल 26x26 की बजाय पेंटिंग के लिए 3x3 सरणी चाहिए सरणी।

स्वीप लाइन एल्गोरिथ्म

एक लाइन बाएं से दाएं, 'दिलचस्प' बिंदुओं पर रोक, और ट्रैक जिनमें से क्षेत्रों पर कब्जा कर लिया जाता है रखने स्वीप।

2 डी रेंज पेड़

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

कौन सा चुनना है?

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

अधिक जानकारी

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

1. What is an Efficient algorithm to find Area of Overlapping Rectangles
2. http://compgeom.cs.uiuc.edu/~jeffe/open/klee.html
3. जे एल बेंटले, क्ली की आयत की समस्याओं के लिए एल्गोरिदम:

   यहाँ झाडू लाइन एल्गोरिथ्म पर संदर्भ के एक जोड़े हैं। अप्रकाशित नोट, कंप्यूटर विज्ञान विभाग, कार्नेगी मेलॉन विश्वविद्यालय, 1977

संदर्भ 3. आमतौर पर आयत संघ के लिए लाइन स्वीप एल्गोरिथ्म के मूल स्रोत के रूप में दिया जाता है, लेकिन मुझे लगता है कि मैं वास्तव में नहीं मिला स्वीकार करना होगा पेपर ऑनलाइन, शायद क्योंकि यह "अप्रकाशित" है ...