पॉलीगॉन के अंक छंटनी

Question

मेरे पास एक उत्तल बहुभुज एबीसीडीई है ... (इसमें अंक की संख्या हो सकती है)। मुझे अपने सभी कशेरुकाओं को क्रमबद्ध करने की आवश्यकता है ताकि किनारों में से कोई भी अंतर न हो।
उदाहरण:

A _____ B 
    \ /
    \/
    X 
/\ 
    /___\ 
C  D 

एबीसीडी क्रम में बहुभुज अन्तर्विभाजक गया है किनारों। तथापि ABDC क्रम में:

A _____ B 
    | | 
    | | 
    | | 
    | | 
    |___| 
C  D 

किनारों में से कोई भी एक दूसरे को काटना तो ABDC उम्मीद उत्पादन होता है।

मैं यह कैसे कर सकता हूं?

Answer 1

अपने अंक मानते हुए अपने बहुभुज के उत्तल पतवार पर सभी, आप उपयोग कर सकते हैं निम्नलिखित हैं:

1. न्यूनतम और अधिकतम एक्स मूल्य के साथ दो चरम बिन्दु चुनें, (उन्हें फोन एक्स _मिनट और एक्स _{अधिकतम}) और उनके बीच की रेखा खींचें। इस मामले में जहां आपके पास चरम पर एक ही एक्स मान के साथ कई बिंदु हैं, अधिकतम वाई मान के साथ न्यूनतम वाई मान और एक्स _{अधिकतम} के साथ एक्स _मिनट चुनें।
2. स्प्लिट दो उप सूचियों जहां रेखा से नीचे अंक के सभी को जोड़ने एक्स _मिनट और एक्स _{अधिकतम} में अंकों की सूची एक सूची में हैं और है कि रेखा के ऊपर उन सभी किसी अन्य रूप में कर रहे हैं। पहली सूची में एक्स _मिनट और एक्स _{अधिकतम} दूसरे में शामिल करें।
3. एक्स मान के आरोही क्रम में पहली सूची क्रमबद्ध करें। यदि आपके पास एक ही एक्स मान के साथ एकाधिक अंक हैं, तो उन्हें आरोही Y मान में क्रमबद्ध करें। यह केवल एक्स एक्सअधिकतम के समान एक्स घटक वाले बिंदुओं के लिए होना चाहिए क्योंकि बहुभुज उत्तल है।
4. एक्स मान के अवरोही क्रम में दूसरी सूची को सॉर्ट करें। दोबारा, एक ही एक्स मान वाले एकाधिक बिंदुओं की स्थिति में अवरोही वाई मान में क्रमबद्ध करें (जो केवल एक्स घटक एक्स _मिनट के साथ बिंदुओं के लिए होना चाहिए।
5. दोनों सूचियों को एक साथ जोड़ना (इससे कोई फर्क नहीं पड़ता कि पहले कौन सा है ।)

Answer 2

बहुभुज पर दो बिंदुओं का चयन करें। लाइन के मध्य बिंदु उस बहुभुज के भीतर निहित होगा। उस बिंदु को एम

फिर, एम (एक्स अक्ष के साथ) के कोण के आधार पर बिंदुओं को क्रमबद्ध करें, उस क्रम में एम Iterating से दूरी पर आधारित degeneracy तोड़ने से यह सुनिश्चित करता है कि कोई भी दो किनारों का अंतर नहीं होगा।