Je voudrais construire une application qui va vous donner le restaurant le plus proche en fonction de votre emplacement. Nous avons une base de données avec tous les POI correspondant au restaurant et nous allons obtenir votre position avec le GPS de votre téléphone ...Qu'est-ce qu'un bon algorithme pour le problème du plus proche voisin en deux dimensions?
Quel algorithme serait approprié? Où puis-je trouver un bon document à ce sujet?
Merci
Voici une présentation informative: http://dimacs.rutgers.edu/Workshops/MiningTutorial/pindyk-slides.ppt
Je recourraient soit un Quadtree ou Kd-tree.
Voir ici quelques repères: http://www.flegg.net/brett/pubs/spatial/index.html. Tout dépend vraiment de la taille et de la portée de vos données.
Le principal problème est de savoir comment stocker et rechercher les données. Si vous utilisez une base de données SQL qui ne prend pas en charge les index spatiaux (disons SQLite sur Android), envisagez de convertir les données spatiales à une courbe linéaire Z-order. L'algorithme est simple, je connais (bien, écrit) this l'implémentation.
C'est le code impressionnant Thomas, chapeau! –
Faire des requêtes de voisin le plus proche sur une grande base de données ne semble pas être une bonne chose à faire directement sur Android de toute façon. Le serveur de base de données est là pour soulever des charges lourdes comme ça en premier lieu. –
@Tim Je suis d'accord Z-order n'est pas génial pour une grande base de données. D'ailleurs, depuis ma réponse en 2010, je l'ai mis en place un [R-Tree] (http://h2database.com/html/mvstore.html#r_tree) qui devrait permettre des requêtes efficaces du plus proche voisin (une fois que ce mis en œuvre) et devrait aussi fonctionner sur Android. Mais il n'utilise pas SQLite. –