डगलस-पीकर एल्गोरिथम

प्रस्तावना

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

विवरण

एल्गोरिथ्म प्रारंभिक पॉलीलाइन और अधिकतम दूरी (,) निर्धारित करता है, जो मूल और सरलीकृत पॉलीलाइन के बीच हो सकता है (अर्थात, मूल के बिंदुओं से अधिकतम दूरी परिणाम पॉलीलाइन के निकटतम भाग तक)। एल्गोरिथ्म पुन: पॉलीलाइन को विभाजित करता है। एल्गोरिथ्म में इनपुट पहले और आखिरी के बीच सभी बिंदुओं का निर्देशांक है, जिसमें उनके साथ-साथ ε का मूल्य भी शामिल है। पहले और आखिरी अंक को अपरिवर्तित रखा गया है। उसके बाद, एल्गोरिथ्म पहले और अंतिम सेगमेंट से बिंदु को सबसे दूर पाता है ( खोज एल्गोरिदम बिंदु से खंड की दूरी है )। यदि बिंदु point से कम दूरी पर स्थित है, तो सभी बिंदु जो अभी तक संरक्षण के लिए चिह्नित नहीं किए गए हैं, उन्हें सेट से बाहर निकाला जा सकता है, और परिणामस्वरूप सीधी रेखा कम से कम accuracy की सटीकता के साथ वक्र को चिकना करती है। यदि यह दूरी ε से अधिक है, तो एल्गोरिथ्म पुनरावर्ती रूप से सेट पर खुद को शुरुआती बिंदु से दिए गए और दिए गए से अंतिम बिंदुओं तक कहता है। यह ध्यान देने योग्य है कि डगलस-पीकर एल्गोरिथ्म अपने काम के दौरान टोपोलॉजी को संरक्षित नहीं करता है। इसका मतलब यह है कि परिणामस्वरूप, हम स्वयं-चौराहों के साथ एक पंक्ति प्राप्त कर सकते हैं। एक उदाहरण के रूप में, अंक के निम्नलिखित सेट के साथ एक पॉलीलाइन लें: [{1; 5}, {2; 3}, {5; 1}, {6; 4}, {9; 6}, {11; 4}, {13; 3}, {14; 2}, {18; 5}] और] के विभिन्न मूल्यों के सरलीकरण प्रक्रिया को देखें:

मूल पॉलीलाइन अंक के प्रस्तुत सेट से:



0.5 के बराबर ε के साथ पालीलाइन:



1 के बराबर ε के साथ एक पॉलीलाइन:



पॉलिनेशन line 1.5 के बराबर:



आप अधिकतम दूरी बढ़ा सकते हैं और एल्गोरिथ्म की कल्पना कर सकते हैं, लेकिन मुझे लगता है कि इन उदाहरणों के बाद मुख्य बिंदु स्पष्ट हो गया है।

कार्यान्वयन

C ++ को एल्गोरिथम के कार्यान्वयन के लिए प्रोग्रामिंग भाषा के रूप में चुना गया था, एल्गोरिथ्म का पूर्ण स्रोत कोड जिसे आप यहां देख सकते हैं। और अब सीधे ही कार्यान्वयन के लिए:

#define X_COORDINATE 0 #define Y_COORDINATE 1 template<typename T> using point_t = std::pair<T, T>; template<typename T> using line_segment_t = std::pair<point_t<T>, point_t<T>>; template<typename T> using points_t = std::vector<point_t<T>>; template<typename CoordinateType> double get_distance_between_point_and_line_segment(const line_segment_t<CoordinateType>& line_segment, const point_t<CoordinateType>& point) noexcept { const CoordinateType x = std::get<X_COORDINATE>(point); const CoordinateType y = std::get<Y_COORDINATE>(point); const CoordinateType x1 = std::get<X_COORDINATE>(line_segment.first); const CoordinateType y1 = std::get<Y_COORDINATE>(line_segment.first); const CoordinateType x2 = std::get<X_COORDINATE>(line_segment.second); const CoordinateType y2 = std::get<Y_COORDINATE>(line_segment.second); const double double_area = abs((y2-y1)*x - (x2-x1)*y + x2*y1 - y2*x1); const double line_segment_length = sqrt(pow((x2-x1), 2) + pow((y2-y1), 2)); if (line_segment_length != 0.0) return double_area / line_segment_length; else return 0.0; } template<typename CoordinateType> void simplify_points(const points_t<CoordinateType>& src_points, points_t<CoordinateType>& dest_points, double tolerance, std::size_t begin, std::size_t end) { if (begin + 1 == end) return; double max_distance = -1.0; std::size_t max_index = 0; for (std::size_t i = begin + 1; i < end; i++) { const point_t<CoordinateType>& cur_point = src_points.at(i); const point_t<CoordinateType>& start_point = src_points.at(begin); const point_t<CoordinateType>& end_point = src_points.at(end); const double distance = get_distance_between_point_and_line_segment({ start_point, end_point }, cur_point); if (distance > max_distance) { max_distance = distance; max_index = i; } } if (max_distance > tolerance) { simplify_points(src_points, dest_points, tolerance, begin, max_index); dest_points.push_back(src_points.at(max_index)); simplify_points(src_points, dest_points, tolerance, max_index, end); } } template< typename CoordinateType, typename = std::enable_if<std::is_integral<CoordinateType>::value || std::is_floating_point<CoordinateType>::value>::type> points_t<CoordinateType> duglas_peucker(const points_t<CoordinateType>& src_points, double tolerance) noexcept { if (tolerance <= 0) return src_points; points_t<CoordinateType> dest_points{}; dest_points.push_back(src_points.front()); simplify_points(src_points, dest_points, tolerance, 0, src_points.size() - 1); dest_points.push_back(src_points.back()); return dest_points; } 

ठीक है, वास्तव में एल्गोरिथ्म का उपयोग स्वयं:

 int main() { points_t<int> source_points{ { 1, 5 }, { 2, 3 }, { 5, 1 }, { 6, 4 }, { 9, 6 }, { 11, 4 }, { 13, 3 }, { 14, 2 }, { 18, 5 } }; points_t<int> simplify_points = duglas_peucker(source_points, 1); return EXIT_SUCCESS; } 

एल्गोरिथ्म निष्पादन उदाहरण

इनपुट के रूप में, हम पहले से ज्ञात ज्ञात बिंदुओं को लेते हैं [{1; 5}, {2; 3}, {5; 1}, {6; 4}, {9; 6}, {11; 4}, {13; 3}, {14; 2}, {18; 5}] और} 1 के बराबर:

• खंड से सबसे दूर बिंदु का पता लगाएं {1; 5} - {18; 5}, यह बिंदु {5 होगा; 1}।
  
  
• खंड {1 पर इसकी दूरी की जाँच करें; 5} - {18; 5}। यह 1 से अधिक निकला, जिसका अर्थ है कि हम इसे परिणामस्वरूप पॉलीलाइन में जोड़ते हैं।
• खंड {1 के लिए पुनरावर्ती एल्गोरिदम चलाएं; 5} - {5; 1} और इस सेगमेंट के लिए सबसे दूर बिंदु खोजें। यह बिंदु {२; 3}।
  
  
• खंड {1 पर इसकी दूरी की जाँच करें; 5} - {5; 1}। इस मामले में, यह 1 से कम है, जिसका अर्थ है कि हम इस बिंदु को सुरक्षित रूप से त्याग सकते हैं।
• खंड 5 के लिए पुनरावर्ती एल्गोरिदम चलाएं; 1} - {18; 5} और इस सेगमेंट के लिए सबसे दूर की बात ...
  
  
• और इसी तरह उसी योजना के अनुसार ...

नतीजतन, इस परीक्षण डेटा के लिए पुनरावर्ती कॉल ट्री इस तरह दिखाई देगा:

काम का समय

एल्गोरिथ्म की अपेक्षित जटिलता सबसे अच्छा हे (nlogn) है, यह तब है जब सबसे दूर बिंदु की संख्या हमेशा शाब्दिक रूप से केंद्रीय होती है। हालांकि, सबसे खराब स्थिति में, एल्गोरिथ्म की जटिलता ओ (एन ^ 2) है। यह प्राप्त किया जाता है, उदाहरण के लिए, यदि सबसे दूर बिंदु की संख्या हमेशा सीमा बिंदु की संख्या के समीप होती है।

मुझे उम्मीद है कि मेरा लेख किसी के लिए उपयोगी होगा, मैं इस तथ्य पर भी ध्यान आकर्षित करना चाहूंगा कि यदि लेख पाठकों के बीच पर्याप्त रुचि दिखाता है, तो मैं जल्द ही रियुम्न-विटकम, ओपीहेम और लैंग की बहुभुज श्रृंखला को सरल बनाने के लिए एल्गोरिदम पर विचार करने के लिए तैयार रहूंगा। आपका ध्यान के लिए धन्यवाद!