पॉलीगॉन

Question

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

मैं आपको एक उदाहरण देता हूँ:

इस के साथ समस्या यह है कि कोशिकाओं के अंदर बहुभुज किनारों को पार और वहाँ कोशिका संरचना और बहुभुज आकार के बीच कोई दृश्य रिश्ता है।

क्या कोई इस समस्या से संपर्क करने के बारे में जानता है? क्या कोई एल्गोरिदम है जो पहले से ही ऐसा करता है या जो मैं प्राप्त करने की कोशिश कर रहा हूं उसके करीब आता है?

किसी भी प्रकार के इनपुट के लिए आपको बहुत बहुत धन्यवाद!

Answer 1

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

इस प्रकार के दृष्टिकोण के संदर्भ में त्रिकोण पैकेज here पर एक नज़र डालें। मेरे अनुभव में यह एक तेज़ और मजबूत लाइब्रेरी है, हालांकि यह cjava में लिखा गया है।

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

संपादित करें: ऐसा लगता है कि आप सामान्य लाइन सेगमेंट के लिए सीधे वोरोनोई आरेख भी बना सकते हैं, वीआरओएनआई लाइब्रेरी, here देखें। आपकी टिप्पणी को संबोधित करते हुए - मुझे यकीन नहीं है कि आप हमेशा एक समान वोरोनोई आरेख प्राप्त करने की उम्मीद कर सकते हैं जो सामान्य बहुभुज सीमा के अनुरूप भी है। मैं उम्मीद करता हूं कि बहुभुज सीमा का आकार सीमा वोरोनोई कोशिकाओं पर अधिकतम आयाम लगाएगा।

उम्मीद है कि इससे मदद मिलती है।

Answer 2

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

आप यह सुनिश्चित करना चाहते हैं कि आप युक्त बहुभुज (चाहे आपके द्वारा या किसी अन्य स्रोत से उत्पन्न हो) के साथ शुरू करें, काफी बराबर लंबाई के किनारों के साथ; एक भिन्न कारक यह और अधिक प्राकृतिक बना देगा। मैं शायद 10-20% के अंतर के लिए जाना होगा।

अब आपके पास अपने बराबर लंबाई के रेखा खंडों से घिरा हुआ बहुभुज बहुभुज है, तो आपके पास आधार है जो आपके वोरोनोई आरेख को उत्पन्न करना शुरू कर देता है।आपके कंटेनर पर प्रत्येक किनारे के लिए:

• किनारे सामान्य (उस सेगमेंट के केंद्र से पार्प लाइन जूटिंग) निर्धारित करें।
• किनारे को सामान्य रूप से एक स्लाइडिंग स्केल के रूप में उपयोग करें जिस पर एक नया वोरोनोई नोड केंद्र स्थापित किया जाए। किनारे से दूर की दूरी को आप अपने औसत वोरोनोई सेल "व्यास" के अनुसार निर्धारित करेंगे, यदि वे सभी मंडलियों के रूप में लिया गया था। आपके उदाहरण में ऐसा लगता है कि शायद 30 पिक्सेल (या जो भी आपकी दुनिया इकाइयों में बराबर होगा)। दोबारा, आपको इसके लिए एक भिन्न कारक लागू करना चाहिए ताकि प्रत्येक सेल सेंटर को इसके स्रोत किनारे से समतुल्य न रखा जाए।
• अपने नए केंद्र के लिए वोरोनोई सेल उत्पन्न करें।
• अपनी वोरोनोई सेल स्रोत बिंदु को एक सूची में स्टोर करें।

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

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

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

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

Answer 3

देखो:

एक:

किर्कपैट्रिक, डेविड जी, 1979

यहाँ में लिखा द्वारा "निरंतर कंकाल की कुशल गणना" सार है ओ (एन एलएनजी) एल्गोरिदम को मनमानी एन-लाइन पॉलीगोनल आंकड़ों के कंकाल के निर्माण के लिए प्रस्तुत किया गया है। यह एल्गोरिदम सामान्यीकृत वोरोनोई आरेखों के निर्माण के लिए ओ (एन एलएनजी) एल्गोरिदम पर आधारित है (हमारा सामान्यीकरण लाइन खंडों के सेट द्वारा बिंदु सेट को प्रतिस्थापित करता है जो केवल अंतिम बिंदुओं पर छेड़छाड़ करने के लिए बाध्य है)। सामान्यीकृत वोरोनोई आरेख एल्गोरिदम दो मनमानी (मानक) वोरोनोई आरेखों के विलय के लिए एक रैखिक समय एल्गोरिदम कार्यरत है।

"रेखा खंडों की सेट अंत अंक पर केवल एक दूसरे को काटना करने के लिए विवश किया जाता है" अवतल बहुभुज आप का वर्णन है।