सच सरल बहुभुज या बहुभुज

Question

पर कमजोर-सरल-बहुभुज विभाजित करें मैं कमजोर-सरल बहुभुज को सरल बहुभुज में विभाजित करना चाहता हूं।

पृष्ठभूमि

उपयोग के मामले बहुभुज कि सरलीकृत कर रहे हैं (Unioned) Javascript Clipper का उपयोग कर सरल करने के लिए है। जावास्क्रिप्ट क्लिपर के साथ-साथ original Clipper'sSimplifyPolygon() फ़ंक्शन स्वयं-छेड़छाड़ को हटा देता है और सामान्य किनारों को जोड़ता है, लेकिन यह वास्तविक सरल बहुभुज उत्पन्न नहीं कर सकता है। आउटपुट का उपयोग तीन.जेएस में किया जाता है, जिसमें TriangulateShapes() है जो बहुभुज को सरल होने की आवश्यकता है। Three.js बहुभुज संरचनाओं को स्वीकार करता है जिनमें एक समोच्च और शून्य या एकाधिक छेद होते हैं।

इनपुट, कमजोर-सरल बहुभुज

दुर्बलता-सरल बहुभुज अनुक्रमिक-डुप्लिकेट-कोने (सच डुप्लिकेट अंक), और न ही छेद (द्वीप) और न ही स्वयं चौराहों (अन्य किनारे पर बढ़त को पार) नहीं हो सकता, लेकिन गैर-अनुक्रमिक-बहु-चरणीय हो सकते हैं (शिखर जिनके पास बिल्कुल समान समन्वय है लेकिन अनुक्रमिक नहीं है)। इनपुट बहुभुज में या तो सीडब्ल्यू या सीसीडब्ल्यू घुमावदार आदेश हो सकता है, जिसका अर्थ है कि सीडब्ल्यू इनपुट बाहरी बहुभुज है और सीसीडब्ल्यू एक छेद है। इनपुट या तो सीडब्ल्यू या सीसीडब्ल्यू बहुभुज है। अंक गिने जा रहे हैं

और यहाँ है, जहां आप:

इनपुट बहुभुज अंक उदा .:

 

// This is a true example of weakly-simple polygon: 

var input = [{"X":270,"Y":520},{"X":130,"Y":490},{"X":210,"Y":250},{"X":60,"Y":170},{"X":130,"Y":490},{"X":20,"Y":410},{"X":60,"Y":300},{"X":60,"Y":20},{"X":780,"Y":40}, {"X":680,"Y":180},{"X":460,"Y":130},{"X":210,"Y":250},{"X":320,"Y":100},{"X":220,"Y":80}, {"X":210,"Y":250},{"X":520,"Y":250},{"X":680,"Y":180},{"X":770,"Y":480},{"X":540,"Y":470}, {"X":520,"Y":250},{"X":380,"Y":280},{"X":430,"Y":390},{"X":540,"Y":470},{"X":270,"Y":520},{"X":330,"Y":350},{"X":210,"Y":250}]; 

यह एक छवि के रूप में ऊपर input बहुभुज है की एक सरणी है आसानी से देख सकते हैं कि कौन से बिंदु डुप्लिकेट हैं:

जैसा कि आप देख, ऊपर बहुभुज, कई मायनों में बांटा जा सकता है जैसे .:
- पांच बाहरी बहुभुज एक के बाद एक छेद है, जिनमें से

आउटपुट, के रूप में सरल बहुभुज - पाँच छेद के साथ एक बाहरी पॉलीगॉन एक exPolygon संरचना

सरल बहुभुज एक बहुभुज है जिसमें कोई आत्म-चौराहे नहीं है, कोई डुप्लिकेट निर्देशांक नहीं है कि वे अनुक्रमिक या अनुक्रमिक थे, कोई छेद नहीं था। आउटपुट के साधारण बहुभुज में सीडब्ल्यू या सीसीडब्ल्यू घुमावदार आदेश हो सकता है। सीडब्ल्यू का मतलब बाहरी और सीसीडब्ल्यू छेद है।

आउटपुट में (और कई बार होगा) छेद हो सकता है, लेकिन कुछ मामलों में आउटपुट में कोई छेद नहीं होता है। आउटपुट में कम से कम एक बाहरी बहुभुज होता है, लेकिन कई बाहरी बहुभुज भी हो सकते हैं जिनमें शून्य या अधिक छेद होते हैं।

आउटपुट exPolygon ऑब्जेक्ट्स की एक सरणी होनी चाहिए जिसमें गुण "बाहरी" और "छेद" हों। "बाहरी" बिंदु वस्तुओं की एक सरणी है, "छेद" बिंदु वस्तुओं के सरणी की एक सरणी है। यदि "छेद" आबादी है, तो इसमें छेद exPolygon ऑब्जेक्ट में "बाहरी" बहुभुज के छेद होना चाहिए।

उत्पादन का उदाहरण:

 

// This is an example of output, but the points are random: 

[ { "outer": [{"X":54,"Y":4},{"X":2,"Y":50},{"X":30,"Y":5},{"X":10,"Y":50}], 
    "holes": [ [{"X":0,"Y":8},{"X":60,"Y":13},{"X":21,"Y":2},{"X":3,"Y":1}], 
       [{"X":21,"Y":2},{"X":50,"Y":2},{"X":6,"Y":1}] ] }, 
    { "outer": [{"X":54,"Y":4},{"X":2,"Y":50},{"X":30,"Y":5},{"X":10,"Y":50}], 
    "holes": [ [{"X":0,"Y":8},{"X":60,"Y":13},{"X":21,"Y":2},{"X":3,"Y":1}], 
       [{"X":21,"Y":2},{"X":50,"Y":2},{"X":6,"Y":1}] ] }, 
    { "outer": [{"X":54,"Y":4},{"X":2,"Y":50},{"X":30,"Y":5},{"X":10,"Y":50}], 
    "holes": [] } 
]; 

आउटपुट के "बाहरी" बहुभुज सीडब्ल्यू, और "छेद" हैं सीसीडब्ल्यू हैं।

बहुभुज में बिंदुओं की संख्या, exPolygons वस्तुओं की गिनती और छेद की गिनती की कोई सीमा नहीं है।

विभाजन

यहाँ का उदाहरण इनपुट बहुभुज का एक उदाहरण है::

यहाँ है

यहाँ कमजोर सरल बहुभुज के अन्य उदाहरण हैं इसे कैसे विभाजित किया जा सकता है:

कुछ अन्य बहुभुज आधार पर ouput के कई संभावित विकल्पों जहां छद्म डुप्लिकेट-अंक हैं हो सकता है।

---

मेरा प्रश्न

कैसे बहुभुज इस तरह से और वांछित उत्पादन संरचना हासिल विभाजित किया जा सकता? मैं पूरा कोड नहीं पूछ रहा हूं (लेकिन यदि आपके पास कुछ खाली समय है और यह दिखाना चाहता है कि यह संभव है)। संभावित एल्गोरिदम के विचार भी स्वागत है।

---

मैंने घंटों के समाधान की खोज की है और एक एल्गोरिदम खोजने की कोशिश की है।

यदि आप समाधान का प्रयास करना चाहते हैं, तो मेरे पास एक कोड है जिसे मैंने डुप्लीकेट खोजने के लिए उपयोग किया है: http://jsbin.com/unuyev/7/edit। यह एसवीजी में बहुभुज दिखाता है और अंक को लाल मंडल और प्रत्येक बिंदु की सरणी अनुक्रमणिका के रूप में दिखाता है (बटन "जेएस के साथ चलाएं" दबाकर)।

यहाँ ही है, लेकिन 12 उदाहरण बहुभुज (जावास्क्रिप्ट विंडो में परिवर्तन pindex बहुभुज को बदलने के लिए) के साथ: http://jsbin.com/unuyev/4/edit

---

संपादित करें: Javascript Clipper 6 अब उपलब्ध है और StrictlySimple के लिए समर्थन नहीं है। लेकिन दस्तावेज़ीकरण के मुताबिक "वर्तमान में कोई गारंटी नहीं है कि 'सरलीकरण' के बाद बहुभुज सख्ती से सरल होंगे क्योंकि अभी भी प्रगति पर एक काम है"। मैंने StrictlySimple का परीक्षण किया है और यह कुछ मामलों में विफल रहता है: Orientation problems और lack of rotation invariance। हमें आशा है कि ये जल्द ही तय हो जाएंगे और StrictlySimple अपेक्षित कार्य करता है।

---

Answer 1

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

अगर मुझे समस्या का समाधान करना पड़ा, तो यह वह दृष्टिकोण है जो मैं लेता हूं।आप निम्नलिखित संसाधनों को देख सकते हैं:

• Articulation vertices from the Algorithm Design Manual - यह आपकी सबसे अच्छी शर्त है। वह सरल शब्दों में एल्गोरिदम बताता है और आपको सी कोड भी देता है जिसे आप आसानी से जावास्क्रिप्ट में अनुवाद कर सकते हैं। अगर मुझे एक एल्गोरिदम लिखना शुरू करना पड़ा, तो यह वह जगह है जहां मैं शुरू करूंगा।
• Biconnected component
• Detection of Articulation Points ("अभिव्यक्ति" के लिए खोज)

अद्यतन

मैं कोशिश करते हैं और आप सही में आप बात करने के लिए समस्या और समाधान की एक संक्षिप्त सिंहावलोकन दे देंगे दिशा। ग्राफ का उपयोग करके इस एल्गोरिदम का कार्यान्वयन आवश्यक रूप से ग्राफ़-एल्गोरिदम शब्दावली में जाएगा, इसलिए यदि आप ग्राफ से परिचित नहीं हैं, तो आप उन पर पढ़ना चाहेंगे।

आपके मामले में ब्रूट-फोर्स दृष्टिकोण ग्राफ को पार करना होगा, अस्थायी रूप से प्रत्येक vetex को हटा देगा और फिर संशोधित ग्राफ पर डीएफएस/बीएफएस ट्रैवर्सल करते समय ग्राफ़ कनेक्ट होगा या नहीं। यह बहुत ही कुशल नहीं है और O(n(m + n)) वर्गबद्ध समय में चलाएगा। लेकिन एक रैखिक-समय एल्गोरिदम है जो डीएफएस ट्रैवर्सल से बने परिणामी डीएफएस पेड़ के किनारों को वर्गीकृत करने पर आधारित है।

एक डीएफएस पेड़ में जिसमें कोई बैक-एज नहीं होता है (पेड़ में "निचले" नोड को नोड "उच्च" से जोड़ने वाले किनारों [मानते हैं कि "उच्च" नोड रूट के करीब हैं]) पत्ता नोड्स articulation नोड्स नहीं हैं, क्योंकि उनमें से किसी एक को हटाने से अब भी ग्राफ से जुड़े रहेंगे। हालांकि, किसी भी आंतरिक नोड को हटाने से रूट से इसका पालन करने वाले किसी भी नोड्स को डिस्कनेक्ट कर दिया जाएगा।

पेड़ की जड़ को हटाने पर निर्भर करता है कि इसमें एक या अधिक बच्चे हैं या नहीं। यदि इसमें केवल एक बच्चा है, तो यह पत्तियां कम या कम है और इसलिए इसे हटाने से कोई प्रभाव नहीं पड़ेगा। हालांकि, एक रूट नोड को हटाकर जिसमें एक से अधिक बच्चे ग्राफ को डिस्कनेक्ट करेंगे।

लेकिन एक सामान्य ग्राफ में, आप बैक-एज कर सकते हैं और इसलिए बीच में से किसी भी नोड को हटाने से ग्राफ को डिस्कनेक्ट नहीं किया जाएगा। तो आर्टिक्यूलेशन शिखर का पता लगाना यह पता लगाने के लिए उबाल जाता है कि पेड़ के कौन से वर्ग पूर्वजों द्वारा पूर्वजों के नोड्स से जुड़े होते हैं (यानी, एक कशेरुक के "पहुंचने योग्य पूर्वजों" को ढूंढना)।

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

उम्मीद है कि यह आपको प्रारंभ करने में मदद करता है!