Prochaine étape N Geo-Points les plus proches

Question

J'ai dans mon application android une table de base de données avec des géo-pointes (lat et lon sont des valeurs de degré décimal), environ 1000 points. Et je dois sélectionner 20 points le plus proche d'un point géo donné.

J'ai trouvé à Stackoverflow la réponse comment calculer la distance entre deux points de géo et était très heureux, jusqu'à ce que j'aie essayé d'écrire ma requête. J'ai découvert, qu'il n'est pas possible d'utiliser des fonctions trignométriques dans sqlite intégré d'android.

Mais alors j'ai une idée. Je n'ai pas vraiment besoin de calculer une distance. Le proche d'un point est à un autre la plus petite différence dans leurs coordonnées géographiques devrait être.

Comment pourrais-je utiliser ce fait? Serait-il suffisant de commander les points sauvegardés par (lat_0 - lat_n)^2 + (lon0-lon_n)^2, où lat_0 et lon_0 sont des coordonnées géographiques d'un point donné?

Merci,

Mur

UPD

Ainsi, la meilleure façon d'obtenir une réponse à ma question était de tester l'approche que je décris ci-dessus.

Cela fonctionne plutôt bien mais pas vraiment exactement par rapport à la distance exacte.

Donc, si vous avez juste besoin de calculer une distance, cette solution est correcte, mais dans mon cas, j'ai aussi besoin de commander des stations à distance et je n'ai pas pu utiliser cette solution.

Mes remerciements vont à John chez CashCommons et Philip. Merci les gars

Answer 1

Si vos points sont séparés dans une ville (plus ou moins), cette approximation fonctionnera correctement. L'approximation tombe en morceaux si vous allez dans le monde entier, cependant. Basé sur le commentaire de Philip ci-dessous, vous devez mettre à l'échelle l'un des composants. L'Allemagne est à environ 50 degrés de latitude nord, donc multiplier la longitude par (cos 50 deg) fera mieux.

Answer 2

Oui. :-) La distance réelle est sqrt ((lat_0 - lat_n)^2 + (lon0-lon_n)^2) mais la commande par (lat_0 - lat_n)^2 + (lon0-lon_n)^2 est suffisante.

Answer 3

Hmm ... Je ne suis pas sûr comment cette commande pourrait fonctionner? N'auriez-vous pas besoin d'un ordre différent pour chaque point pour indiquer qu'il est voisin.

La solution la plus simple consiste à parcourir simplement tous les points et à calculer le geometrical distance entre les points. Pour 1000 points cela devrait arriver assez rapidement.

La solution la plus optimisée (en termes de vitesse de récupération) consiste à calculer les voisins de chaque point lorsque vous les insérez dans la base de données. Par exemple, vous pouvez conserver la liste des ID en tant que chaîne séparée par une virgule et l'insérer dans la base de données. Ensuite, quand vous avez besoin de voisins, vous leur faites directement. Cependant, cela va devenir pénible si vous avez besoin d'insérer de nouveaux points. Fondamentalement, vous aurez besoin de re-calculer les voisins.