अवास्ट वहां साथी प्रोग्रामर!आयताकार बहुभुज पर बूलियन परिचालन
मैं नीचे चित्र में दिखाया गया है जैसे अतिव्यापी दो आयतों है:
मैं निम्नलिखित समस्या है।
मैं बिंदु ABCDEF से मिलकर बहुभुज यह पता लगाने के लिए चाहते हैं।
वैकल्पिक क्रिसमस विवरण: लाल कुकी कटर ब्लैक कुकी का थोड़ा सा काट रहा है। मैं ब्लैक कुकी की गणना करना चाहता हूं।
प्रत्येक आयताकार 4 2 डी-कोर्सेस के साथ एक डेटा संरचना है।
इसे प्राप्त करने के लिए सबसे अच्छा एल्गोरिदम क्या है?
यह सामान्य 2 डी बहुभुज कतरन की एक विशेष मामला है। शुरू करने के लिए एक अच्छी जगह वीलर-एथर्टन एल्गोरिदम है। Wikipedia has a summary और links to the original paper। एल्गोरिदम उस डेटा संरचना से मेल खाता प्रतीत होता है जिसे आपने बहुत अच्छी तरह वर्णित किया है।
ध्यान दें कि यह संभव है कि आप इसमें एक छेद के साथ एक आयत के साथ समाप्त हो जाएंगे (यदि लाल रंग पूरी तरह से काले रंग के अंदर है) या यहां तक कि दो आयतों (जैसे कि लाल काला से लंबा और पतला है)। यदि आप निश्चित हैं कि काले रंग के अंदर लाल आयताकार का केवल एक कोने है तो समाधान बहुत आसान होना चाहिए।
लाल आयत काला पर कहीं भी हो सकता है। हालांकि, अगर यह ओवरलैप हो जाता है, तो मैं पूरी तरह से काले आयत को नजरअंदाज करता हूं, क्योंकि इसकी प्राथमिकता कम होती है। – Nailer
ऐसा लगता है कि मुझे वास्तव में क्या चाहिए था। – Nailer
http://en.wikipedia.org/wiki/Sutherland-Hodgman_clipping_algorithm भी बेहतर समझाया गया लगता है। इसके लिए सीजीएएल का उपयोग करके – Nailer
मैं यहाँ कुछ सामान मिला मैं उपयोग कर सकते हैं:
http://www.cgal.org/Manual/3.3/doc_html/cgal_manual/Boolean_set_operations_2/Chapter_main.html
मैं वास्तव में CGAL स्रोत डाउनलोड किया इससे पहले कि मैं भी इस प्रश्न पोस्ट, लेकिन मुझे लगता है कि मैं इस पर करीब ध्यान देंगे।
तोपों के साथ शिकार चिड़ियों की तरह है। 912 टुकड़े दृष्टिकोण में विभाजन के लिए –
निर्देशांक कितने सटीक हैं? यदि आयताकार काफी छोटे होते हैं, तो सबसे आसान तरीका केवल उन्हें कैनवास, काले आयताकार पर लाल रंग के बाद पेंट करना पड़ सकता है। कैनवास पर शेष काले पिक्सल बहुभुज हैं जो शेष हैं।
एक और तरीका आयताकार ग्रिड को आयत के सभी किनारों के आधार पर आयताकारों के समूह में विभाजित करना है (असंबद्ध आयतों की गिनती नहीं, आपके पास दो आयत होने पर 9 आयताकार उत्पन्न होते हैं)। फिर विशिष्ट आयतों में सदस्यता के लिए इन आयतों में से प्रत्येक के प्रतिनिधि बिंदु का परीक्षण करें, यह निर्धारित करने के लिए कि कौन से आयताकार हैं और कौन से हैं।
+1। यह सबसे सरल और सबसे तेज़ है .. –
बस एक स्पष्टीकरण नोट: "उन्हें कैनवास पर पेंट करें" दो तरीकों से किया जा सकता है: या तो ग्राफिक्स एपीआई से कैनवास पर, या एक साधारण 2-डी सरणी पर – Yuliy
क्या बहुभुज हमेशा दिखाए गए अनुसार अक्ष-संरेखित होते हैं? –