Estoy buscando un algoritmo rápido que encuentre el punto más cercano de un segmento de línea en un gráfico (como una red de carreteras) a mi punto de prueba.
Intentaré ser más específico. Tengo un gráfico de red de carreteras. Puede tener alrededor de 30 millones de nodos y enlaces/líneas (mi conjunto de datos de Estados Unidos es de este tamaño). Ya tengo un algoritmo de enrutamiento rápido en funcionamiento, pero funciona de nodo a nodo. El mundo real no funciona con nodos, sino con coordenadas. Podría buscar el nodo más cercano a cada coordenada de inicio/final, y en el pasado he codificado un algoritmo de coincidencia de coordenadas muy rápido (unos cuantos millones de nodos, y gestionando >~1000 puntos de prueba por segundo).
Los algoritmos de enrutamiento comerciales no funcionan así: Te dirigen al segmento de carretera más cercano. En otras palabras, necesito hacer coincidir una coordenada con la línea más cercana (enlace gráfico). Además de encontrar la línea más cercana, necesito una fracción que me diga a qué distancia de la línea está ese punto más cercano. Entonces puedo hacer la ruta desde el nodo más cercano y añadir la línea fraccionaria a la suma de distancia/tiempo. O corregir en consecuencia si la ruta pasa por la línea.
Creo que es razonable tener un límite en la distancia máxima de búsqueda. Por ejemplo, "La línea más cercana que esté a menos de 500 metros". Y esto debería ayudar a podar el espacio de búsqueda.
Codificar un algoritmo que busque todas estas líneas es bastante sencillo, pero sería lento debido al gran número de líneas y a los cálculos de geometría. Podría limitar la búsqueda a aquellas líneas que estén dentro del límite de distancia. Y esto podría optimizarse aún más ordenando las líneas por longitud (digamos). Por supuesto, la mayoría de las líneas tienen una "anchura" de longitud fina, lo que complica esa ordenación y búsqueda.
Sigo pensando que esto será lento. ¿Cómo lo hacen los paquetes comerciales? La mayoría de ellos encuentran y muestran una ruta en medio segundo, más o menos, y la mayor parte de ese tiempo se dedica al algoritmo principal de enrutamiento y a la construcción del resultado (derivando las direcciones de los giros, etc.).
Hay una serie de preguntas similares en este sitio (por ejemplo ¿Cómo encontrar el punto más cercano proyectado en la red de carreteras? ) pero estos se refieren a paquetes específicos como PostGIS o ArcGIS. Estoy buscando un algoritmo real para codificar yo mismo. Sospecho que mi principal problema es conocer las palabras/frases a buscar. Una vez que haya encontrado el nombre de un algoritmo, entonces un poco de Google/etc. encontrará rápidamente todo tipo de algoritmos y documentos...
