एल्गोरिदम एक त्रिभुज पट्टी के चरम को बहुभुज में परिवर्तित करने के लिए

Question

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

ओपन = संगत, देख http://en.wikipedia.org/wiki/Triangle_strip

उदाहरण: http://en.wikipedia.org/wiki/File:Triangle_Strip_Small.png मैं उत्पादन ABDFEC या ACEFDB

जरूरत इस पट्टी के लिए

Answer 1

अगर अपने आकार एक विशेष रूप से सरल संरचना है एक शॉर्टकट हो सकता है, लेकिन सामान्य रूप में मुझे लगता है कि आप निम्नलिखित

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

Answer 2

मेरा मानना ​​है कि निम्नलिखित काम करना चाहिए:

कोने की सूची पूरी करें। अपने बहुभुज में पहला बिंदु जोड़ें। ढेर पर दूसरी बिंदु पुश करें। बहुभुज में तीसरा बिंदु जोड़ें। स्टैक पर पॉइंटिंग पॉइंट्स के बीच वैकल्पिक रूप से जारी रखें और उन्हें पॉलीगॉन में जोड़कर जब तक आप सूची के अंत तक नहीं पहुंच जाते। जब आप सूची के अंत तक पहुंच जाते हैं, तो स्टैक के बिंदु पॉप करें और उन्हें बहुभुज में जोड़ें।

Answer 3

मैं अपने त्रिकोण पट्टी हमेशा एक ही तरीके (जो मेरा मानना ​​है कि ओपन के लिए सच है) से जुड़ा हुआ है मान लेंगे।

• "नीचे" कोने हमेशा दो अलग हैं: एक, सी, ई, ...
• "टॉप" कोने हमेशा से रहे हैं दो अलग: बी, डी, एफ, ...

"नीचे" सूची लें और "शीर्ष" सूची के विपरीत को संलग्न करें। (उदाहरण के लिए ACEFDB)

---

या, अधिक सीधे, पत्र के बजाय एक शून्य आधारित सूचकांक का उपयोग कर:

// do "bottom" 
for (i = 0; i < N; i += 2) 
    addVertex(i) 

// do "top" 
largestOddNumberLessThanN = N % 2 == 0 ? N - 1 : N - 2; 
for (i = largestOddNumberLessThanN; i >= 0; i -= 2) 
    addVertex(i)