लाइन स्ट्रिंग्स

Question

के बीच समानता मेरे पास एक जीपीएस द्वारा रिकॉर्ड किए गए कई ट्रैक हैं, जो अधिक औपचारिक रूप से कई लाइन स्ट्रिंग के रूप में वर्णित किए जा सकते हैं।

अब, कुछ रिकॉर्ड किए गए ट्रैक एक ही मार्ग के रिकॉर्डिंग हो सकते हैं, लेकिन जीपीएस सिस्टम में गलत होने की वजह से, यह तथ्य कि विभिन्न अवसरों पर रिकॉर्डिंग किए गए थे और वे अलग-अलग गति से यात्रा दर्ज कर सकते थे, वे पूरी तरह से मेल नहीं खाएंगे, लेकिन एक मानव द्वारा मानचित्र पर देखे जाने पर यह काफी करीब दिखता है कि यह वास्तव में वही मार्ग है जो रिकॉर्ड किया गया है।

मैं एक एल्गोरिदम खोजना चाहता हूं जो दो रेखा तारों के बीच समानता की गणना करता है। मैं ऐसा करने के लिए कुछ घर उगाए गए तरीकों के साथ आया हूं, लेकिन यह जानना चाहूंगा कि यह एक समस्या है जो इसे हल करने के लिए पहले से ही अच्छा एल्गोरिदम है।

आप समानता की गणना कैसे करेंगे, यह देखते हुए कि समान माध्यम नक्शे पर एक ही पथ का प्रतिनिधित्व करते हैं?

संपादित करें: मैं क्या, कृपया क्या एक लाइन स्ट्रिंग है की एक परिभाषा के लिए इस लिंक को देखने के बात कर रहा हूँ के बारे में अनिश्चित उन लोगों के लिए: http://msdn.microsoft.com/en-us/library/bb895372.aspx - मैं नहीं चरित्र तार के बारे में पूछ रहा हूँ।

Answer 1

ट्रैक की प्रत्येक जोड़ी पर Fréchet distance की गणना करें। दूरी का उपयोग आपके ट्रैक की समानता को मापने के लिए किया जा सकता है।

मठ चेतावनी: Fréchet metric space के क्षेत्र जो आपकी समस्या के लिए प्रासंगिक है में अग्रणी था।

Answer 2

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

Answer 3

"उसी मार्ग" को निर्धारित करने के लिए, सामान्यीकृत पथ वैक्टरों का न्यूनतम सेट बनाएं, कुल पावर मतभेदों की गणना करें और कुल गुणवत्ता माप की तुलना करें।

1. कुल पथ लंबाई पर जीपीएस वेपोइंट सामान्यीकृत करें,
2. रास्तों में से वैक्टर एक साथ चलते हैं, प्रत्येक वेपॉइंट पर कम से कम वेक्टर पर आधारित प्रत्येक पथ के लिए पथ वैक्टर का एक नया सेट बनाने,
3. गणना वेक्टर लंबाई के लिए वेटिंग सामान्यीकृत पथों में प्रत्येक वेक्टर के अंतराल के बीच कुल बिजली अंतर, और
4. गुणवत्ता माप के विरुद्ध तुलना करें।

मतभेदों की शक्ति (शुरू करें, कहें, स्क्वायर मतभेद) शुरू करें और गुणवत्ता माप (कुल शक्ति मतभेदों का प्रतिशत के रूप में कहें) दृष्टि से ट्यून करें। इस एल्गोरिथ्म पथ मैच की एक सतत गुणवत्ता माप के साथ-साथ एक द्विआधारी परिणाम पैदा करता है (पथ समान है?)

पॉल Tomblin कहा: मैं अनुमान के आधार पर पहली पंक्ति के चारों ओर एक बफर जोड़ना होगा संभावित त्रुटि, और फिर निर्धारित करें कि दूसरी पंक्ति पूरी तरह से बफर के भीतर फिट बैठती है या नहीं।

आप सामान्यीकृत वेक्टर एंडपॉइंट्स की तुलना में एल्गोरिदम को संशोधित कर सकते हैं। आप यह निर्धारित कर सकते हैं कि कोई अंतराल अंतर एक निश्चित आकार से ऊपर था (पॉल के बफर विचार को लागू करना) या शायद, यदि अंतराल "बफर" के बाहर थे, तो उस तथ्य का उपयोग उस अंतराल अंतर को अनदेखा करने के लिए करें, तुलना तुलनात्मक पक्षों को से अनदेखा करने की अनुमति देता है।

Answer 4

मैं वास्तव में उस व्यक्ति (एरोर्न एफ) के साथ पक्ष में हूं, जिन्होंने कहा था कि आपको लेवेनशेटिन दूरी की समस्या में रुचि हो सकती है (और this उद्धृत)। उनका जवाब मुझे अब तक का सबसे अच्छा लगता है।

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

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

1: http://en.wikipedia.org/wiki/Levenshtein_distance, http://www.nist.gov/dads/HTML/Levenshtein.html

Answer 5

आप प्रत्येक बिंदु LineString एक की (Pa) के साथ चल और Pa से LineString बी के पास लाइन खंड के लिए दूरी को मापने, इन दूरियों से प्रत्येक औसत सकता है।

यह एक त्वरित या सही विधि नहीं है, लेकिन एक उपयोगी संख्या का उपयोग करने में सक्षम होना चाहिए और इसे लागू करने के लिए बहुत तेज़ है।

लाइन स्ट्रिंग्स समान बिंदुओं पर शुरू होती हैं और खत्म होती हैं, या वे बहुत अलग हैं?

Answer 6

यदि आप [x, y] अंक (या [x, y, z] बिंदुओं का अनुक्रम होने के लिए एक पंक्ति स्ट्रिंग मानते हैं), तो आप Needleman-Wunsch एल्गोरिदम का उपयोग करके लाइन स्ट्रिंग्स की प्रत्येक जोड़ी के बीच समानता की गणना कर सकते हैं । जैसा कि संदर्भित विकिपीडिया लेख में वर्णित है, सुलेमेन-वुन्श एल्गोरिदम को "समानता मैट्रिक्स" की आवश्यकता होती है जो अंक की एक जोड़ी के बीच की दूरी को परिभाषित करता है। हालांकि, मैट्रिक्स की बजाय फ़ंक्शन का उपयोग करना आसान होगा। आपके मामले में आप बिंदुओं की प्रत्येक जोड़ी के बीच दूरी प्रदान करने के लिए बस 2 डी Euclidean distance फ़ंक्शन (या 3 डी यूक्लिडियन फ़ंक्शन यदि आपके अंक ऊंचाई हैं) का उपयोग कर सकते हैं।