Algorithme pour trouver le point le plus proche

J'ai une liste de quelques centaines de villes avec leur latitude / longitude. Étant donné un autre emplacement (également en lat / long), je dois trouver la ville la plus proche.

Comme je n'utilise aucun SIG, l'algorithme évident consiste maintenant à faire une boucle pour toutes les villes, en calculant la distance entre les points.

Faire la boucle est réalisable pour moi, mais existe-t-il un algorithme facile à implémenter pour y parvenir plus efficacement? Ou une bibliothèque Java légère qui peut aider à résoudre ce problème?

Notes : Je n'ai pas besoin / je veux une solution SIG complète ou une bibliothèque lourde / compliquée. Je préfère une solution moins bonne mais plus simple et plus légère car c'est la seule chose que je dois résoudre.

J'ai étudié exactement cette question il y a 20 ans lors de la conception d'un SIG de bureau. Nous devions trouver des distances point à point de manière interactive; notre objectif était de faire les calculs en moins de 1/2 seconde pour des milliers de points. Les tests (sur un PC 256 486!) Ont montré que nous pouvions calculer toutes les distances, exactement comme vous le décrivez (avec l'algorithme simple évident), si rapidement qu'il n'était pas logique de créer une solution plus sophistiquée, telle qu'une structure à quatre arbres .

Pour calculer les distances vers un seul point "sonde", vos options incluent (a) la projection de tous les points à l'aide d'une projection équidistante centrée au point de sonde ou (b) l'adoption d'un modèle de terre sphérique et l'utilisation de la formule Haversine . La première est appropriée si vous avez besoin de la précision d'un modèle ellipsoïdal. Dans les deux cas, les calculs sont raisonnablement rapides, prenant probablement moins de 1000 ticks: vous pouvez interroger environ un million de points par seconde avec un seul processeur.

Assez rapide pour vous? Sinon, la méthode de force brute se parallélise facilement et évolue directement avec le nombre de processeurs: il suffit de diviser les points entre les processeurs et de faire une comparaison finale du plus proche trouvé par chaque processeur.

Si vous devez aller plus vite, vous pouvez utiliser diverses approximations pour filtrer les points. Par exemple, si vous êtes entre -88 et +88 degrés de latitude et que le point le plus proche trouvé jusqu'à présent est à 200 km, aucun point dont la latitude diffère de plus de 2 degrés de la latitude du point de sonde ne peut être plus proche (car n'importe où sur Terre, un degré de latitude dépasse environ 110 km). Dans de nombreux cas, ce type de présélection peut vous permettre de traiter des centaines de millions de points par seconde.

Je suis d'accord avec d'autres pour dire qu'une simple boucle devrait être efficace pour "quelques centaines de villes".

Compte tenu de votre application, la gestion des distances ellipsoïdales est probablement une surpuissance majeure - vous avez probablement affaire à des prévisions météorologiques dont la localité n'est guère plus basse que quelques mètres. La géométrie sphérique est suffisamment simple pour que vous puissiez facilement le faire dans votre boucle.

Cela pourrait être encore plus simple (par exemple, utilisez delta lat comme y et delta lon * cos (lat) comme x et trouvez le minimum x ^ 2 + y ^ 2). Vous utilisez le cosinus de la latitude cible, que vous ne calculez qu'une seule fois. Ce sera de plus en plus inexact pour les villes éloignées, mais elles seront rejetées de toute façon, alors peu importe. En supposant que votre ville la plus proche se trouve généralement à quelques centaines de kilomètres, les chances qu'un résultat différent (ville la plus proche) utilise ceci vs en utilisant une formule plus précise sont assez petites et ne se produiraient que lorsque les différences sont suffisamment petites pour que "quelle prévision soit plus précis "dépendrait de toute façon d’autres facteurs (c.-à-d. perte dans le bruit).

À moins que vous n'utilisiez un système intégré ou un interpréteur lent, vous pouvez probablement vous permettre d'utiliser simplement les formels sphériques que d'autres suggèrent, cependant.

Cela s'ajoute à ce qui a déjà été dit, mais j'ai pensé noter l'importance de choisir une structure de données appropriée. J'ai écrit mon propre code pour une fonction K dans .NET et j'ai constaté que l'utilisation de collections efficaces accélérait considérablement les choses. Désolé, je ne connais pas la notation O pour les vitesses exactes. J'ai utilisé deux dictionnaires pour les coordonnées x et y avec l'ID du point comme clé. Je ne connais pas Java, donc je ne pouvais rien suggérer.

À la vôtre, David