Comment calculer les coordonnées les plus proches d'un point donné à partir d'une liste de coordonnées

Question

Fondamentalement, j'ai un emplacement actuel des utilisateurs. J'ai alors une liste de coordonnées.

Comment procéder pour calculer le jeu de coordonnées le plus proche de la liste par rapport à l'emplacement actuel de l'utilisateur. Mon application est écrit en java pour hthe plate-forme Android

Answer 1

http://developer.android.com/reference/android/location/Location.html

Location location = new Location(""); 
location.setLatitude(lat); 
location.setLongitude(lon); 

vérification des méthodes distanceTo ou distanceEntre.

Ou vous pouvez calculer manuellement la distance entre les coordonnées et trouver la plus petite distance pour calculer la distance, vous pouvez consulter le lien suivant http://www.zipcodeworld.com/samples/distance.java.html

Answer 2

Il y a un fossé et conquérir algorithme pour trouver la ferme paire de points dans O (nlogn). Bien que cela puisse être un peu exagéré pour la taille de votre ensemble de données. Plus d'infos sur ce here

Answer 3

Si des points sur la liste sont assez uniformément répartis dans la région, cela devrait fonctionner:

diviser la zone en quarts de cercle d'une certaine taille. Conservez et mettez à jour une liste de points qui résident dans chaque quadrant. Si vous avez une coordonnée x, trouvez le quadrant auquel elle appartient, calculez les distances uniquement pour les points du même quadrant (si vous n'y ajoutez pas de points des quadrants voisins, jusqu'au succès), choisissez k points les plus proches p_i.

Vérifiez si le cercle c (centre = x, rayon = max (p_i-x)) traverse tous les quadrants qui n'ont pas encore été vérifiés, et si c'est le cas, calculez les distances aux points de ces quadrants. Renvoie l'ensemble des k points les plus proches. Au lieu de sélectionner tous les quadrants dans un cercle c, vous pouvez vérifier les quadrants les plus proches dans c qui contiennent des points, jusqu'à ce que vous trouviez k points les plus proches p_i de sorte que tous les quadrants dans c (x, max (p_i-x)) sont vide ou vérifié. Accélérez la recherche de quadrant la plus proche de O (n) à O (log n): vous devez implémenter une structure arborescente: quadrants de 4 quadrants, etc. qui suit le nombre de points dans chaque quadrant. Lorsque les points bougent, mettez-le à jour (O (log)). Quoi qu'il en soit, pour 200 points c'est probablement une surcharge.

modifier: au lieu d'une "structure arborescente" il suffit d'utiliser la table de hachage et une fonction de hachage facile, comme: (x div 10^p, y div 10^p)