Question

J'ai une liste non triée de points X, Y bruyants. Ils forment cependant un chemin à travers le monde. J'aimerais qu'un algorithme trace une approximation de ces données en utilisant des segments de droite.

Ceci est similaire à la manière dont vous utiliseriez un algorithme d'adaptation de ligne pour choisir une approximation de données linéaires. Mon problème n’est que plus dur car le chemin tourne et s’enroule autour du monde. alt text http://www.praeclarum.org/so/pathfinder.png

Est-ce que quelqu'un connaît des algorithmes standard / robustes / faciles à comprendre pour y parvenir?

Q & amp; A :

Qu'entendez-vous par bruit? Si j'avais une réalisation idéale du chemin, mon ensemble de points serait échantillonné à partir de ce chemin idéal avec un bruit gaussien ajouté aux éléments X et Y. Je ne connais pas la moyenne ou l'écart type de ce bruit. Je peux peut-être deviner le dev std ...

Les points se trouvent-ils près, mais pas sur, d'un chemin idéal mais compliqué que vous souhaitez approcher? Oui.

Avez-vous des informations à priori sur la forme du chemin? N'importe quel autre moyen d'obtenir de telles informations? Malheureusement, pas.

Était-ce utile?

La solution

Avec une liste non triée, vous ne saurez pas vraiment quels points inclure dans chaque segment, alors je suppose que vous pouvez simplement choisir le point le plus proche.

Une solution pourrait être de choisir un point de départ au hasard et de choisir le point le plus proche comme point suivant de chaque étape. Ajoutez les deux premiers points à un ensemble S.

Ajustez une ligne aux points de S jusqu'à ce que le RMS dépasse une valeur, puis supprimez S et commencez une nouvelle ligne.

L’intersection de lignes consécutives serait le point final des segments.

Autres conseils

L'interpolation de Bézier pourrait vous convenir.

Interpolation de Bézier

Toutefois, cela ne concerne pas l’ordre des points dans un chemin; plusieurs approches sont à considérer:

  • Tout "ient optimal " type de chemin (par exemple, le plus petit changement de direction à chaque point du chemin, * le chemin le plus court passant par tous les points) résultera probablement en une NP complète Problème concernant le vendeur itinérant (TSP).
  • Un " raisonnable " chemin pour regrouper les nœuds, puis acheminer entre les grappes et au sein de grappes. Bien sûr, plus le cluster est grand ou plus le nombre de clusters est grand, plus ce petit problème ressemble à un grand TSP.
  • Classement des points par un axe. S'il existe beaucoup plus que 2 axes, une stratégie de réduction dimensionnelle peut être utile. par exemple. Analyse en composantes indépendantes.

Si vos points sont proches les uns des autres, vous pouvez normalement & "straight &"; lignes (lignes orthogonales). Utilisation des algorithmes de lissage normaux . Vous pouvez voir le monde comme étant plat.

S'ils sont éloignés les uns des autres, vous devez compenser l'arrondi de la Terre en utilisant grands cercles pour naviguer d'un point à l'autre. Sinon, vos lignes droites seront plus longues.

Vous choisissez si un point est trop éloigné pour créer des lignes droites.

De plus, vous devez savoir si vous devez & "visiter &"; chaque point, ou juste besoin d'aller près, et comment près de ce près est.

Si vous devez envoyer le ou les cours à un avion, un bateau ou un autre voyageur, vous devrez probablement vous rendre à chaque point. Si vous obtenez les données GPS d'un objet, vous souhaitez probablement simplement tracer un parcours sur un écran et supprimer le bruit.

Après avoir vu vos modifications: S'il s'agit d'un objet déplaçant une trajectoire que vous souhaitez tracer, vous pouvez adoucir la direction et la vitesse au lieu des valeurs x / y. (Si vos valeurs mesurées (x) ont un intervalle Y fixe et croissant, le lissage est beaucoup plus facile.)

Voici un hack heuristique qui pourrait résoudre le problème de classement des données, si

  • vous avez assez de points
  • la distance moyenne entre les points est faible par rapport au plus petit rayon de courbure attendu du trajet
  • la distance moyenne entre les points n’est pas grande comparée au std. dev. du bruit
  • le chemin ne se croise pas (vous pourriez avoir de la chance, mais aucune garantie)

Procédez comme ceci:

  1. Choisissez un moyen de départ ( p1 ).
  2. Recherchez tous les points situés à une certaine distance de regroupement, r_c sur p1 . Choisissez r_c faible par rapport au rayon de braquage attendu, mais large par rapport à la dispersion.
  3. Appelez ce cluster C1 .
  4. Trouver le point q1 sur la moyenne des positions dans C1 .
  5. Ajustez une ligne aux points de C1 , projetez-le sur le bord du cluster (ou juste au-delà de celui-ci) et recherchez le point le plus proche dans vos données d'origine. Identifiez ce point p2 .
  6. Répétez les étapes 2 à 5 jusqu'à ce que vous manquiez de données.

Vous avez maintenant une nouvelle liste de points q1 .. qn commandés.

De manière très agitée, je ne travaille que dans de très bonnes conditions ...

Le comportement d'auto-croisement peut probablement être amélioré en exigeant à l'étape (5) que la nouvelle ligne projetée se situe dans un angle maximal de l'angle précédent.

Le problème avec la courbe de Bézier est qu’il n’y a pas lieu de passer par les points que vous avez échantillonnés et même si les échantillons de points sont légèrement déformés; la courbe de Bézier pourrait en réalité être à des kilomètres.

Une meilleure approximation et une solution qui semble mieux ressembler à l'image d'origine est un Catmull-Rom Spline , car il exécute tous les points de la courbe.

Mon approche serait d’abord de trier votre liste de points, puis d’utiliser une courbe de Bézier.

Le truc est bien sûr le tri. Commencez avec un point aléatoire et trouvez le point le plus proche. Supposons que ces deux sont connectés. Avec ces deux extrémités, recherchez les points les plus proches d’eux. Supposons que celui dont la distance est inférieure à son extrémité est connecté à ce point. Répétez l'opération jusqu'à ce que tous les points soient connectés.

Je suppose que cette approche pose encore quelques problèmes, mais vous pouvez peut-être vous en servir comme point de départ (jeu de mots).

Modifier: vous pouvez le faire plusieurs fois avec différents points de départ, puis voir où les résultats diffèrent. Cela vous donne au moins une certaine confiance, quels points sont connectés les uns aux autres.

Une approche complètement différente, qui ne nécessite aucune autre contrainte, mais les détails peuvent dépendre de votre application. Cela devrait fonctionner mieux si vous avez un & "Dense nuage de points &"; autour du chemin.

Utilisez un " coût " fonction qui définit la différence entre la courbe et le nuage de points. Utilisez une courbe paramétrée et un algorithme d'optimisation standard. - OU - Commencez par une courbe droite du début à la fin, puis utilisez un algorithme génétique pour la modifier.

La fonction de coût typique serait de prendre la plus petite distance entre chaque point et la courbe et d’additionner les carrés.

Je n'ai pas assez d'expérience pour suggérer une optimisation ou un algorithme génétique, mais je suis sûr que cela peut être fait:)

Je pourrais imaginer un algorithme génétique comme suit: Le chemin sera construit à partir de points de cheminement. Commencez par placer N points de route dans une ligne droite du début à la fin. (N peut être choisi en fonction du problème). Les mutations pourraient être:

  1. Pour chaque segment, si rnd () < x, un nouveau waypoint est introduit au milieu.
  2. Pour chaque point de cheminement, les coordonnées X et Y varient légèrement.

Vous devrez inclure la longueur totale dans la fonction de coût. La scission peut ne pas être nécessaire, ou peut-être que x (le & "; Chance divisée &";) Pourrait devoir diminuer à mesure que davantage de points de passage sont introduits. Vous pouvez ou non appliquer (2) au point de départ et au point final.

Ce serait amusant d'essayer ça ...

Je suppose que " liste non triée " Cela signifie que tant que votre ensemble de points est terminé, vous ne savez pas dans quel ordre ils ont été parcourus?

Le bruit gaussien doit être fondamentalement ignoré. Nous ne recevons absolument aucune information nous permettant de tenter de reconstruire le chemin d'origine, non bruyant. Je pense donc que le mieux que nous puissions faire est de supposer que les points sont corrects.

À ce stade, la tâche consiste à & "Trouver le meilleur chemin parmi un ensemble de points &"; avec & "Meilleur &"; laissé vague. J'ai fouillé dans le code qui tente de commander un ensemble de points dans l'espace euclidien, préférant les commandes qui ont pour résultat des lignes plus droites. Bien que la métrique soit facile à mettre en œuvre, je ne pouvais pas penser à un bon moyen d’améliorer la commande en fonction de cela, alors j’ai simplement échangé des points au hasard pour trouver un meilleur arrangement.

Donc, voici un code de schéma PLT qui le fait.

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

Il semble que vous connaissiez la "courbe en or" de vos réponses aux questions. Je suggérerais donc de trouver la courbe de Bézier de la "courbe en or" comme suggéré par @jamesh et de dessiner cela.

Combien de points avez-vous?
Une courbe de Bézier, comme mentionné, est une bonne idée si vous avez peu de points de comparaison. Si vous avez beaucoup de points, créez des clusters comme suggéré par dmckee.

Cependant, vous également avez besoin d'une autre contrainte pour définir l'ordre des points. Il y a eu beaucoup de bonnes suggestions sur la manière de choisir les points, mais à moins que vous n'introduisiez une autre contrainte, toutes les solutions possibles.

Contraintes possibles auxquelles je peux penser:

  • chemin le plus court
  • la plupart des segments droits
  • moins la rotation absolue totale
  • préférence directionnelle (c'est-à-dire horizontale / verticale est plus probable que les croisements)

Dans tous les cas, pour respecter la contrainte, vous devez probablement tester toutes les permutations de la séquence. Si vous commencez avec un & "Bon supposé &", Vous pouvez terminer les autres rapidement.

Licencié sous: CC-BY-SA avec attribution
Non affilié à StackOverflow
scroll top