परिचय

इस साल की गर्मियों मैं Västerås में एक प्रौद्योगिकी खंड पर काम कर रहा हूँ. मैं एक ही कंपनी में और लगभग एक ही कार्यालय में तीन सीधे गर्मियों के लिए काम किया है. बहुत तकनीकी है, मजेदार और चुनौतीपूर्ण काम है. एक कार्यालय में कई अन्य गर्मियों में नौकरी के विपरीत, मैं जहाँ मैं जिम्मेदारी है और सामान्य कार्यों के साथ काम करने के लिए मिल पाया है. विशेष रूप से, मैं विकासशील उपकरणों पर काम ज्यादातर MatLab, जीयूआई प्रोग्रामिंग और जावा का उपयोग कर संगणना को सरल. MATLAB की नई शैली वस्तु उन्मुख कोड और अधिक एक कुछ साल पहले की तुलना में स्पष्ट बनाता है.

समस्या

दूसरे दिन मैं एक छोटे से चुनौती का सामना करना पड़ा. यह है कि जटिल अंक का एक सेट है कि विमान में बिखरे हुए हैं encloses एक बहुभुज खोजने पर ध्यान केंद्रित सरलीकृत. सबसे पहले मैं समारोह है कि Matlab, जो बेशक बहुत ही अजीब था में इस करता है नहीं मिला. इसलिए मैं एक कस्टम एल्गोरिथ्म खोजने का फैसला किया. इस पोस्ट में मैं अपने एल्गोरिथ्म का वर्णन करेंगे.

आकृति 1. उत्तल खोल के उदाहरण हैं.

मेरे Alogritm

मैं मेरा होना 2 अंक का उपयोग कर एल्गोरिथ्म का वर्णन. के साथ शुरू करने के लिए, मैं आवास खोजने में कठिनाई की व्याख्या करेगा. बात यह है कि सभी बिंदुओं संरचना में unsorted हैं. यदि अंकों के एक केंद्र बिंदु के आसपास के आदेश दिए हैं, एक केंद्र से उनके आदेश और दूरी का उपयोग करने के लिए समस्या को हल कर सकते हैं. हालांकि, यह O (n लॉग (एन)) के कम से कम एक रैखिक छँटाई करने के लिए लेता है. मेरा एल्गोरिथ्म unsorted सूची में काम करता है और शायद भी अधिक समय होगा, क्योंकि मैं कोई सबूत नहीं निकाली गई है.

निश्चित रूप से विचार है x दिशा में मेरे बिंदु के साथ शुरू हो और फिर बात जिस पर कश्मीर मूल्य अधिकतम हो जाता है लगता है. बाहर आंकड़ा अर्थात्:

(k_i) अधिकतम = (y_min y_i) / (x_min x_i) मैं के लिए = [सभी आइटम यह आप p_2 बिंदु देता है.

कम y मूल्य X_min की तुलना में सभी बिंदुओं को हटाया जा सकता है. P_2 से छोटे एक्स मूल्य के साथ सभी बिंदुओं को भी आगे पढ़ने के लिए बाहर शासन किया जा सकता है.

k_2 तब बिंदु जो कम से कम खोजने के द्वारा पाया जाता है:

k_1 (y_1 y_i) / (x_1 x_i) मैं = [सभी बिंदुओं बाहर नहीं कर रहे हैं]

इसी तरह k_a आम तौर पर पाया:

मिनट (k_a-1 (y_a-1 - y_i) / (x_a-1 - x_i)) के लिए मैं = [सभी अंक शामिल नहीं हैं]

गणना बहुभुज के ऊपरी आधे के लिए किया जाता है जब तक आप बिंदु जो x दिशा में अधिकतम है. इसके बाद, बहुभुज के निचले आधे के लिए एक ही एल्गोरिथ्म.

चित्रा 2. उत्तल मामले के लिए एलगोरिदम.

निष्पादन

एल्गोरिथ्म के प्रदर्शन पर निर्भर करता है कि कितने अंक बहुभुज में खत्म होता है. मैं के रूप में कई linjärsök सूची है कि यह बहुभुज में इशारा करते हैं. इसका मतलब यह है कि जटिलता हे (एन खोज की संख्या *). इष्टतम बहुभुज में अंकों की संख्या के बीच 10 और 25 अपने मौका बिंदुओं पर निर्भर करता है. एल्गोरिथ्म इस तरह अपेक्षाकृत तेजी से है.

कोड

कोड सार्वजनिक नहीं है.

Matlab के समाधान - उत्तल पतवार

मेरा एल्गोरिथ्म एक Matlab समारोह के रूप में एक ही बात करता convhull . उत्तल पतवार इस प्रकार एक संलग्न बहुभुज या एक उत्तल शरीर के लिए अंग्रेजी शब्द है. एक और अच्छा संसाधन है http://en.wikipedia.org/wiki/Convex_hull_algorithms समझा है कि सैद्धांतिक कम से कम समय के लिए एक उत्तल खोल के मिल आदेश हे (n लॉग (एन)) है.