Domanda

Ho un elenco non ordinato di punti X, Y rumorosi. Tuttavia, formano un percorso attraverso il mondo. Vorrei un algoritmo per disegnare un'approssimazione di questi dati usando segmenti di linea.

Questo è simile al modo in cui useresti un algoritmo di adattamento di linea per scegliere un'approssimazione di dati lineari. Il mio problema è più difficile solo perché il percorso si piega e si snoda in tutto il mondo. alt text http://www.praeclarum.org/so/pathfinder.png

Qualcuno conosce algoritmi standard / robusti / di facile comprensione per raggiungere questo obiettivo?

D amp; A &:

Che cosa intendi per rumore? Se avessi una realizzazione ideale del percorso, il mio insieme di punti verrebbe campionato da quel percorso ideale con rumore gaussiano aggiunto agli elementi X e Y. Non conosco la media o la deviazione standard di quel rumore. Potrei essere in grado di indovinare al dev dev ...

I punti si trovano vicino, ma non su, un percorso ideale ma complicato che cerchi di approssimare? Sì.

Hai informazioni a priori sulla forma del percorso? Qualche altro modo per ottenere tali informazioni? Purtroppo no.

È stato utile?

Soluzione

Con un elenco non ordinato, non saprai davvero quali punti includere in ogni segmento, quindi immagino che potresti semplicemente andare con il punto più vicino.

Un modo potrebbe essere quello di scegliere un punto iniziale a caso, e scegliere il punto più vicino come punto successivo in ogni passaggio. Aggiungi i primi due punti a un set S.

Adatta una linea ai punti in S fino a quando RMS non supera un certo valore, quindi cancella S e avvia una nuova linea.

L'intersezione di linee consecutive sarebbe il punto finale dei segmenti.

Altri suggerimenti

Interpolazione di Bezier potrebbe adattarsi al tuo problema.

Interpolazione di Bezier

Questo tuttavia non risolve l'ordinamento dei punti in un percorso; ci sono una serie di approcci da considerare:

  • Qualsiasi " ottimale " il tipo di percorso (ad es. il più piccolo cambio di direzione in ciascun punto del percorso, * Il percorso più breve attraverso tutti i punti) probabilmente ridurrà il NP completo Problema del commesso viaggiatore (TSP).
  • A " ragionevole " percorso per raggruppare i nodi e quindi instradare tra i cluster e all'interno dei cluster. Naturalmente, più grande è il cluster o maggiore è il numero di cluster, più questo piccolo problema sembra un grande n TSP.
  • Ordinamento dei punti per un asse. Se sono presenti più di 2 assi, alcune strategie riduzione dimensionale possono essere utili. per esempio. Analisi dei componenti indipendenti.

Se i tuoi punti sono vicini l'uno all'altro, puoi normalmente " dritto " linee (linee ortogonali). Utilizzando i normali algoritmi di smoothing . Puoi vedere il mondo piatto.

Se sono distanti, devi compensare l'arrotondamento della terra, usando grandi cerchi per navigare da un punto all'altro. Altrimenti le tue linee rette faranno una strada più lunga.

È una tua scelta se un punto è troppo lontano per creare linee rette.

Inoltre devi sapere se è necessario " visitare " ogni punto, o devi solo avvicinarti, e quanto è vicino quel vicino.

Se devi inviare il / i corso / i ad un aereo, una nave o un altro viaggiatore, probabilmente dovrai visitare ogni punto. Se ottieni i dati GPS da un oggetto, probabilmente vuoi solo tracciare un percorso su uno schermo e rimuovere il rumore.


Dopo aver visto le tue modifiche: Se si tratta di un oggetto che sposta una traiettoria che si desidera tracciare, è possibile attenuare la direzione e la velocità anziché i valori x / y. (Rendere i valori misurati (x) con un intervallo Y fisso e crescente rende molto più semplice il livellamento.)

Ecco un trucco euristico che potrebbe risolvere il problema di ordinazione dei dati, se

  • hai abbastanza punti
  • la distanza media tra i punti è piccola rispetto al raggio di curvatura più piccolo previsto per il percorso
  • la distanza media tra i punti non è grande rispetto allo standard. dev. del rumore
  • il percorso non è auto-attraversante (potresti essere fortunato, ma nessuna garanzia)

Procedi in questo modo:

  1. Scegli (si spera con mezzi significativi anziché casuali) un punto di partenza, p1 .
  2. Trova tutti i punti che si trovano entro una certa distanza di raggruppamento, r_c di p1 . Scegli r_c piccolo rispetto al raggio di sterzata previsto, ma grande rispetto allo scatter.
  3. Chiama questo cluster C1 .
  4. Trova punto q1 la media delle posizioni in C1 .
  5. Adatta una linea ai punti in C1 e proietta (o appena oltre) il bordo del cluster e trova il punto più vicino nei dati originali. Etichetta quel punto p2 .
  6. Esegue i passaggi da 2 a 5 fino a quando non si esauriscono i dati.

Ora hai un nuovo elenco di punti q1 .. qn che sono stati ordinati.

In cima alla mia testa, molto ruvido, e funziona solo in condizioni piuttosto buone ...


Il comportamento di auto-attraversamento può probabilmente essere migliorato richiedendo nel passaggio (5) che la nuova linea proiettata si trovi all'interno di un angolo massimo di quella precedente.

Il problema con la curva di Bezier è che in realtà non va se i punti che hai campionato e anche se i punti dei campioni sono leggermente distorti; la curva più bezier potrebbe effettivamente essere a miglia di distanza.

Un'approssimazione migliore e una soluzione che sembra assomigliare meglio all'immagine originale è un Catmull-Rom Spline perché corre attraverso tutti i punti della curva.

Il mio approccio sarebbe quello di ordinare prima il tuo elenco di punti, quindi utilizzare una curva più bezier.

Il trucco è ovviamente l'ordinamento. Inizia con un punto casuale e trova il punto più vicino. Supponiamo che questi due siano collegati. Con questi due punti finali, trova i punti più vicini a loro. Supponiamo che quello con la distanza minore rispetto al suo endpoint sia collegato a quel punto. Ripeti fino a quando tutti i punti sono collegati.

Presumo che ci siano ancora dei problemi con questo approccio, ma forse puoi usarlo come punto di partenza (gioco di parole).

Modifica: puoi farlo più volte con diversi punti di partenza, quindi vedere dove i risultati differiscono. Questo almeno ti dà un po 'di fiducia, quali punti sono collegati tra loro.

Un approccio completamente diverso, che non richiede un altro vincolo, ma i dettagli potrebbero dipendere dall'applicazione. Funzionerebbe meglio se hai una & Quot; densa nuvola di punti & Quot; attorno al percorso.

Usa un " costo " funzione che definisce la differenza tra la curva e la nuvola di punti. Utilizzare una curva parametrizzata e un algoritmo di ottimizzazione standard. - O - Inizia con una curva dritta dall'inizio alla fine, quindi usa un algoritmo genetico per modificarlo.

La tipica funzione di costo sarebbe quella di prendere la distanza minima tra ciascun punto e la curva e sommare i quadrati.

Non ho abbastanza esperienza per suggerire un'ottimizzazione o un algoritmo genetico, ma sono sicuro che può essere fatto :)

Potrei immaginare un algoritmo genetico come segue: Il percorso sarà creato da Waypoint. Inizia mettendo N punti intermedi in una linea retta dall'inizio alla fine. (N può essere scelto in base al problema). Le mutazioni potrebbero essere:

  1. Per ogni segmento, se rnd () < x, viene introdotto un nuovo waypoint nel mezzo.
  2. Per ciascun waypoint, le coordinate X e Y sono leggermente modificate.

Dovrai includere la lunghezza totale nella funzione di costo. La suddivisione potrebbe non essere necessaria o forse x (la & Quot; possibilità di suddivisione & Quot;) potrebbe dover diminuire quando vengono introdotti più waypoint. È possibile che si desideri applicare (2) l'inizio e l'endpoint.

Sarebbe divertente provarlo ...

Prendo che " lista non ordinata " significa che mentre il tuo set di punti è completo, non sai in quale ordine sono stati percorsi?

Il rumore gaussiano deve essere sostanzialmente ignorato. Non ci viene data assolutamente alcuna informazione che ci consenta di fare qualsiasi tentativo di ricostruire il percorso originale e non rumoroso. Quindi penso che il meglio che possiamo fare sia supporre che i punti siano corretti.

A questo punto, l'attività consiste in " trova il percorso migliore attraverso una serie di punti " ;, con " best " lasciato vago. Ho preparato un codice che tenta di ordinare una serie di punti nello spazio euclideo, preferendo ordini che si traducono in linee più dritte. Mentre la metrica era facile da implementare, non riuscivo a pensare a un buon modo per migliorare l'ordinamento basato su quello, quindi ho semplicemente scambiato casualmente i punti in cerca di una migliore disposizione.

Quindi, ecco un codice dello schema PLT che lo fa.

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

Sembra che tu conosca la 'curva d'oro' dalle tue risposte alle domande, suggerirei di trovare la curva di Bezier della 'curva d'oro' come suggerito da @jamesh e disegnarla.

Quanti punti hai?
Una curva di Bezier, come detto, è una buona idea se hai comparativamente pochi punti. Se hai molti punti, costruisci i cluster come suggerito da dmckee.

Tuttavia anche hai bisogno di un altro vincolo per definire l'ordine dei punti. Ci sono stati molti buoni suggerimenti su come scegliere i punti, ma a meno che tu non introduca un altro vincolo, tutti offrono una possibile soluzione.

Possibili vincoli a cui posso pensare:

  • percorso più breve
  • segmenti più diritti
  • rotazione totale minima
  • preferenza direzionale (ovvero orizzontale / verticale è più probabile dell'incrocio)

In tutti i casi, per soddisfare il vincolo è probabilmente necessario testare tutte le permutazioni della sequenza. Se inizi con un & Quot; buona ipotesi & Quot; puoi terminare rapidamente gli altri.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top