दिलचस्प पोस्ट
आधुनिक ब्राउज़रों, एंड्रॉइड और आईओएस के लिए मुझे किस प्रकार की फ़ॉन्ट फाइलों की आवश्यकता है? छवि पर टेक्स्ट कैसे दिखाना है जब घूम रहा है? एंड्रॉइड – क्या नेविगेशन ड्रॉवर दाएं हाथ से संभव है? क्षैतिज अज्ञात चौड़ाई की एक unordered सूची केंद्र कैसे करें? एक मानक :: नक्शा जो प्रविष्टि के आदेश का ट्रैक रखता है? सी ++: एरे के लिए कन्स्ट्रक्टर आरंभक यह तारीख प्रारूप क्या है? 2011-08-12T20: 17: 46.384Z URL पैरामीटर बदलें क्या कोई अद्वितीय एंड्रॉइड डिवाइस आईडी है? मेरा आईफोन ऐप अपने स्वयं के संस्करण का नंबर कैसे देख सकता है? jQuery के यूआई संवाद – बंद आइकन याद आ रही है पढ़ने के लिए पायथन रीडलाइन () उपयोग और कुशल अभ्यास मैं डिग्री से रेडियन को कैसे परिवर्तित कर सकता हूं? मैं मनमाना pthread_t से एक धागा आईडी कैसे प्राप्त करूं? निश्चित हेडर और एक निश्चित कॉलम के साथ HTML तालिका?

मैं जटिल बहुभुजों को कैसे जोड़ूं?

दो बहुभुजों को देखते हुए:

POLYGON((1 0, 1 8, 6 4, 1 0)) POLYGON((4 1, 3 5, 4 9, 9 5, 4 1),(4 5, 5 7, 6 7, 4 4, 4 5)) 

मैं यूनियन (संयुक्त बहुभुज) की गणना कैसे कर सकता हूं?

वैकल्पिक पाठ http://img.hiwab.com/math/STUnion_2.png

दवे का उदाहरण संघ का उत्पादन करने के लिए SQL सर्वर का उपयोग करता है, लेकिन मुझे कोड में ऐसा पूरा करने की आवश्यकता है। मैं एक गणितीय सूत्र या कोड उदाहरण के लिए देख रहा हूँ जो वास्तविक गणित को उजागर करता है। मैं उन मैप्स का उत्पादन करने की कोशिश कर रहा हूं जो देशों को गतिशील रूप से क्षेत्रों में जोड़ती है। मैंने यहां एक संबंधित प्रश्न पूछा: भौगोलिक आकृतियाँ समूह बनाना

वेब के समाधान से एकत्रित समाधान "मैं जटिल बहुभुजों को कैसे जोड़ूं?"

यह एक बहुत अच्छा सवाल है। मैंने कुछ समय पहले सी # पर एक ही एल्गोरिदम लागू किया था। एल्गोरिथ्म दो बहुभुजों (यानी छेद के बिना एक संघ बनाता है) का एक आम रूप है। यही पर है।


लक्ष्य

चरण 1. ग्राफ बनाएँ जो बहुभुजों का वर्णन करता है।

इनपुट: पहले बहुभुज (एन पॉइंट्स), दूसरा बहुभुज (एम पॉइंट्स)। आउटपुट: ग्राफ वर्टेक्स – चौराइण बिंदु के बहुभुज बिंदु।

हमें चौराहों का पता लगाना चाहिए दोनों बहुभुजों [ओ (एनएम)] में सभी बहुभुज पक्षों के माध्यम से फिराना और किसी भी चौराहों को खोजने

  • यदि कोई प्रतिच्छेदन नहीं मिला है, तो बस कोने में जोड़ दें और उन्हें किनारे पर कनेक्ट करें

  • यदि कोई चौराहियां मिलती हैं, तो उन्हें अपने शुरुआती बिंदु तक क्रमशः क्रमबद्ध कर दें, सभी अनुक्रम (प्रारंभ, समाप्ति और चौराहों) को जोड़ दें और उन्हें किनारे पर पहले से क्रमबद्ध क्रम में जोड़ दें ग्राफ़

चरण 2. निर्माण ग्राफ़ की जांच करें

यदि ग्राफ़ का निर्माण किया गया था, तो हमें कोई प्रतिच्छेदन अंक नहीं मिला, तो हम निम्नलिखित शर्तों में से एक हैं:

  1. बहुभुज 1 में बहुभुज 2 – रिटर्न पॉलीगॉन 1 होता है
  2. बहुभुज 2 में बहुभुज 1 – वापसी बहुभुज 2 होता है
  3. बहुभुज 1 और बहुभुज 2 अंतर नहीं करते। बहुभुज 1 और बहुभुज 2 लौटें।

चरण 3. बायां-नीचे शीर्ष को खोजें।

न्यूनतम एक्स और वाई निर्देशांक (मिनक्स, मिने) का पता लगाएं फिर न्यूनतम (minx, miny) और बहुभुज के अंक के बीच न्यूनतम दूरी ढूंढें। यह बिंदु बाएं-नीचे बिंदु होगा

वाम-नीचे बिंदु

चरण 4. आम समोच्च बनाएं

हम बाईं तरफ से ग्राफ को पार करना शुरू करते हैं और तब तक जारी रहती हैं जब तक हम उसमें वापस नहीं आ जाते। शुरूआत में हम सभी किनारों को अनभिज्ञ रूप से चिह्नित करते हैं। प्रत्येक पुनरावृत्ति पर आपको अगले बिंदु का चयन करना चाहिए और उसे दौरा किया जाना चाहिए।

अगले बिंदु का चयन करने के लिए, अधिकतम आंतरिक कोण के साथ एक किनारे को दक्षिणावर्त दिशा में चुनें।

मैं दो वैक्टरों की गणना करता हूं: वेक्टर 1 वर्तमान किनारे के लिए और प्रत्येक अगली उजागर किनारे के लिए वेक्टर 2 (जैसा कि चित्र में प्रस्तुत किया गया है)।

वैक्टर के लिए मैं गणना करता हूँ:

  1. स्केलर उत्पाद (डॉट उत्पाद) यह वैक्टर के बीच के कोण से संबंधित मान देता है
  2. वेक्टर उत्पाद (पार उत्पाद) यह एक नया सदिश देता है यदि इस वेक्टर के z- समन्वय सकारात्मक है, तो स्केलर उत्पाद मुझे सही दिशा को दिशा में दिशा में देता है। अन्य (z- समन्वय ऋणात्मक है), मैं वैक्टर के बीच के कोण को 360-कोण के रूप में स्केलर उत्पाद से मिलता है।

नतीजतन, मैं अधिकतम कोण के साथ एक किनारे (और अगले शीर्ष के अनुरूप) मिलता है

मैं प्रत्येक पारित परिणाम को सूची में जोड़ता हूं। परिणाम सूची यूनियन बहुभुज है वैक्टर

टिप्पणियों

  1. यह एल्गोरिथ्म हमें बहुभुजों के मर्ज को मर्ज करने की अनुमति देता है – बहुभुज के जोड़े के साथ iteratively लागू करने के लिए।
  2. यदि आपके पास एक पथ है जिसमें कई बेजियर घटता और रेखाएं हैं, तो आपको इस पथ को पहले समतल करना चाहिए।

आपको यह निर्धारित करने की आवश्यकता है कि कौन-से बिंदु अंतर्निहित हैं । इन बिंदुओं को हटाने के बाद, आप दूसरे के "बाहर" बिंदुओं का एक समूह सम्मिलित कर सकते हैं आपका सम्मिलन बिंदु (उदाहरण के लिए जहां दाईं ओर चित्र में तीर है) आप जहां इनपुट सेट से अंक निकालते हैं

यह एक चुनौतीपूर्ण लेकिन अच्छी तरह से समझने वाला विषय है, जिसे अक्सर "बहुभुज पर नियमित बूलियन ऑपरेशन" नाम से जाना जाता है। आप इस MathOverflow उत्तर को देख सकते हैं, जिसमें नीचे दी गई संख्या शामिल है ( एलन मर्टा की क्लिपिंग लाइब्रेरी से ), गुलाबी संघ के ओपी के साथ :


BooleanOps


अच्छा प्रश्न! मैंने इससे पहले कभी भी प्रयास नहीं किया है, लेकिन मैं इस पर अब एक दरार ले जाऊंगा।

सबसे पहले: आपको यह पता होना चाहिए कि ये दो आकार ओवरलैप करते हैं। ऐसा करने के लिए, आप बहुभुज ए में हर किनारे पर गौर कर सकते हैं और देखें कि यह बहुभुज बी में कहाँ से छेदता है और बढ़ता है। इस उदाहरण में, प्रतिच्छेदन के दो बिंदु होने चाहिए।

उसके बाद: संघ आकार बनाएँ। आप ए और बी में सभी कोने, और चौराहे के अंक भी ले सकते हैं, और फिर अंतिम आकार से समाहित शिरोबिंदु को निकाल सकते हैं। इन बिंदुओं को ढूंढने के लिए, ऐसा लगता है कि आप ए के किसी भी शीर्ष को बी के अंदर और ए के किसी भी ऊपरी भाग में मिल सकते हैं।

जीपीसी प्रयास करें

बीएसपी पेड़ों का उपयोग करते हुए मैंने जो भी हल देखा है, वह यहां वर्णित है ।

असल में, यह बहुभुज के किनारों के एक संघ के संदर्भ में चौराहे का वर्णन करता है जो बहुभुज बी (आंशिक किनारों सहित, और बसपा पेड़ का उपयोग करके) के अंदर है। फिर, आप / बी को ~ (~ / बी ) के रूप में परिभाषित कर सकते हैं, जहां बहुभुज की घुमाव को उल्लेखित करने के लिए, / यूनियन को इंगित करता है और / \ चौराहे को इंगित करता है।

जब समूह के देशों में, मैं आशा करता हूं कि कोई ओवरलैप नहीं होगा – आप एक भद्दा एल्गोरिथ्म ले सकते हैं जो साझा शिरोमणि के लिए दिखता है – एक बहुभुज पर अंक के माध्यम से एक साधारण दृश्य को पुनरावृत्त करना होगा, यह देखें कि क्या यह आपके किसी अन्य बहुभुज पर है , और एक ही अगले या पिछले बिंदु साझा करने के लिए यह देखने के लिए कि क्या कोई मैच है। फिर अपने संघ बनाने के लिए साझा वर्टेक्स को निकाल दें

मुझे आज भी यही समस्या हल करने की आवश्यकता है और इस लिबिल के साथ समाधान मिला: http://www.cs.man.ac.uk/~toby/alan/software/

इसमें जावा, ओबजे-सी, सी #, लुआ, अजगर और अधिक सहित यहां कई भाषाओं के कार्यान्वयन हैं।