algoritmo eficiente para encontrar el punto más cercano en un gráfico que no tiene una ecuación conocida

Question

Estoy haciendo estas preguntas por curiosidad, ya que mi implementación rápida y sucia parece ser lo suficientemente buena. Sin embargo, tengo curiosidad por saber cuál sería una mejor implementación.

Tengo un gráfico de datos del mundo real. No hay valores duplicados de X y el valor de X se incrementa a una tasa constante en todo el gráfico, pero los datos de Y se basan en la salida del mundo real. Quiero encontrar el punto más cercano en el gráfico desde un punto dado arbitrario P programáticamente. Estoy tratando de encontrar un algoritmo eficiente (es decir, rápido) para hacer esto. No necesito el punto exacto más cercano, puedo conformarme con un punto que es "casi" el punto más cercano.

La solución diferida obvia es incrementar cada punto del gráfico, calcular la distancia y luego encontrar el mínimo de la distancia. Sin embargo, esto podría ser teóricamente lento para gráficos grandes; demasiado lento para lo que quiero.

Dado que solo necesito un punto aproximado aproximado, imagino que la ecuación más rápida ideal sería generar una línea de mejor ajuste y usar esa línea para calcular dónde debe estar el punto en tiempo real; pero eso suena como un potencial dolor de cabeza matemático que no voy a asumir.

Mi solución es un truco que funciona solo porque asumo que mi punto P no es arbitrario, es decir, supongo que P generalmente estará cerca de mi línea gráfica y cuando eso sucede puedo tachar los valores X distantes de consideración . Calculo cuán cerca está el punto en la línea que comparte la coordenada X con P y uso la distancia entre ese punto y P para calcular el valor X más grande/más pequeño que podría ser puntos más cercanos.

No puedo evitar sentir que debería haber un algoritmo más rápido que mi solución (que solo es útil porque supongo que el 99% del tiempo mi punto P ya estará cerca de la línea). Intenté buscar mejores algoritmos en Google, pero encontré tantos algoritmos que no encajaban que era difícil encontrar lo que estaba buscando entre todo el desorden de algoritmos inapropiados. Entonces, ¿alguien aquí tiene un algoritmo sugerido que sería más eficiente? Tenga en cuenta que no necesito un algoritmo completo, ya que lo que tengo funciona para mis necesidades, solo tengo curiosidad por saber cuál hubiera sido la solución adecuada.

Answer 1

Si puede utilizar una estructura de datos, algunas estructuras de datos comunes para la búsqueda espacial (incluyendo vecino más cercano) son ...

• en árbol cuádruple (y octree etc).
• kd-tree
• bsp árbol (solo es práctico para un conjunto estático de puntos).
• árbol R

El árbol R viene en un número de variantes. Está muy relacionado con el árbol B +, pero con (dependiendo de la variante) diferentes ordenamientos en los elementos (puntos) en los nodos de hoja.

El árbol Hilbert R utiliza un ordenamiento estricto de puntos basado en la curva de Hilbert. La curva de Hilbert (o más bien una generalización de la misma) es muy buena para ordenar datos multidimensionales, de modo que los puntos cercanos en el espacio suelen estar cerca en el orden lineal.

En principio, el pedido de Hilbert podría aplicarse ordenando una simple matriz de puntos. El agrupamiento natural en esto significaría que una búsqueda por lo general solo necesitaría buscar unos pocos tramos bastante cortos en el conjunto, con la complicación de que tiene que calcular qué tramos abarcan.

Solía ​​tener un enlace para un buen artículo sobre cómo hacer los cálculos de la curva Hilbert, pero lo he perdido. Un pedido basado en códigos Gray sería más simple, pero no tan eficiente en la agrupación. De hecho, hay una conexión profunda entre los códigos Gray y las curvas de Hilbert: ese papel que he perdido usa un poco las funciones relacionadas con el código Gray.

EDITAR - He encontrado que enlazan - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.133.7490

Answer 2

Digamos que su punto de P=(x,y) y los datos del mundo real es una función y=f(x)

Paso 1: Calcular r=|f(x)-y|.

Paso 2: Encontrar puntos en el intervalo de I=(x-r,x+r)

Paso 3: Encontrar el punto más cercano en I-P.

Answer 3

Si almacena los puntos [x, y] en un quadtree, podrá encontrar rápidamente el más cercano (algo así como O (log n)). Creo que es lo mejor que puedes hacer sin hacer suposiciones sobre dónde va a estar el punto. En lugar de repetir el algoritmo aquí, eche un vistazo a este link.

Su solución es bastante buena, al examinar cómo varían los puntos en y no se puede calcular un límite para el número de puntos a lo largo del eje x que necesita examinar en lugar de utilizar uno arbitrario.