छेद के साथ बहुभुज का प्रतिनिधित्व कैसे करें?

Question

आमतौर पर वेक्टरों (2 * 1 या 1 * 2 मैट्रिस) में सीडब्ल्यू या सीसीडब्ल्यू सॉर्ट किए गए उनके शिखर के साथ बहुभुज के साथ काम करना लोकप्रिय होता है। हालांकि, वेक्टरों में छेद के साथ बहुभुज कैसे कहें?

मैं इन बहुभुजों पर विभिन्न प्रक्रियाओं को लागू करने जा रहा हूं, इसलिए मैं प्रतिनिधित्व करने का एक तरीका चाहता हूं जिसके साथ मैं आसानी से या कुशलता से काम कर सकता हूं। (यानी मेरे एल्गोरिदम को कम करने के लिए मेरे प्रोग्राम में उस तरह के बहुभुज को कैसे बताना है ?)

बहुभुज 2 डी हैं और मैं MATLAB में प्रोग्रामिंग कर रहा हूं।

संपादित करें 1: मैं इन बहुभुजों के साथ visibility graph की गणना करने जा रहा हूं (छेद के साथ या बिना)।

Answer 1

दूसरों के रूप में उल्लेख किया है, छेद के साथ एक बहुभुज एक बाहरी सीमा के रूप में प्रतिनिधित्व किया जा सकता है, के साथ साथ शून्य या अधिक आंतरिक सीमाओं, जो सभी के परस्पर nonoverlapping हैं *। आप अशून्य winding number का उपयोग करते हैं यह निर्धारित करने के अंदर/बाहर, अपने इंटरियो निर्दिष्ट करना सुनिश्चित करें बाहरी सीमाओं के विपरीत विपरीत दिशा में आर सीमाएं (बाहरी के लिए बाहरी और दक्षिणावर्त के लिए दक्षिणावर्त, या इसके विपरीत) ताकि समोच्च इंटीग्रल छेद के अंदर शून्य हो।

एफवाईआई, ओपनजीआईएस सरल सुविधाओं विशिष्टता (PDF) में परिभाषा/प्रतिनिधित्व की तरह औपचारिक रूप दिया गया है।

जहाँ तक प्रतिनिधित्व के रूप में:

मैं शायद सेल में कश्मीर NX2 मैट्रिक्स, जहां सेल सरणी में पहला तत्व बाहरी सीमा नहीं है, और शेष तत्वों की एक सेल सरणी (यदि हो तो) होगा सरणी आंतरिक सीमाएं हैं। मैं एक सेल सरणी का उपयोग करता हूं क्योंकि प्रत्येक सीमा पर अंक की संख्या समान नहीं हो सकती है।

* nonoverlapping = अलग-अलग बिंदुओं को छोड़कर, उदा। एक वर्ग के अंदर एक हीरे:

Answer 2

एक बहुभुज, साथ ही पॉलीगोनल छेद की एक सूची। बस सुनिश्चित करें कि विभिन्न बहुभुज अंतर नहीं करते हैं।

आप इस चीज़ के साथ क्या करने की योजना बना रहे हैं?

Answer 3

ऐसा लगता है जैसे प्रत्येक छेद बहुभुज के अंदर सिर्फ एक बहुभुज है। शायद आप बाहरी पॉलीगॉन के लिए वर्णित एक वेक्टर स्टोर कर सकते हैं, फिर छेद के लिए अधिक बहुभुज वैक्टरों का वेक्टर।

Answer 4

"दृश्यता ग्राफ" के तहत आपका क्या मतलब है?

दो "पूर्ण" बहुभुज, दो राज्य संभव है, या तो +1 या -1।

आप एक छेद का प्रतिनिधित्व कर रहे हैं, तो आप राज्य -1, जो एक छेद का प्रतिनिधित्व करता है, राज्य 0.
में जिसके परिणामस्वरूप आप अतिव्यापी बहुभुज रखी है, तो साथ राज्य +1 के साथ एक और एक मिल गया है, तो आप ' परिणामस्वरूप राज्य> 1 के साथ समाप्त हो जाएगा। फिर आप एक नए बहुभुज की सीमाओं की गणना कर सकते हैं।
यदि आपके पास छेद वाले छेद वाले दो बहुभुज हैं, तो पहले एक नए बहुभुज की स्थिति की गणना करें जिसमें दो पुराने लोगों की बाहरी सीमाएं होती हैं, फिर छेद से निपटती हैं।

वैसे भी, ... मुझे लगता है कि आपको सामान्य सिद्धांत मिलता है।

मैटलैब में इसे कैसे करना है, मुझे पता नहीं है, मैंने इसे केवल मामूली रूप से उपयोग किया है, और यहां तक ​​कि बहुत सरल चीजों के लिए भी।

Answer 5

आप छेद के बिना दो आकारों में एक छेद के साथ बहुभुज तोड़ सकते हैं। जब आप एक जटिल विमान में समोच्च एकीकरण कर रहे हैं, तो आप बहुभुज के एक किनारे से "कट" बना सकते हैं जो आपको छेद के किनारे लाता है; छेद के पीछे एक तरफ एकीकृत करें; फिर दूसरे बहुभुज के लिए दूसरी तरफ घूमते हैं। आप प्रत्येक कट के साथ दो पथ इंटीग्रल के साथ समाप्त होते हैं जो एक-दूसरे को रद्द करते हैं।

"दृश्यता ग्राफ" - क्या यह छायांकन के साथ विकिरण दृश्य कारक गणना के लिए है? या एक रे-ट्रेसिंग ग्राफिक्स एल्गोरिदम?

Answer 6

संभवतः आप एक वृक्ष संरचना चाहते हैं यदि आप इसे जितना संभव हो उतना सामान्य होना चाहते हैं (यानी पॉलीगोनल छेद वाले बहुभुज जिनके अंदर बहुभुज हैं, उनके अंदर छेद हैं ...)। Matlab पेड़ संरचनाओं का कुशलतापूर्वक प्रतिनिधित्व करने में वास्तव में महान नहीं है, लेकिन यहां एक विचार है ...

बहुभुजों की एक संरचना-सरणी है।

प्रत्येक बहुभुज दो क्षेत्रों, 'कोनों' और 'बच्चों' के साथ एक संरचना है।

'कोनों' फ़ील्ड में कोनों के (x, y) निर्देशांक का एक मैट्रिक्स होता है, जिसे "डेटा {polyIdx} .corners (:, cornerIdx)" के रूप में एक्सेस किया जाता है।

'बच्चों का क्षेत्र बहुभुज का एक संरचना-सरणी है।

यहाँ एक त्रिकोण फर्जी बच्चों कि छेद कर रहे हैं के साथ बनाने के लिए कुछ कोड का एक उदाहरण है (वे वास्तव में वैध हालांकि, क्योंकि वे संभावना ओवरलैप नहीं कर रहे हैं:

polygon = struct; 
npoints = 3; 
polygon.corners = rand(2,npoints); 
polygon.children = struct; 
nchildren = 5; 
for c=1:nchildren 
    polygon.children(c).corners = rand(2,npoints); 
    polygon.children(c).children = struct; 
end 

आप रिकर्सिवली बच्चों को परिभाषित करने के लिए जारी कर सकता है कि वैकल्पिक । छेद बनाने और उन्हें भरने के बीच