Qual a melhor forma de procurar a latitude e longitude mais proxima em um array de 150mil posições ? (node)

Para lidar com essa situação de maneira eficiente, a melhor abordagem é utilizar índices R-tree, que são estruturas de dados otimizadas para consultas espaciais, como a busca de pontos mais próximos. No entanto, a maneira mais prática e performática de fazer isso é utilizar uma base de dados geográfica especializada, como o PostGIS.

Com o PostGIS, você pode armazenar suas cidades com suas coordenadas geográficas e, em seguida, realizar consultas espaciais extremamente eficientes usando SQL. Um exemplo de consulta que encontra a cidade mais próxima de uma determinada coordenada seria algo assim:

SELECT name, ST_Distance(geog::geography, ST_MakePoint(lon, lat)::geography) AS distance
FROM cities
ORDER BY distance
LIMIT 1;

Nesse caso, geog seria uma coluna que contém os pontos geográficos das cidades. O ST_MakePoint cria um ponto a partir das coordenadas fornecidas, e o ST_Distance calcula a distância entre esse ponto e as cidades armazenadas. Essa consulta além de ser trivial é otimizada automaticamente pela indexação espacial!

Portanto, a melhor solução é evitar tentar implementar isso em Node.js e, ao invés disso, confiar em uma base de dados que já é otimizada para esse tipo de operação, como o PostGIS ou outras solucões similares!

Não tem condições de realizar esse tipo de busca sem otimizar a estrutura de dados antes, eu pensaria em uma forma de criar algum cluster de regiões maiores e ficar medindo com base nela tipo alguma estrutura de árvore mas sem conhecer o que você tem a disposição fica dificil

Como falaram, para conseguir fazeru buscas mais rápidas, você vai precisar mudar a estrutura de dados que você salva os dados, e para isso vai ter um pré processamento para criar essa estrutura nova.

Se for er que fazer muitas queries desse tipo, faz sentido fazer esse pré processamento, se forem poucas queries, uma busca linear já resolve seu problema

Agora, vamos falar sobre os algoritmos a serem utilizados.

Não sou expert em geometria computacional, que é a área da computação que estuda problemas desse tipo, mas existem tipos de árvores específicas para esse problema, e os algoritmos podem ficar complexos. Recomendo dar uma olhada nessa página da wikipedia https://en.wikipedia.org/wiki/Nearest_neighbor_search#Space_partitioning e nessa resposta do Stack Overflow https://stackoverflow.com/a/1901885

Como você está usando node, imagino que alguma biblioteca no NPM com esses algoritmos já resolvam, dá uma olhada em https://www.npmjs.com/search?q=nearest+neighbor, mas lembra que no seu caso o cálculo da distância não é a distância euclidiana, esse cálculo envolve cálculos trigonométricos, e a biblioteca tem que levar isso em conta ou ser flexível para você poder criar a função de distância que vc queira.

Bônus:
O chat GPT ainda deu essas sugestôes:

Árvore KD (k-dimensional tree): Uma estrutura de dados comum para problemas de nearest neighbor search é a árvore KD. Ela divide os dados em uma estrutura de árvore binária, permitindo que você faça buscas mais rápidas do que uma busca linear. No caso de coordenadas geográficas, essa árvore pode ser ajustada para trabalhar com distâncias geográficas (não euclidianas). Há implementações em Node.js, como a kd-tree-javascript que você pode personalizar para usar a função de Haversine.

2. Bibliotecas Node.js:

turf.js: Embora você já esteja usando o turf, que é excelente para cálculos geoespaciais, você pode combiná-lo com uma estrutura de dados mais eficiente como as mencionadas acima. Há também o módulo turf.nearestPoint que pode ser usado se os pontos estiverem pré-processados.

geokdbush: Outra biblioteca recomendada é o geokdbush, que combina uma árvore KD com uma implementação otimizada para buscas de nearest neighbor em coordenadas geográficas. Ele usa flatbush para indexação espacial e é muito rápido.