Como para determinar o caminho de barulhento X, Y dados

Question

Eu tenho uma lista não ordenada de X barulhento, pontos Y. Eles, no entanto, formam um caminho através do mundo. Eu gostaria de um algoritmo para desenhar uma aproximação destes dados usando segmentos de linha.

Esta é semelhante à forma como você usaria um algoritmo linha -fitting para escolher uma aproximação de dados linear. Meu problema é apenas mais difícil porque as curvas de caminho e ventos ao redor do mundo. alt texto http://www.praeclarum.org/so/pathfinder.png

Alguém sabe de quaisquer robustos fácil de compreender algoritmos padrão / / para alcançar este objetivo?

Q & A :

O que você quer dizer com barulhento? Se eu tivesse uma realização ideal do caminho, então o meu conjunto de pontos seria amostrado desse caminho ideal com o ruído Gaussian adicionado ao X e elementos Y. Eu não sei o desvio médio ou padrão de que o ruído. Eu posso ser capaz de adivinhar o std dev ...

Será que os pontos estão perto, mas não em, algum ideal, mas complicado caminho que você procura para se aproximar? Sim.

Você tem alguma informação a priori sobre ele forma do caminho? Qualquer outra forma de obter essa informação? Infelizmente não.

Answer 1

Com uma lista não ordenada, você realmente não vai saber quais os pontos a incluir em cada segmento, então eu acho que você poderia apenas ir com o ponto mais próximo.

Uma forma poderia ser a de escolher um ponto de partida de forma aleatória, e escolher o ponto mais próximo como o próximo ponto em cada etapa. Adicionar os dois primeiros pontos a um conjunto S.

Coloque uma linha para os pontos em S até que o RMS excede algum valor, S, em seguida, clara e iniciar uma nova linha.

A intersecção de linhas consecutivas seriam os pontos finais dos segmentos.

Answer 2

Bezier interpolação pode caber seu problema.

Esta não aborda a ordenação dos pontos em um caminho, no entanto; há uma série de abordagens a considerar:

• Qualquer tipo "ideal" do caminho (por exemplo, menor mudança de direção em cada ponto no caminho, * caminho mais curto através de todos os pontos) provavelmente vai se resumem a NP completa Problema do Caixeiro Viajante (TSP).
• Um caminho "razoável" para agrupar os nós e, em seguida, rota entre clusters, e dentro de clusters. É claro que, quanto maior o cluster, ou quanto maior o número de clusters mais este problema parece menor, como um grande n TSP.
• Como encomendar os pontos por um eixo. Se houver mais de 2 eixos, alguns estratégia redução dimensional pode ser útil. por exemplo. Análise de Componentes Independentes.

Answer 3

Se os seus pontos estão próximos uns dos outros, você pode linhas normais "retas" (linhas ortogonais). Usando normal suavização algoritmos . Você pode ver o mundo como sendo plana.

Se eles estão distantes, você precisa compensar o arredondamento da terra, usando grandes círculos para navegar de ponto a ponto. Caso contrário, suas linhas retas fará um caminho mais longo.

É sua escolha se um ponto está muito longe para criar linhas retas.

Além disso, você tem que saber se você precisa "visita" cada ponto, ou apenas necessidade de ir perto, e como perto daquele próximo é.

Se você precisa enviar o curso (s) para um avião, navio ou outro viajante, você provavelmente precisa visitar cada ponto. Se você obter os dados de GPS de um objeto, você provavelmente só quero traçar um curso em uma tela, e remover o ruído.

---

Depois de ver as suas edições: Se este é um objeto que se move alguns traject você quiser trama, você pode querer suavizar a direção e velocidade em vez dos X / valores y. (Fazendo seus valores medidos (x) tem um fixo e aumentando marcas Y-intervalo de alisamento muito mais fácil.)

Answer 4

Aqui é um hack heurística que pode resolver o problema de ordenação para os dados, se

• você tiver pontos suficientes
• a distância média entre os pontos é pequena em comparação com o menor raio de curvatura esperado do caminho
• a distância média entre os pontos não é grande em comparação com o std. dev. do ruído
• o caminho não é auto-crossing (você pode ter sorte, mas sem garantias)

Proceda assim:

1. Pick (espera-se por um significativo em vez de meios aleatórios) um ponto de partida, p1 .
2. Encontre todos os pontos que se encontram dentro de uma certa distância clustering, rc de p1 . Escolha rc pequeno em comparação com o raio de giro esperado, mas grande em comparação com a dispersão.
3. Chamada este cluster C1 .
4. Encontre ponto Q1 a média de posições em C1 .
5. Coloque uma linha para os pontos em C1 e projeto para (ou logo depois) da borda do cluster, e encontrar o ponto mais próximo em seus dados originais. Rotular esse ponto p2 .
6. Iterate os passos 2-5 até que você correr para fora de dados.

Agora você tem uma nova lista de pontos de Q1 .. qn que são ordenados.

Em cima da minha cabeça, muito áspero, e só funciona em condições boas bonitas ...

---

O comportamento de auto-cruzamento pode provavelmente ser melhorada exigindo que no passo (5) que o novo mentira linha projectada dentro de algum ângulo máximo de que a anterior.

Answer 5

O problema com a curva Bezier é que é na verdade não ir embora os pontos que você amostrados e mesmo que as amostras pontos são distorcidos um pouco; a curva de bezier pode realmente ser milhas ao largo.

Uma aproximação melhor, e uma solução que parece assemelhar-se a forma como a imagem original melhor é um Catmull-Rom Spline porque ele for executado embora todos os pontos da curva.

Answer 6

A minha abordagem seria primeiro ordenar sua lista de pontos, em seguida, usar uma curva de bezier.

O truque é, naturalmente, a ordenação. Comece com um ponto aleatório e encontrar o ponto mais próximo. Suponha estes dois estão ligados. Com esses dois pontos finais, encontrar os pontos mais próximos a eles. Suponha que aquele com a menor distância a ela do terminal está ligado a esse ponto. Repita até que todos os pontos são conectados.

Presumo que ainda existem alguns problemas com esta abordagem, mas talvez você possa usá-lo como ponto de partida (trocadilho intencional).

Editar: Você pode fazer isso várias vezes com diferentes pontos de partida, e depois ver onde os resultados são diferentes. Isso, pelo menos, dá-lhe alguma confiança, quais os pontos são conectados uns aos outros.

Answer 7

Uma abordagem completamente diferente, que não requer outro constrangimento, mas os detalhes podem depender de sua aplicação. Ele sghould funcionam melhor se você tem uma "densa nuvem de pontos" em torno do caminho.

Use uma função de "custo" que define a diferença entre a curva ea nuvem de pontos. Use uma curva parametrizada, e um algoritmo de otimização padrão. - OU - Comece com uma curva reta do início ao fim, em seguida, usar um algoritmo genético para modificá-lo.

A função de custo típico seria a de tomar a menor distância entre cada ponto ea curva, e somar os quadrados.

Eu tenho experiência não o suficiente para sugerir uma otimização ou algoritmo genético, mas tenho a certeza que pode ser feito:)

Eu poderia imaginar um algoritmo genético da seguinte forma: O caminho vai ser construída a partir de pontos de passagem. Comece com a colocação de waypoints N em uma linha straigt do início ao fim. (N pode ser escolhido dependendo do problema). As mutações podem ser:

1. Para cada segmento, se RND ()
2. Para cada ponto de passagem, o coordenadas X e Y são variar ligeiramente.

Você precisará incluir o comprimento total na função custo. Divisão pode não ser necessário, ou talvez x (o "acaso split") pode precisar diminuir à medida que mais waypoints são introduzidos. Você pode ou não pode querer aplicar (2) para o arranque e ponto final.

Seria divertido tentar que ...

Answer 8

Presumo que "lista não ordenada" significa que, enquanto o seu conjunto de pontos é completo, você não sabe o que ordem em que foram percorreu?

O ruído Gaussian tem de ser basicamente ignorada. Estamos dada absolutamente nenhuma informação que nos permite fazer qualquer tentativa de reconstruir o caminho original, un-barulhento. Então eu acho que o melhor que podemos fazer é assumir os pontos estão corretos.

Neste ponto, a tarefa consiste em "encontrar o melhor caminho através de um conjunto de pontos", com "melhor" deixado vago. Eu chicoteado até algum código que tentativas de encomendar um conjunto de pontos no espaço euclidiano, preferindo ordenações que resultam em linhas retas. Enquanto a métrica foi fácil de implementar, eu não conseguia pensar em uma boa maneira de melhorar a ordenação com base nisso, então eu apenas aleatoriamente pontos de swap à procura de um acordo melhor.

Então, aqui está algum código PLT Scheme que faz isso.

#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

Parece que você sabe que a 'curva de ouro' de suas respostas às perguntas, gostaria de sugerir encontrar a curva Bezier da 'curva de ouro', como sugerido por @jamesh e desenhar isso.

Answer 10

Quantos pontos você tem?
A Bezier curva, como mencionado, é uma boa idéia se você tiver comparedly alguns pontos. Se você tem muitos pontos, buiding grupos como sugerido por dmckee.

No entanto, você também precisa de outro constrangimento para definir a ordem dos pontos. Houve muitas sugestões boas para como escolher os pontos, mas a menos que você introduzir um outro constrangimento, qualquer dá uma solução possível.

As restrições possíveis eu posso pensar de:

• caminho mais curto
• a maioria dos segmentos retos
• rotação absoluta menos totais
• preferência direccional (isto é, é horizontal / vertical mais provável do que entrecruzamento)

Em todos os casos, para atender a restrição você provavelmente precisará testar todas as permutações da sequência. Se você começar com um "bom palpite", você Cayn rescindir os outros rapidamente.