كيفية تحديد المسار من صاخبة X, Y البيانات

Question

لدي قائمة لم يتم فرزها صاخبة X, Y نقاط.إلا أنها تشكل الطريق عبر العالم.أود خوارزمية رسم تقريبي من هذه البيانات باستخدام شرائح الخط.

هذا هو مماثل لكيفية استخدام الخط المناسب خوارزمية اختيار تقريب خطي البيانات.مشكلتي هي أصعب لأن المسار الانحناءات الرياح في جميع أنحاء العالم.النص البديل http://www.praeclarum.org/so/pathfinder.png

لا أحد يعرف من أي معيار / القوي / من السهل فهم الخوارزميات لتحقيق هذا الهدف ؟

Q&A:

ماذا تعني صاخب ؟ إذا كنت قد المثالي تحقيق المسار ، ثم مجموعة من النقاط على أن يتم سحب عينات من أن مسار المثالي مع جاوس الضوضاء وأضاف أن X و Y العناصر.أنا لا أعرف يعني أو الانحراف المعياري تلك الضوضاء.كنت قد تكون قادرة على تخمين في std dev...

هل وتكمن نقطة قرب ، ولكن ليس على بعض مثالية ولكن معقدة المسار الذي كنت تسعى لتقريب? نعم.

هل لديك أي بداهة معلومات عن شكل المسار ؟ أي طريقة أخرى للحصول على هذه المعلومات ؟ للأسف لا.

Answer 1

مع قائمة لم يتم فرزها ، لن تعرف حقا مما يشير إلى تدرج في كل قطاع ، لذلك أعتقد أنك يمكن أن تذهب فقط مع أقرب نقطة.

طريقة واحدة يمكن أن تختار نقطة البداية عشوائيا ، واختيار أقرب نقطة النقطة التالية في كل خطوة.إضافة نقطتين الأولى إلى مجموعة S.

تناسب خط النقاط في الصورة حتى RMS يتجاوز بعض القيمة ، ثم مسح S و بداية سطر جديد.

تقاطع خطوط متتالية سيكون نهاية نقطة من القطاعات.

Answer 2

بيزيه الاستيفاء قد يصلح المشكلة.

هذا لا يتناول ترتيب النقاط في الطريق ، ومع ذلك ؛ هناك عدد من الطرق للنظر:

• أي "الأمثل" هو نوع من الطريق (مثلأصغر تغيير الاتجاه في كل نقطة على المسار ، * أقصر الطرق من خلال جميع نقاط) من المرجح أن تختزل NP كاملة المشكلة السفر بائع (ملعقة صغيرة).
• "معقولة" الطريق إلى المجموعة العقد ثم الطريق بين المجموعات داخل المجموعات.بالطبع أكبر كتلة أو أكبر عدد من المجموعات أكثر هذا أصغر المشكلة تبدو كبيرة ن ملعقة شاي.
• يأمر نقاط من خلال محور واحد.إذا كان هناك أكثر من 2 محاور بعض الأبعاد الحد من استراتيجية قد تكون مفيدة.على سبيل المثالمستقل مكون التحليل.

Answer 3

إذا كانت النقاط الخاصة بك هي قريبة من بعضها البعض, يمكنك طبيعية "مستقيم" خطوط (خطوط متعامدة).استخدام عادي تجانس الخوارزميات.يمكنك أن ترى العالم بأنها مسطحة.

إذا كانت متباعدة ، تحتاج لتعويض التقريب الأرض ، باستخدام كبيرة الدوائر إلى التنقل من نقطة إلى نقطة.وإلا خطوط مستقيمة سوف تجعل الطريق أطول.

هو اختيارك إذا نقطة بعيدة جدا لإنشاء خطوط مستقيمة.

كذلك عليك أن تعرف إذا كنت بحاجة إلى "زيارة" كل نقطة, أو تحتاج فقط للذهاب بالقرب وكيف بالقرب من قرب.

إذا كنت بحاجة إلى إرسال الدورة(s) إلى طائرة أو سفينة أو غير مسافر ، ربما تحتاج إلى زيارة كل نقطة.إذا كنت الحصول على بيانات GPS من كائن ، ربما كنت ترغب فقط في رسم مسار على الشاشة ، وإزالة الضوضاء.

---

بعد رؤية التعديلات: إذا كان هذا هو كائن نقل بعض traject تريد مؤامرة ، قد ترغب في تخفيف اتجاه وسرعة بدلا من x/y القيم.(جعل القيم المقاسة (x) يكون ثابت وزيادة Y-الفاصل الزمني يجعل تجانس أسهل كثيرا.)

Answer 4

هنا هو ارشادي الإختراق التي قد تعالج يأمر مشكلة البيانات ، إذا

• لديك ما يكفي من النقاط
• يعني المسافة بين نقطة صغيرة مقارنة أصغر دائرة نصف قطرها من انحناء المتوقعة من المسار
• يعني المسافة بين نقطة ليست كبيرة بالمقارنة مع الأمراض المنقولة جنسيا.dev.الضوضاء
• الطريق ليست الذاتي المعبر (قد تحصل على الحظ لكن لا ضمانات)

المضي قدما مثل هذا:

1. اختيار (أمل فعلي بدلا من عشوائية يعني) نقطة انطلاق ، p1.
2. إيجاد جميع النقاط التي تقع داخل بعض المجموعات المسافة ، r_c من p1.اختيار r_c صغيرة مقارنة مع المتوقع تحول دائرة نصف قطرها ، ولكن كبيرة مقارنة مبعثر.
3. دعوة هذه المجموعة C1.
4. العثور على نقطة q1 يعني من المناصب في C1.
5. تناسب الخط إلى نقطة في C1 و مشروع (أو بعدها) حافة المجموعة والعثور على أقرب نقطة في البيانات الأصلية.تسمية هذه النقطة p2.
6. تكرار الخطوات من 2-5 حتى نفاد البيانات.

الآن لديك قائمة جديدة من النقاط q1..qn التي أمرت.

من على قمة رأسي صعبة للغاية ، و يعمل فقط تحت ظروف جيدة...

---

الذاتي المعبر السلوك ربما يمكن أن تحسن من تتطلب في الخطوة (5) أن الجديد المتوقع خط تكمن في بعض أقصى زاوية من سابقتها.

Answer 5

المشكلة مع منحنى بيزيه أن لا يذهب في الواقع على الرغم من النقاط لديك عينات وعلى الرغم من النقاط عينات مشوهة قليلا ؛ فإن منحنى بيزيه قد يكون في الواقع ميلا قبالة.

تقريب أفضل و الحل الذي يبدو تشبه الصورة الأصلية أفضل طريقة هي كاتمول-Rom المفتاح لأنها لا تعمل على الرغم من كل نقطة في المنحنى.

Answer 6

توجهي سيكون أول فرز قائمة من النقاط ، ثم استخدام منحنى بيزيه.

الخدعة هي بالطبع الفرز.تبدأ مع واحد عشوائي نقطة والعثور على أقرب نقطة.تفترض هذه الأمرين.مع هذه النهاية اثنين ، والعثور على أقرب نقطة لهم.نفترض أن واحد مع أصغر المسافة إلى نقطة النهاية متصل إلى تلك النقطة.كرر حتى ترتبط كل نقطة.

أعتقد أنه لا تزال هناك بعض المشاكل مع هذا النهج ، لكن ربما يمكنك استخدامه بمثابة نقطة البداية (يقصد التورية).

تحرير: يمكنك أن تفعل ذلك عدة مرات مع نقاط انطلاق مختلفة ، ومن ثم نرى أين النتائج تختلف.على الأقل يعطي بعض الثقة النقاط التي ترتبط مع بعضها البعض.

Answer 7

نهجا مختلفا تماما, هذا لا يحتاج إلى قيد آخر ، ولكن التفاصيل قد تعتمد على التطبيق الخاص بك.فإنه sghould تعمل بشكل أفضل إذا كان لديك "سحابة كثيفة من النقاط" حول المسار.

استخدام "التكلفة" وظيفة أن يعرف الفرق بين منحنى سحابة من النقاط.استخدام parametrized المنحنى القياسي الأمثل الخوارزمية.- أو - تبدأ مع منحنى مستقيم من البداية إلى النهاية ، ثم استخدام الخوارزمية الجينية إلى تعديله.

نموذجية تكلفة وظيفة أن تأخذ أصغر المسافة بين كل نقطة و المنحنى و مجموع المربعات.

ليس لدي خبرة كافية تشير إلى الأمثل أو الخوارزمية الجينية ولكن أنا متأكد من أنه يمكن القيام به :)

يمكنني أن أتخيل الخوارزمية الجينية على النحو التالي:المسار سيتم بناؤها من نقاط الطريق.تبدأ مع وضع N نقاط الطريق في straigt خط من البداية إلى النهاية.(ن يمكن اختيارها اعتمادا على المشكلة).الطفرات التي يمكن أن تكون:

1. لكل شريحة ، إذا rnd() < x, إحداثية جديدة يتم تقديمها في الوسط.
2. لكل إحداثية ، X و Y إحداثيات متنوعة قليلا.

سوف تحتاج إلى تضمين إجمالي طول في تكلفة وظيفة.تقسيم قد لا تكون ضرورية ، أو ربما x ("تقسيم فرصة") قد تحتاج إلى إنقاص المزيد من النقاط يتم تقديمها.كنت قد أو قد لا ترغب في تطبيق (2) البداية و نقطة النهاية.

سيكون من المرح في محاولة ذلك...

Answer 8

أنا أعتبر أنه "لم يتم فرزها قائمة" يعني أنه في حين الخاص بك في مجموعة من النقاط كاملة ، أنت لا تعرف ما كانوا سافر ؟

جاوس الضوضاء يجب أن يكون أساسا تجاهلها.لدينا على الإطلاق أي المعلومات التي تسمح لنا لجعل أي محاولة لإعادة بناء النص الأصلي ، الامم المتحدة صاخبة المسار.لذلك أعتقد أن أفضل ما يمكننا فعله هو تحمل نقاط صحيحة.

في هذه المرحلة المهمة تتكون من "العثور على أفضل مسار من خلال مجموعة من النقاط" ، مع "أفضل" تبقى غامضة.أضفت بعض التعليمات البرمجية التي يحاول النظام مجموعة من النقاط في الفضاء الإقليدية ، مفضلا orderings التي تؤدي إلى استقامة خطوط.في حين أن المقياس كانت سهلة التنفيذ ، لم أستطع التفكير في وسيلة جيدة لتحسين الطلب على أساس أن أنا فقط عشوائيا مبادلة نقطة على الترتيب.

لذا هنا بعض PLT مخطط رمز أن يفعل ذلك.

#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)

Answer 9

يبدو أنك تعرف الذهبي منحنى' من إجاباتك على الأسئلة أود أن أقترح إيجاد منحنى بيزيه من الذهبي منحنى' كما اقترح @jamesh و الرسم.

Answer 10

كيف العديد من النقاط لديك ؟
وهو منحنى بيزيه ، كما ذكر ، هو فكرة جيدة إذا كان لديك comparedly بعض النقاط.إذا كان لديك العديد من النقاط ، وعمارة مجموعات كما اقترح dmckee.

ومع ذلك كنت أيضا تحتاج إلى عائق آخر في تحديد ترتيب نقاط.كانت هناك العديد من الاقتراحات الجيدة لكيفية اختار النقاط ، ولكن ما لم كنت أعرض عائق آخر ، أي يعطي حلا ممكنا.

القيود المحتملة أستطيع أن أفكر:

• أقصر طريق
• معظم قطاعات مباشرة
• أقل مجموع المطلق دوران
• الاتجاه تفضيل (أيأفقي / عمودي هو المرجح أكثر طولا)

في جميع الحالات ، لتلبية القيد ربما تحتاج إلى اختبار جميع التباديل من التسلسل.إذا كنت تبدأ مع "تخمين جيد" ، cayn إنهاء الآخرين بسرعة.