जियोइन्फॉर्मेशन सिस्टम धीरे-धीरे रोजमर्रा की जिंदगी में प्रवेश कर रहा है।

अधिकांश मोबाइल उपकरण GPS / GLONASS रिसीवर से लैस हैं। इससे डेवलपर्स अपने उपयोगकर्ताओं (ट्रैक) का ट्रैक रिकॉर्ड प्राप्त कर सकते हैं। ट्रैक का उपयोग कई समस्याओं को हल करने के लिए किया जा सकता है - मानचित्र को नेविगेट करने और ट्रैफ़िक जाम के निर्माण के लिए दोस्तों के स्थान के बारे में सूचित करने और ट्रैफ़िक स्थिति की भविष्यवाणी करने से।

दुर्भाग्य से, अतिरिक्त प्रसंस्करण के बिना, उपयोगकर्ता का ट्रैक एकरूप है, इसलिए, बाहरी डेटा और आंतरिक एप्लिकेशन मैप को लिंक करने के चरण की आवश्यकता होती है। ऐसा करने के लिए, विशेष डेटा मिलान एल्गोरिदम (मानचित्र मिलान एल्गोरिदम) हैं।

यह लेख एक ट्रैक को रोड ग्राफ से जोड़ने और Map@Mail.ru परियोजना में इसके आवेदन के परिणामों के लिए समर्पित है।

जिस एल्गोरिथ्म पर चर्चा की जाएगी, आने वाले ट्रैक को प्रोसेस करता है, आउटपुट पर रोड ग्राफ के किनारों का एक क्रम प्राप्त होता है, जो इनपुट डेटा को उनके ज्यामिति के साथ निकटता से दोहराते हैं।

रोड ग्राफ एक भौगोलिक सूचना अनुप्रयोग की नींव में से एक है। इसमें सड़कों के बारे में सभी जानकारी शामिल है: कोटिंग के प्रकार और गलियों की संख्या से लेकर उनकी ज्यामिति तक। कंप्यूटर मेमोरी में रोड ग्राफ का प्रतिनिधित्व करने के कई तरीके हैं।

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

यह ताश के पत्तों की तरह एक मास्को इंटरचेंज दिखता है:


और इसलिए, नाविकों के संस्करण के अनुसार, हमारे उपयोगकर्ता इस पर चलते हैं:

ट्रैक बाइंडिंग प्रक्रिया

एक ट्रैक पर एक बिंदु को एक ग्राफ पर स्नैप करने के लिए, सरलतम मामले में, आपको किनारे से बिंदु तक न्यूनतम दूरी के साथ किनारों को खोजने की आवश्यकता है। दुर्भाग्य से, व्यवहार में (विशेष रूप से शहर के केंद्र में), इस तरह से बंधा हुआ मार्ग एक दूसरे से जुड़े किनारों का एक सेट हो सकता है। बाध्यकारी की गुणवत्ता में सुधार करने के लिए, हम मानते हैं कि ट्रैक ग्राफ़ के किनारों के ज्यामितीय भागों के साथ उपयोगकर्ता का एक लक्षित लक्षित आंदोलन है। यही है, पूरा मार्ग एक दूसरे से जुड़ी पसलियों के साथ गुजरता है। उसी समय, मार्ग के प्रत्येक किनारे के लिए, ट्रैक पर कई बिंदु हो सकते हैं, और एक भी नहीं।

इस प्रकार, चूंकि हम किनारे को बिंदु के सबसे करीब ले जाने से इनकार करते हैं, हमें कुछ अन्य मात्रात्मक उपाय चुनने की आवश्यकता होती है जो हमें यह निर्धारित करने की अनुमति देगा कि मापा किनारा तड़कने के लिए कितना उपयुक्त है।

ऐसे कई कारक हैं जिनका उपयोग इस मामले में किया जा सकता है:

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

इन कारकों के आधार पर, एक संभावना मूल्यांकन सूत्र बनाया जाता है। फ़्रीचेट दूरी का उपयोग इन सूत्रों में से एक के रूप में किया जाता है। सीधे शब्दों में कहें तो, यह कुत्ते के पट्टे की न्यूनतम आवश्यक लंबाई है यदि मालिक रोड ग्राफ का अनुसरण करता है और उसका पालतू जीपीएस ट्रैक का अनुसरण करता है। यह अनुमान केवल ट्रैक की भौगोलिक सुदूरता पर केंद्रित है।

इस लेख में पटरियों को बांधने के लिए, हम एक वृद्धिशील डेटा-बाइंडिंग एल्गोरिथ्म के लिए अनुमान सूत्र का उपयोग करते हैं (एस। बाराकात्सोलास [2] के काम के आधार पर)।

इस सूत्र में दो मुख्य घटक शामिल हैं: और ।

अंग ट्रैक पॉइंट से किनारे तक भारित दूरी को ध्यान में रखता है और सूत्र द्वारा गणना की जाती है:

जहाँ
स्केलिंग कारक हैं, और बिंदु p _i से किनारे c _j की ज्यामिति की दूरी है।

अंग रिब की ज्यामिति की दिशा और ट्रैक की दिशा के बीच के कोण को ध्यान में रखता है:

जहाँ
और स्केलिंग कारक हैं, और कॉस (α _{i, j} ) ग्राफ के ith किनारे की ज्यामिति और ट्रैक के किनारे पर आंदोलन की दिशा के बीच का कोण है
और - ये पैरामीटर हैं जो घटकों के महत्व को प्रभावित करते हैं। एल्गोरिथ्म के लिए, एक दूसरे के सापेक्ष इन मापदंडों के मूल्य महत्वपूर्ण हैं - यह निर्धारित करता है कि तुलना करते समय किन कारकों का वजन अधिक होगा।

मापदंडों और वर्णित कारक में परिवर्तन की संवेदनशीलता को प्रभावित करते हैं।

घटकों की गणना करने के बाद, अंतिम मीट्रिक की गणना इस प्रकार की जाती है:



परिणाम जितना बड़ा होगा, ट्रैक सेक्शन और किनारे का संयोग उतना ही बेहतर होगा।

आपके शस्त्रागार में प्लॉट किए गए मार्ग की संभावना का सूत्र होने पर, आप बाध्यकारी एल्गोरिथ्म का वर्णन कर सकते हैं:

1. , ;
2. ;
3. . ;
4. , . ( , );
5. ;
6. 2;

अनुवर्ती रणनीति

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

प्रदर्शन के बारे में थोड़ा सा

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

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

परिणाम

बाइंडिंग एल्गोरिदम के कार्यान्वयन ने न केवल मोबाइल उपयोगकर्ता डेटा के साथ काम करना शुरू करने के लिए मैप ऑफ़ प्राइवेसी प्रोजेक्ट की अनुमति दी, बल्कि मनमाने सिस्टम के साथ अपने स्वयं के डेटा को जल्दी से समन्वयित करने के लिए भी। बाइंडिंग के नए सबसिस्टम का उपयोग करने से एक ही सर्वर पर एक मिनट के भीतर आपके ग्राफ पर पटरियों को फिर से बनाने की अनुमति मिलती है, जिसमें कुल 55 हजार अंक तक होते हैं। इसके लिए धन्यवाद, डेटा उपयोगकर्ताओं को जितनी जल्दी हो सके प्रदर्शित किया जाता है। एल्गोरिदम आंतरिक ग्राफ़ के तीन किनारों पर ट्रैक के एक बिंदु पर भी एक गुणात्मक संदर्भ दिखाता है। हालांकि, वर्णित एल्गोरिथ्म की सबसे बड़ी दक्षता ग्राफ के प्रत्येक किनारे पर एक या दो बिंदुओं के साथ लंबी पटरियों के बंधन के दौरान हासिल की जाती है।

संबंधित साहित्य

1. “मानचित्र मिलान। एक परिचय “प्रो। डेविड बर्नस्टीन, जेम्स मैडिसन यूनिवर्सिटी।
2. "मैप-मैचिंग व्हीकल ट्रैकिंग डेटा पर" सोतीरिस ब्रैकटोसस, डाइटर पीफोसर रान्डल सालास कैरा वेक VLDB'05
3. "अनुमानित दूरी फ़्रीचेट दूरी के संबंध में मिलान" डैनियल चेन, ऐनी Driemel, लियोनिडस जे। गुइबास, एंडी गुयेन, कैरोला वेनक। स्टैनफोर्ड। 2011

---

लेव ड्रैगुनोव, मैप्स रम्बलर के टॉप 100 के लिए एक प्रोग्रामर