7
के लिए एक प्रतिनिधि का मतलब आंतरिक बिंदु ढूँढना मैं सी ++ में एक यात्रा विक्रेता समस्या को हल करने की कोशिश कर रहा हूं, लेकिन मुझे बिंदुओं के सेट के बजाय पॉयल्गन्स के सेट के बीच सबसे छोटी दूरी को पार करना होगा। ऐसा करने के लिए, मैं एक प्रतिनिधि "मतलब" इंटीरियर प्वाइंट द्वारा प्रत्येक बहुभुज का प्रतिनिधित्व करने की कोशिश कर रहा हूं ताकि मैं इन आंतरिक आंतरिक बिंदुओं पर एक टीएसपी कर सकूं।एक गैर-उत्तल बहुभुज
मेरे लिए एक उत्तल बहुभुज में एक औसत आंतरिक बिंदु ढूंढना आसान है क्योंकि यह केवल अंकगणितीय माध्य बिंदु है (और हमेशा एक उत्तल बहुभुज के लिए अंदर झूठ बोलता है), लेकिन यह दृष्टिकोण एक अवतल बहुभुज के लिए काम नहीं करेगा क्योंकि यह बहुभुज के लिए आंतरिक नहीं होगा।
इस पर सहायता करें? धन्यवाद। :-)
आप अपने बहुभुजों का प्रतिनिधित्व कैसे करते हैं? मैंने टैग 'एल्गोरिदम' जोड़ा है क्योंकि यह मूल रूप से एल्गोरिदमिक समस्या है। आप किस तरह की जटिलता का जोखिम उठा सकते हैं? –
'माध्य आंतरिक' बिंदु की आपकी परिभाषा क्या होगी? – Xyand
इसे एक आंतरिक बिंदु क्यों होना चाहिए? मैं कल्पना करता हूं कि आप या तो _approximation_ खोजना चाहते हैं, इस मामले में मुझे समझ में नहीं आता कि इंटीरियर क्यों सुरक्षित है। या सामान्य रूप से _shortest path_, इस मामले में मैं औसत प्रतिनिधियों का उपयोग नहीं करता, लेकिन बहुभुज से छुटकारा पाता हूं और समस्या को सीधे टीएसपी में बदल देता हूं। – Fiktik