Nombrar este algoritmo: Comparación y la interpolación de puntos?

Question

mi pregunta podría ser un poco extraño. He "desarrollado" un algoritmo y no sé si hay un algoritmo similar ya está ahí.

La situación: Tengo una pista definida por puntos (2D). Los puntos representan vueltas, por ejemplo. Entre los puntos de la pista sólo hay líneas rectas. Ahora me dan un conjunto de coordenadas en este espacio 2D. Calculo de la distancia desde el primer punto de la ruta a las nuevas coordenadas y la distancia para el intervalo de los dos primeros puntos de la pista. Si la distancia a las coordenadas medidas es más corta que la distancia desde la primera a la segunda punto de seguimiento, estoy suponiendo que este punto se encuentra entre este intervalo. entonces que hago una interpolación lineal en eso. Si es más grande, voy a comprobar con el siguiente intervalo.

Así que es básicamente tomar distancias de intervalo y tratando de encajar en ese país. Estoy tratando de localizar un objeto que se mueve aproximadamente a lo largo de este camino.

¿Le suena familiar a alguien? Alguien puede venir con una sugerencia para un algoritmo existente similar?

EDIT: Por lo que he dicho hasta aquí, quiero aclarar que una posición no se multiplicará asociada a los puntos de seguimiento. Considere la elaboración Jonathan hizo bien ASCII:

La posición X se encuentra que es dentro del segmento 1 y 2 (S12). Ahora la siguiente posición es Y, que es no debe considerarse lo suficientemente cerca para estar en S12. Voy a pasar a S23, y comprobar si está en.

Si se encuentra, no voy a estar revisando S12 para cualquier otro valor, porque he encontrado uno en el siguiente segmento ya. El algoritmo "no mira hacia atrás".

Pero si no encuentra el segmento de la derecha a partir de ahí, porque happenend a ser muy lejos del primer segmento, pero aún más lejos de cualquier otro segmento de todos modos, voy a dejar caer el valor y la siguiente posición se ser mirado para atrás en S12, de nuevo.

El bucle todavía sigue siendo un problema. Considero que tengo Y para S23 y pase dos o tres posiciones (ya que son demasiado lejos), podía perder la pista. Pude determinar una posición en S34 donde sería ya estar en S56.

Tal vez pueda llegar a alguna velocidad media a Våge dice en qué segmento debe ser.

Parece más grandes son los segmentos son, mayor es la oportunidad de hacer una decisión correcta.

Answer 1

Lo que me preocupa sobre el algoritmo que has descrito es que es 'codicioso' y podría elegir el segmento de 'equivocado' pista (o, al menos, un segmento de vía que no es la más cercana al punto).

Es hora de impulsar el arte ASCII a los límites. Tenga en cuenta la ruta de acceso siguiente (los números representan la secuencia en la lista de puntos de la pista), y la coordenada X (y, más tarde, Y).

    1-------------2
                  |
                  |    Y
                X |
            5-----+-----6
            |     |
            |     |
            4-----3

¿Cómo se supone que vamos a interpretar su descripción?

  

[C] alculate la distancia desde el primer punto de la pista a las nuevas coordenadas y la distancia para el intervalo para los dos primeros puntos de la pista. Si la distancia a las coordenadas medidas es más corta que la distancia desde la primera a la segunda punto de seguimiento, [suponer] que este punto se encuentra en el medio de este intervalo; [...] [s] i que es más grande, [...] consulte con el siguiente intervalo.

Creo que significa la primera frase:

• calcular la distancia desde TP1 (punto de pista 1) a TP2 - llamarlo D12
.
• calcular la distancia desde TP1 a X (llamarlo D1X) y desde TP2 a X (llamarlo D2X).

La parte difícil es la interpretación de la sentencia condicional.

Mi impresión es que si cualquiera de D1X o D2X es inferior a D12, entonces X se supone que en (o más cercano también) el TP1 segmento de pista a TP2 (llamarlo segmento S12).

En cuanto a la posición de X en el diagrama, es moderadamente claro que tanto D1X y D2X son más pequeños que D12, por lo que mi interpretación de su algoritmo de interpretaría X como asociadas con S12, sin embargo, X es claramente más cerca de S23 o S56 de lo que es a S12 (pero los que se descartan sin ni siquiera ser considerado).

¿He entendido bien algo acerca de su algoritmo?

Pensando en ello un poco: lo que he interpretado en el sentido de que su algoritmo es que si el punto X se encuentra dentro del círculo, ya sea de D12 radio con centro en TP1 o el círculo de radio con centro en D12 TP2, entonces X asociado con S12. Sin embargo, si además tenemos en cuenta el punto Y, el algoritmo que sugieren que está utilizando también se asocian con S12.

Si el algoritmo se refina decir MAX(D1Y, D2Y) < D12, entonces no se considera Y por estar relacionados con S12. Sin embargo, X es, probablemente, todavía se considera estar relacionado con S12 en lugar de S23 o S56.

Answer 2

La primera parte de este algoritmo me recuerda a moverse a través de un espacio discretizado. Un ejemplo de representación de un espacio de este tipo es el orden Z de relleno del espacio curva. He usado esta técnica para representar un quadtree , la estructura de datos para un malla adaptativa código de refinamiento una vez trabajé en, y se utiliza un algoritmo muy parecida a la que usted describe para atravesar la red y determinar las distancias entre las partículas.

La similitud puede no ser inmediatamente evidente. Dado que usted es sólo se preocupa por los lugares de intervalo, se está tratando de manera efectiva todos los puntos del intervalo como equivalentes en este paso. Esto es lo mismo que elegir un espacio que sólo tiene puntos discretizados -. Usted es efectivamente 'romperse' sus puntos para una cuadrícula