शोर एक्स, वाई डेटा

Question

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

यह रैखिक डेटा का अनुमान लगाने के लिए आप लाइन-फिटिंग एल्गोरिदम का उपयोग कैसे करेंगे। मेरी समस्या केवल कठिन है क्योंकि पथ दुनिया भर में झुकता है और हवाओं को घुमाता है। alt text http://www.praeclarum.org/so/pathfinder.png

क्या कोई इसे पूरा करने के लिए किसी भी मानक/मजबूत/आसानी से एल्गोरिदम को समझने में जानता है?

क्यू & एक:

क्या आप शोर से क्या मतलब है? यदि मेरे पास पथ का आदर्श अहसास था, तो अंक के मेरे सेट को उस आदर्श पथ से नमूना दिया जाएगा जिसमें एक्स और वाई तत्वों में जोड़ा गया गॉसियन शोर होगा। मुझे उस शोर का मतलब या मानक विचलन नहीं पता है। मैं std dev पर अनुमान लगाने में सक्षम हो सकता हूं ...

क्या अंक कुछ हद तक जटिल हैं, लेकिन कुछ आदर्श लेकिन जटिल पथ जिन्हें आप अनुमानित करना चाहते हैं? हां।

क्या आपके पास पथ के आकार के बारे में कोई प्राथमिक जानकारी है? ऐसी जानकारी प्राप्त करने का कोई और तरीका? दुर्भाग्य से नहीं।

Answer 1

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

यादृच्छिक रूप से प्रारंभ बिंदु चुनने का एक तरीका हो सकता है, और प्रत्येक चरण में अगले बिंदु के रूप में निकटतम बिंदु चुनें। पहले सेट को एक सेट एस

एस में बिंदुओं के लिए एक पंक्ति फ़िट करें जब तक कि आरएमएस कुछ मूल्य से अधिक न हो, फिर एस साफ़ करें और एक नई लाइन शुरू करें।

लगातार लाइनों का चौराहे सेगमेंट के अंत-बिंदु होंगे।

Answer 2

यदि आपके अंक एक-दूसरे के करीब हैं, तो आप सामान्य "सीधी" रेखाएं (ऑर्थोगोनल लाइन) कर सकते हैं। सामान्य smoothing algorithms का उपयोग करना। आप दुनिया को फ्लैट के रूप में देख सकते हैं।

यदि वे बहुत दूर हैं, तो आपको बिंदु से बिंदु पर नेविगेट करने के लिए great circles का उपयोग करके पृथ्वी के गोलाकार की भरपाई करने की आवश्यकता है। अन्यथा आपकी सीधी रेखाएं एक लंबा रास्ता बनाती हैं।

यदि आपकी ओर सीधी रेखाएं बनाने के लिए बहुत दूर है तो यह आपकी पसंद है।

इसके अलावा आप को पता है आप "जाएँ" करने के लिए प्रत्येक बिंदु, या बस के पास जाने की जरूरत की जरूरत है, और कैसे वह यह है कि पास के पास।

यदि आपको किसी विमान, जहाज या अन्य यात्री को पाठ्यक्रम (ओं) भेजने की आवश्यकता है, तो आपको शायद प्रत्येक बिंदु पर जाना होगा। यदि आपको किसी ऑब्जेक्ट से जीपीएस डेटा मिलता है, तो आप शायद स्क्रीन पर एक कोर्स प्लॉट करना चाहते हैं, और शोर को हटा सकते हैं।

---

अपने संपादनों को देखने के बाद: इस एक वस्तु है, तो कुछ traject आप प्लॉट करने के लिए चाहते हैं चलती, तो आप दिशा चिकनी और x/y मान के स्थान पर लाने के लिए चाहते हो सकता है।

Answer 3

Bezier Interpolation आपकी समस्या को फिट कर सकते हैं (अपने मापा मूल्यों (एक्स) बनाना एक तय की और बढ़ रही है वाई के अंतराल बहुत आसान बना देता है चौरसाई है।)।

Bezier Interpolation http://upload.wikimedia.org/wikipedia/en/thumb/0/0c/BezierInterpolation.gif/150px-BezierInterpolation.gif

यह एक पथ में अंक के आदेश को संबोधित नहीं करता है, तथापि, विचार करने के लिए कई दृष्टिकोण हैं:

• कोई भी "इष्टतम" प्रकार का पथ (उदा।पथ पर प्रत्येक बिंदु पर सबसे छोटी दिशा परिवर्तन, * सभी बिंदुओं के माध्यम से सबसे छोटा रास्ता) एनपी पूर्ण Travelling Salesman Problem (टीएसपी) को उबाल देगा।
• नोड्स को क्लस्टर करने के लिए एक "उचित" पथ और क्लस्टर के बीच मार्ग, और क्लस्टर के भीतर। बेशक, क्लस्टर जितना बड़ा होगा, या क्लस्टर की संख्या उतनी ही बड़ी होगी जितनी छोटी समस्या एक बड़ी एन टीएसपी की तरह दिखती है।
• एक अक्ष द्वारा अंक का ऑर्डर करना। यदि 2 अक्षरों से अधिक हैं, तो कुछ dimensional reduction रणनीति उपयोगी हो सकती है। जैसे स्वतंत्र घटक विश्लेषण।

Answer 4

यहाँ, एक अनुमानी हैक उस डेटा के लिए आदेश देने की समस्या का समाधान हो सकता है

• आप पर्याप्त अंक अगर
• अंक के बीच औसत दूरी वक्रता की छोटी से छोटी त्रिज्या की उम्मीद की तुलना में छोटा है पथ
• अंकों के बीच औसत दूरी std की तुलना में बड़ी नहीं है। देव। शोर के
• पथ नहीं आत्म पार कर रहा है (अगर आप भाग्यशाली हो सकती है, लेकिन कोई गारंटी)

इस तरह आगे बढ़ें: (यादृच्छिक साधन के बजाय एक सार्थक द्वारा उम्मीद है कि)

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

अब आप अंक की एक नई सूची q1 .. qn कि आदेश दिया जाता है।

मेरे सिर, बहुत किसी न किसी तरह के शीर्ष बंद

, और बहुत अच्छी परिस्थितियों में ही काम करता है ...

---

स्व पार व्यवहार शायद (5) है कि नए अनुमान चरण में की आवश्यकता द्वारा सुधार किया जा सकता रेखा पिछले एक के कुछ अधिकतम कोण के भीतर है।

Answer 5

ऐसा लगता है कि आप सवालों के जवाबों से 'सुनहरा वक्र' जानते हैं, मैं सुझाव देता हूं कि 'जमेमेश द्वारा सुझाए गए' सुनहरे वक्र के बेजियर वक्र को ढूंढने और उसे चित्रित करने का सुझाव दिया जाएगा।

Answer 6

मेरा दृष्टिकोण सबसे पहले अंक की अपनी सूची को क्रमबद्ध करना होगा, फिर एक बेजियर वक्र का उपयोग करें।

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

मुझे लगता है कि इस दृष्टिकोण के साथ अभी भी कुछ समस्याएं हैं, लेकिन हो सकता है कि आप इसे प्रारंभिक बिंदु (पन इरादा) के रूप में उपयोग कर सकें।

संपादित करें: आप इसे विभिन्न शुरुआती बिंदुओं के साथ कई बार कर सकते हैं, और फिर देखें कि परिणाम कहां भिन्न हैं। कम से कम आपको कुछ आत्मविश्वास देता है, जो अंक एक-दूसरे से जुड़े होते हैं।

Answer 7

आपके पास कितने अंक हैं?
जैसा कि बताया गया है, एक बेजियर वक्र, यदि आपके तुलनात्मक रूप से कुछ बिंदु हैं तो यह एक अच्छा विचार है। यदि आपके पास कई अंक हैं, तो डिक्की द्वारा सुझाए गए क्लस्टर को खरीदना।

हालांकि आप भी बिंदुओं का अनुक्रम को परिभाषित करने के लिए एक और बाधा जरूरत । अंक चुनने के लिए कई अच्छे सुझाव दिए गए हैं, लेकिन जब तक कि आप एक और बाधा उत्पन्न नहीं करते हैं, कोई भी संभावित समाधान देता है।

संभावित बाधाओं मैं के बारे में सोच सकते हैं:

• कम से कम पथ
• सबसे सीधे खंडों
• कम से कम कुल पूर्ण रोटेशन
• दिशात्मक वरीयता (यानी क्षैतिज/ऊर्ध्वाधर crisscrossing की तुलना में अधिक होने की संभावना है)

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

Answer 8

एक पूरी तरह से अलग दृष्टिकोण, जिसके लिए किसी अन्य बाधा की आवश्यकता नहीं है, लेकिन विवरण आपके आवेदन पर निर्भर हो सकते हैं। यदि आपके पास पथ के चारों ओर "बिंदुओं का घना बादल" है तो यह सबसे अच्छा काम करेगा।

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

सामान्य लागत कार्य प्रत्येक बिंदु और वक्र के बीच छोटी दूरी लेना होगा, और वर्गों को जोड़ना होगा।

क्या अनुकूलन या आनुवंशिक एल्गोरिथ्म सुझाव देने के लिए पर्याप्त नहीं अनुभव है लेकिन मुझे यकीन है कि यह किया जा सकता है :)

इस प्रकार मैं एक आनुवंशिक एल्गोरिथ्म कल्पना कर सकता हूँ: पथ वेपाइंट से बनाया जाएगा। शुरुआत से अंत तक एक स्ट्रैगेट लाइन में एन मार्गपॉइंट डालने से शुरू करें। (एन समस्या के आधार पर चुना जा सकता है)। उत्परिवर्तन हो सकता है:

1. प्रत्येक खंड के लिए, यदि rnd() < एक्स, एक नया वेपॉइंट बीच में शुरू की है।
2. प्रत्येक मार्ग के लिए, एक्स और वाई समन्वय थोड़ा अलग हैं।

आपको लागत कार्य में कुल लंबाई शामिल करने की आवश्यकता होगी। विभाजन की आवश्यकता नहीं हो सकती है, या शायद एक्स ("विभाजन मौका") को कम करने की आवश्यकता हो सकती है क्योंकि अधिक तरीके से पेश किए जाते हैं। आप प्रारंभ (और) शुरू करने के लिए (2) लागू नहीं कर सकते हैं।

कि कोशिश करने के लिए मजेदार होगा ...

Answer 9

बेज़ियर वक्र के साथ समस्या यह है कि

है वास्तव में, हालांकि अंक आप नमूना है और भले ही अंक नमूने एक छोटे से विकृत कर रहे हैं नहीं जाता है; बेजियर वक्र वास्तव में मील दूर हो सकता है।

एक बेहतर अनुमान, और मूल छवि जैसा दिखने वाला एक समाधान बेहतर है Catmull-Rom Spline क्योंकि यह वक्र में सभी बिंदुओं के बावजूद चलता है।

Answer 10

मुझे लगता है कि "अपरिवर्तित सूची" का अर्थ है कि जब आपके अंक का सेट पूरा हो गया है, तो आप नहीं जानते कि वे किस क्रम से यात्रा कर रहे थे?

गाऊसी शोर को मूल रूप से अनदेखा किया जाना चाहिए। हमें बिल्कुल कोई जानकारी नहीं दी गई है जो हमें मूल, अनौपचारिक पथ का पुनर्निर्माण करने का कोई प्रयास करने की अनुमति देती है। तो मुझे लगता है कि हम सबसे अच्छा कर सकते हैं मान लें कि अंक सही हैं।

इस बिंदु पर, कार्य में "सर्वश्रेष्ठ" बाएं अस्पष्ट के साथ "बिंदुओं के एक सेट के माध्यम से सबसे अच्छा मार्ग" होता है। मैंने कुछ कोड चाबुक किया जो यूक्लिडियन स्पेस में पॉइंट्स के सेट को ऑर्डर करने का प्रयास करता है, ऑर्डरिंग पसंद करता है जिसके परिणामस्वरूप स्ट्राइटर लाइनें होती हैं। जबकि मीट्रिक को कार्यान्वित करना आसान था, मैं उस पर आधारित ऑर्डरिंग को बेहतर बनाने का एक अच्छा तरीका नहीं सोच सका, इसलिए मैं यादृच्छिक रूप से एक बेहतर व्यवस्था की तलाश में अंक स्वैप कर रहा हूं।

तो, यहां कुछ पीएलटी योजना कोड है जो ऐसा करता है।

#lang scheme 

(require (only-in srfi/1 iota)) 

; a bunch of trig 
(define (deg->rad d) 
    (* pi (/ d 180))) 

(define (rad->deg r) 
    (* 180 (/ r pi))) 

(define (euclidean-length v) 
    (sqrt (apply + (map (lambda (x) (expt x 2)) v)))) 

(define (dot a b) 
    (apply + (map * a b))) 

(define (angle-ratio a b) 
    (/ (dot a b) 
    (* (euclidean-length a) (euclidean-length b)))) 

; given a list of 3 points, calculate the likelihood of the 
; angle they represent. straight is better. 
(define (probability-triple a b c) 
    (let ([av (map - a b)] 
     [bv (map - c b)]) 
    (cos (/ (- pi (abs (acos (angle-ratio av bv)))) 2)))) 

; makes a random 2d point. uncomment the bit for a 3d point 
(define (random-point . x) 
    (list (/ (random 1000) 100) 
     (/ (random 1000) 100) 
     #;(/ (random 1000) 100))) 

; calculate the likelihood of an entire list of points 
(define (point-order-likelihood lst) 
    (if (null? (cdddr lst)) 
     1 
     (* (probability-triple (car lst) 
          (cadr lst) 
          (caddr lst)) 
     (point-order-likelihood (cdr lst))))) 

; just print a list of points 
(define (print-points lst) 
    (for ([p (in-list lst)]) 
    (printf "~a~n" 
      (string-join (map number->string 
           (map exact->inexact p)) 
         " ")))) 

; attempts to improve upon a list 
(define (find-better-arrangement start 
           ; by default, try only 10 times to find something better 
           [tries 10] 
           ; if we find an arrangement that is as good as one where 
           ; every segment bends by 22.5 degrees (which would be 
           ; reasonably gentle) then call it good enough. higher 
           ; cut offs are more demanding. 
           [cut-off (expt (cos (/ pi 8)) 
               (- (length start) 2))]) 
    (let ([vec (list->vector start)] 
     ; evaluate what we've started with 
     [eval (point-order-likelihood start)]) 
    (let/ec done 
     ; if the current list exceeds the cut off, we're done 
     (when (> eval cut-off) 
     (done start)) 
     ; otherwise, try no more than 'tries' times... 
     (for ([x (in-range tries)]) 
     ; pick two random points in the list 
     (let ([ai (random (vector-length vec))] 
       [bi (random (vector-length vec))]) 
      ; if they're the same... 
      (when (= ai bi) 
      ; increment the second by 1, wrapping around the list if necessary 
      (set! bi (modulo (add1 bi) (vector-length vec)))) 
      ; take the values from the two positions... 
      (let ([a (vector-ref vec ai)] 
       [b (vector-ref vec bi)]) 
      ; swap them 
      (vector-set! vec bi a) 
      (vector-set! vec ai b) 
      ; make a list out of the vector 
      (let ([new (vector->list vec)]) 
       ; if it evaluates to better 
       (when (> (point-order-likelihood new) eval) 
       ; start over with it 
       (done (find-better-arrangement new tries cut-off))))))) 
     ; we fell out the bottom of the search. just give back what we started with 
     start))) 

; evaluate, display, and improve a list of points, five times 
(define points (map random-point (iota 10))) 
(define tmp points) 
(printf "~a~n" (point-order-likelihood tmp)) 
(print-points tmp) 
(set! tmp (find-better-arrangement tmp 10)) 
(printf "~a~n" (point-order-likelihood tmp)) 
(print-points tmp) 
(set! tmp (find-better-arrangement tmp 100)) 
(printf "~a~n" (point-order-likelihood tmp)) 
(print-points tmp) 
(set! tmp (find-better-arrangement tmp 1000)) 
(printf "~a~n" (point-order-likelihood tmp)) 
(print-points tmp) 
(set! tmp (find-better-arrangement tmp 10000)) 
(printf "~a~n" (point-order-likelihood tmp)) 
(print-points tmp)