Pregunta

Tengo una lista sin clasificar de ruidosos puntos X, Y. Sin embargo, forman un camino a través del mundo. Me gustaría que un algoritmo dibuje una aproximación de estos datos usando segmentos de línea.

Esto es similar a cómo usaría un algoritmo de ajuste de línea para elegir una aproximación de datos lineales. Mi problema es aún más difícil porque el camino se dobla y vuela alrededor del mundo. texto alternativo http://www.praeclarum.org/so/pathfinder.png

¿Alguien sabe de algún algoritmo estándar / robusto / fácil de comprender para lograr esto?

Q & amp; A :

¿Qué quiere decir con ruido? Si tuviera una realización ideal de la ruta, mi conjunto de puntos se muestrearía desde esa ruta ideal con ruido gaussiano agregado a los elementos X e Y. No sé la desviación media o estándar de ese ruido. Tal vez pueda adivinar el desarrollo estándar ...

¿Los puntos se encuentran cerca, pero no en alguna, ruta ideal pero complicada que busca aproximar? Sí.

¿Tiene alguna información a priori sobre la forma del camino? ¿Alguna otra forma de obtener dicha información? Desafortunadamente no.

¿Fue útil?

Solución

Con una lista sin ordenar, realmente no sabrá qué puntos incluir en cada segmento, así que supongo que podría ir con el punto más cercano.

Una forma podría ser elegir un punto de inicio al azar, y elegir el punto más cercano como el siguiente punto en cada paso. Agregue los primeros dos puntos a un conjunto S.

Ajuste una línea a los puntos en S hasta que el RMS exceda algún valor, luego borre S y comience una nueva línea.

La intersección de líneas consecutivas serían los puntos finales de los segmentos.

Otros consejos

La interpolación de Bezier puede adaptarse a su problema.

Bezier Interpolation

Sin embargo, esto no aborda el orden de los puntos en una ruta; Hay una serie de enfoques a considerar:

  • Cualquier " óptimo " tipo de ruta (por ejemplo, el cambio de dirección más pequeño en cada punto de la ruta, * la ruta más corta a través de todos los puntos) probablemente reducirá el NP completo Problema de vendedor ambulante (TSP).
  • A " razonable " ruta para agrupar los nodos y luego enrutar entre grupos y dentro de grupos. Por supuesto, cuanto más grande es el clúster, o cuanto mayor es el número de clústeres, más se parece este pequeño problema a un gran n TSP.
  • Ordenar los puntos por un eje. Si hay más de 2 ejes, puede ser útil alguna estrategia reducción dimensional . p.ej. Análisis de componentes independientes.

Si sus puntos están cerca uno del otro, puede normal " straight " líneas (líneas ortogonales). Usando los algoritmos de suavizado normales. Puedes ver el mundo como plano.

Si están muy separados, debe compensar el redondeo de la tierra, utilizando grandes círculos para navegar de un punto a otro. De lo contrario, sus líneas rectas harán un camino más largo.

Es su elección si un punto está demasiado lejos para crear líneas rectas.

Además, debe saber si necesita " visite " cada punto, o simplemente necesita acercarse, y qué tan cerca está ese cerca.

Si necesita enviar el curso (s) a un avión, barco u otro viajero, probablemente necesite visitar cada punto. Si obtiene los datos de GPS de un objeto, probablemente solo desee trazar un curso en una pantalla y eliminar el ruido.


Después de ver sus ediciones: Si se trata de un objeto que mueve algún objeto que desea trazar, es posible que desee suavizar la dirección y la velocidad en lugar de los valores x / y. (Hacer que sus valores medidos (x) tengan un intervalo Y fijo y creciente hace que el suavizado sea mucho más fácil).

Aquí hay un truco heurístico que podría abordar el problema de pedido de los datos, si

  • tienes suficientes puntos
  • la distancia media entre puntos es pequeña en comparación con el radio de curvatura más pequeño esperado de la ruta
  • la distancia media entre puntos no es grande en comparación con el estándar. dev. del ruido
  • el camino no se cruza (puede que tengas suerte, pero no hay garantías)

Proceda así:

  1. Elija (con suerte por un medio significativo en lugar de aleatorio) un punto de partida, p1 .
  2. Encuentra todos los puntos que se encuentran dentro de una distancia de agrupamiento, r_c de p1 . Elija r_c pequeño en comparación con el radio de giro esperado, pero grande en comparación con la dispersión.
  3. Llame a este clúster C1 .
  4. Encuentre el punto q1 la media de las posiciones en C1 .
  5. Ajuste una línea a los puntos en C1 y proyecte (o más allá) el borde del clúster, y encuentre el punto más cercano en sus datos originales. Etiqueta ese punto p2 .
  6. Itere los pasos 2-5 hasta que se quede sin datos.

Ahora tiene una nueva lista de puntos q1 .. qn que están ordenados.

Fuera de mi cabeza, muy áspero, y solo funciona en condiciones bastante buenas ...


El comportamiento de autocruzamiento probablemente puede mejorarse si se requiere en el paso (5) que la nueva línea proyectada se encuentre dentro de un ángulo máximo del anterior.

El problema con la curva de Bezier es que en realidad no pasa por los puntos que ha muestreado y aunque las muestras de puntos están ligeramente distorsionadas; la curva de Bezier podría estar a kilómetros de distancia.

Una mejor aproximación y una solución que parece parecerse mucho mejor a la imagen original es un Catmull-Rom Spline porque corre a través de todos los puntos de la curva.

Mi enfoque sería primero ordenar su lista de puntos, luego usar una curva bezier.

El truco es, por supuesto, la clasificación. Comience con un punto aleatorio y encuentre el punto más cercano. Suponga que estos dos están conectados. Con esos dos puntos finales, encuentre los puntos más cercanos a ellos. Suponga que el que tiene la menor distancia a su punto final está conectado a ese punto. Repita hasta que todos los puntos estén conectados.

Supongo que todavía hay algunos problemas con este enfoque, pero tal vez pueda usarlo como punto de partida (juego de palabras).

Editar: puede hacerlo varias veces con diferentes puntos de partida y luego ver dónde difieren los resultados. Eso al menos te da algo de confianza, qué puntos están conectados entre sí.

Un enfoque completamente diferente, que no requiere otra restricción, pero los detalles pueden depender de su aplicación. Debería funcionar mejor si tiene una & Quot; nube de puntos densa & Quot; alrededor del camino.

Use un " cost " función que define la diferencia entre la curva y la nube de puntos. Use una curva parametrizada y un algoritmo de optimización estándar. - O - Comience con una curva recta de principio a fin, luego use un algoritmo genético para modificarla.

La función de costo típica sería tomar la distancia más pequeña entre cada punto y la curva, y sumar los cuadrados.

No tengo suficiente experiencia para sugerir una optimización o algoritmo genético, pero estoy seguro de que se puede hacer :)

Podría imaginar un algoritmo genético de la siguiente manera: El camino se construirá a partir de Waypoints. Comience poniendo N puntos de ruta en una línea recta de principio a fin. (Se puede elegir N dependiendo del problema). Las mutaciones pueden ser:

  1. Para cada segmento, si rnd () < x, se introduce un nuevo waypoint en el medio.
  2. Para cada punto de referencia, las coordenadas X e Y varían ligeramente.

Deberá incluir la longitud total en la función de costo. Es posible que no sea necesario dividir, o tal vez x (& Quot; posibilidad de división & Quot;) podría necesitar disminuir a medida que se introducen más puntos de referencia. Es posible que desee aplicar (2) al punto inicial y final.

Sería divertido intentar eso ...

Supongo que " lista sin clasificar " significa que si bien su conjunto de puntos está completo, ¿no sabe en qué orden se recorrieron?

El ruido gaussiano tiene que ser básicamente ignorado. No tenemos absolutamente ninguna información que nos permita hacer ningún intento de reconstruir la ruta original y poco ruidosa. Así que creo que lo mejor que podemos hacer es asumir que los puntos son correctos.

En este punto, la tarea consiste en " encontrar la mejor ruta a través de un conjunto de puntos " ;, con " best " dejado vago Creé un código que intenta ordenar un conjunto de puntos en el espacio euclidiano, prefiriendo los pedidos que resultan en líneas más rectas. Si bien la métrica fue fácil de implementar, no pude pensar en una buena manera de mejorar el orden basado en eso, por lo que simplemente intercambié puntos al azar en busca de una mejor disposición.

Entonces, aquí hay un código de esquema PLT que hace eso.

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

Parece que conoce la 'curva dorada' de sus respuestas a las preguntas, sugeriría encontrar la curva Bezier de la 'curva dorada' como lo sugiere @jamesh y dibujar eso.

¿Cuántos puntos tienes?
Una curva de Bezier, como se mencionó, es una buena idea si tiene comparativamente pocos puntos. Si tiene muchos puntos, cree clústeres como lo sugiere dmckee.

Sin embargo, también necesita otra restricción para definir el orden de los puntos. Ha habido muchas buenas sugerencias sobre cómo elegir los puntos, pero a menos que introduzca otra restricción, cualquiera da una posible solución.

Posibles restricciones que se me ocurren:

  • camino más corto
  • segmentos más rectos
  • menor rotación absoluta total
  • preferencia direccional (es decir, horizontal / vertical es más probable que entrecruzar)

En todos los casos, para cumplir con la restricción, probablemente necesite probar todas las permutaciones de la secuencia. Si comienza con un & "; Buena suposición &"; Puede terminar con los demás rápidamente.

Licenciado bajo: CC-BY-SA con atribución
No afiliado a StackOverflow
scroll top