Algorithme - regrouper des emplacements sur la carte

Question

J'ai une liste de n emplacements, chacun étant constitué d'une latitude, d'une longitude et d'un horodatage. Ces emplacements seront épinglés sur la carte.

Cependant, il est nécessaire de regrouper les emplacements proches les uns des autres, l'emplacement le plus récemment modifié étant le centre, afin que la carte ne soit pas inondée par des broches.

Mes pensées initiales seraient:

1. Trier les emplacements par horodatage
2. Sélectionnez le dernier emplacement
3. Calculer la distance au dernier emplacement pour les emplacements n-1
4. Sélectionnez les emplacements dans le rayon, disons 5 km, puis les supprimer de la liste
5. Répétez les étapes 2 à 4

Cette méthode fonctionne mais elle est très inefficace. Le pire des cas serait ~ O (n^2).

Existe-t-il des algorithmes pour améliorer les performances?

Answer 1

Pour battre l'exécution quadratique, utilisez un index. Sur la latitude et la longitude, vous pouvez utiliser un arbre R, un arbre à billes, un arbre de couverture ou similaire, car un arbre kd fonctionne apparemment uniquement avec la distance euclidienne, pas avec la haversine.

Answer 2

J'ai une solution hacky pour vous qui pourrait fonctionner si vous êtes d'accord avec une réponse approximative.

Généralement les longitudes de latitude vont plusieurs plusieurs points décimaux comme (12.9877949,77.6095064). Vous ne pouvez maintenant sélectionner que quelques chiffres après les virgules et cela se situe généralement à quelques kilomètres. Comme 12.9877979,77.6095064 est plus proche de 12.9877949,77.6095064 donc si je prends seulement jusqu'à 2 points après la virgule tous les deux deviendront 12.98,77.60 maintenant je passe par la liste et choisis ceux avec la même valeur.

Cependant, cela ne fonctionnera pas si vous avez besoin de calcul très précis