Hace 20 años, cuando diseñaba un SIG de escritorio, me planteé exactamente esta cuestión. Necesitábamos encontrar distancias punto a punto de forma interactiva; nuestro objetivo era hacer los cálculos en menos de 1/2 segundo para miles de puntos. Las pruebas (¡en un PC 486 de 25 MHz!) demostraron que podíamos calcular todas las distancias, exactamente como describes (con el sencillo algoritmo obvio), tan rápido que no tenía sentido crear una solución más sofisticada, como una estructura de árbol cuádruple.
Para calcular distancias a un único punto "sonda", sus opciones incluyen (a) proyectar todos los puntos utilizando una proyección equidistante centrada en el punto sonda o (b) adoptar un modelo terrestre esférico y utilizar la proyección Fórmula Haversine . El primero es apropiado si se necesita la precisión de un modelo elipsoidal. En cualquier caso, los cálculos son razonablemente rápidos, probablemente menos de 1.000 ticks: se podría consultar alrededor de un millón de puntos por segundo con un solo procesador.
¿Suficientemente rápido para ti? Si no, el método de fuerza bruta se paraleliza fácilmente y escala directamente con el número de procesadores: basta con dividir los puntos entre los procesadores y luego hacer una comparación final del más cercano encontrado por cada procesador.
Si necesitas ir más rápido, puedes utilizar varias aproximaciones a los puntos de la pantalla. Por ejemplo, si se encuentra entre -88 y +88 grados de latitud y el punto más cercano encontrado hasta el momento está a 200 km, es imposible que cualquier punto cuya latitud difiera de la del punto sonda en más de 2 grados esté más cerca (porque en cualquier lugar de la Tierra, un grado de latitud supera unos 110 km). En muchos casos, este tipo de preselección puede permitir procesar cientos de millones de puntos por segundo.
