Bonjour,

Je suis actuellement sur un algorithme pour le boulot et je me pose quelques questions par rapport à celui-ci sans vraiment trouver de réponse..

J'ai une API/Serveur en Go (Golang) et donc rélié à une base de donnée.

Ce serveur doit trouver tout les smartphones avec mon application les plus proches de lui.

Dans la logique, je pense que mon application doit donc chaque minute, voir toutes les deux minutes, envoyer sa position au serveur? Mais où stocker les positions? de plus, si je les met en base de données, ca veut dire qu'avec mon algo, je dois utiliser l'API google pour demander chaque chemin entre chaque points, puis les classer (sous forme de liste chainée) pour les étudier? SI j'ai 1 million d'utilisateur, le serveur va être long non?

Une fois que je peux trouver le point le plus près, je dois me rendre au second, etc etc, imaginons que chaque smatphone est un checkpoint, je dois trouver le plus proche a chaque fois, et passer au suivant.

Merci de vos réponses !

Si l'application sait où est le point de référence, elle peut interroger Google Maps elle-même et envoyer le résultat (et sa position si nécessaire) au serveur, qui n'a plus qu'à classer les distances qu'il reçoit. Mais si j'ai bien compris ton algo, ce sera une opération à faire autant de fois qu'il y a d'appareils, à chaque fois qu'un appareil change de position, donc le nombre de requêtes vers ton serveur comme vers Google Maps est énorme.

Pour optimiser un peu, plutôt que de comparer la position de chaque appareil à tous les autres appareils, tu peux demander au serveur de calculer un cercle à vol d'oiseau autour du point N (juste en calculant les limites d'un cercle centré sur le point, sans passer par Maps), et demander seulement aux terminaux dans le cercle de se situer par rapport à N pour trouver N+1, et ainsi de suite.

Si c'est le serveur qui doit déterminer tous les chemins, oui, ça va être long, et surtout, ça va être payant (le nombre de requêtes que tu peux faire gratuitement à Maps est limité).

Bon j'ai découpé un peu tout ça Je sais pour la clé oui

Merci de ta réponse, après je peux peut-être faire un system de listes chainés comme ça je classe par département non?

Tu pense que en passant par les clients c'est plus opti? pour faire le cercle il me faut leurs positions non?

Je réfléchis et je me dis que non en fait, passer par les clients a ses limites aussi, parce que du coup pour chaque point tu vas devoir interroger quelques terminaux... Alors qu'une fois que toutes les positions ont été transmises au serveur, il peut faire toutes les mesures sans eux, donc si un nombre élevé de requêtes à Maps depuis ton serveur est pas un problème, c'est pas vraiment intéressant de décentraliser.

Oui, il te faut les positions pour faire les cercles, mais de toutes façons, le préalable à toute opération, c'est que tous les appareils te transmettent leurs coordonnées GPS.

Mais une fois que t'as une première carte, t'auras plus que des mises à jour à faire (qui peuvent certes être très nombreuses, ça dépend à quelle vitesse bougent tes appareils, combien de nouveaux appareils t'as par jour...).

Disons que j'ai 1Million d'appareil car le projet de ma boite fonctionne

Je peux pas donner plus d'infos sur le projet, mais je vois pas comment je peux centraliser les points? genre savoir le quel est le plus proche?

En gros, les étapes pour arriver à ta liste, à mon avis :

• chaque appareil transmet sa position GPS au serveur
• le serveur définit qui est l'appareil 1 (premier qui se connecte, un certain utilisateur, un lieu...)
• selon la densité d'appareils, le serveur calcule un cercle de 1, 10, 100...km autour de l'appareil 1 et cherche les appareils qui sont dedans (juste en vérifiant si les coordonnées des appareils rentrent dans les coordonnées du cercle)
• le serveur demande à Maps la distance routière entre 1 et les appareils contenus dans le cercle
• à partir des résultats il définit l'appareil 2
• nouveau cercle autour de 2, et ainsi de suite (évidemment, au fur et à mesure des analyses, tu exclues les appareils qui sont déjà classés)
• tu obtiens une première liste
• à chaque nouvel appareil tu fais un cercle autour de la position pour trouver dans quel maillon le terminal s'intercale
• à chaque mise à jour de position d'un appareil N, tu vérifies s'il est toujours à sa place dans la chaine (N est l'appareil le plus proche de N-1, et N+1 est l'appareil le plus proche de N). Si c'est pas le cas, tu dois recalculer ta chaine autour de son ancien emplacement, et insérer N comme un nouvel appareil dans sa nouvelle position.

ça vaut peut-être le coup de comparer la complexité de cet algo (calcul des cercles et recherche des points qui sont dedans) à un algo qui compare la distance de l'appareil N à tous les autres appareils pour trouver N+1 pour voir à partir de combien d'utilisateurs c'est efficace (comparer N à tout le monde est plus rentable pour un faible nombre d'utilisateurs, il faut voir si une approche locale est rentable à partir de 10, 1.000, 1.000.000... d'utilisateurs).

Au pire, chaque tel transmet sa pos a chaque minute?

Du coup, ca fait, si j'ai 200.000 appareils dispo, ca fait 200.000 request a google api geoloc pour calculer les distance ?

Ok je vois comment faire maintenant, merci beaucoup

Ben après faut voit si t'as vraiment besoin d'actualiser les positions chaque minute, ça dépend de ce que tu veux faire de ta liste.

Ouai c'est vrai aussi toute facon c'est coté mobile, je vérrai après