Discussion :

[topolino]

Bonjour,

J'ai une fonctionnalité de geolocalisation sur le projet sur lequel je travaille, c'est de situer en km chaque utilisateur en fonction de ma situation geographique.

Je dois donc calculer pour tous les utilisateurs la distance qui les separe avec tous les autres.

J'ai donc une class qui calcul bien ces distances, ce n'est pas ca le probleme.

Est ce pertinent de calculer par exemple la nuit chaque coordonnée des utilisateurs en fonction de tous les utilisateurs ? ca risque de prendre du temps et de la place en Bdd non ? Car si j'ai 5000 utilisateurs ca va faire 5000 x 5000 en base de données et que lorsqu'un nouvel utilisateur s'inscrit, je vais devoir parcourir toute la table utilisateur afin de calculer sa distance avec les autres donc 5001 traitement.

Avez vous des conseils ?

Merci de votre aide

[SaumonAgile]

Comment calcule tu cette distance ?
Dans SQL Server 2008, il y a la possibilité de stocker des données géographiques pour ensuite générer des index spatiaux. Cette méthode est efficace et permet entre autres de calculer les distances entre les coordonnées.

Et sinon c'est pas vraiment 5000 * 5000 comme calcul. C'est plus du genre 6248750...

Pour résumer, je suis tout de même plus tenté par une approche orientée calcul de distance à la volée plutôt que précalculée.

[topolino]

Je suis sous sql server 2005. Et je stocke les coordonées de chaque utilisateurs en bdd. J' dois afficher par exemple sur la Home page, les personnes qui sont par à moins de 5000 metres de l'utilisateur logué(critere qui peut etre changé a tous moment par l'utilisateur). Donc calculer en temps reelle me fait un peu peur qd meme, car il peut y avoir un nombre important d'utilisateurs dans la bdd.

[smyley]

Je verrai plus une division du monde en plusieurs carrés, un peut à la manière des cartes dans les jeux. Le plus grand serai le monde en entier, et à chaque itération du divise le monde en 4 avec comme taille minimale 1 km (ou plus, une fois que tu as déjà une idée de qui est dans un carré, ça élimine déjà pas mal de monde, sauf s'ils sont tous concentrés sur 2 km², et tu peut aller boucler sur les gens présents dans le carrés).
Si les utilisateurs sont répartis à peut près équitablement, tu pourra approcher du log ce qui fait déjà beaucoup moins que 5000 * 5000 ...

[topolino]

c'est une bonne idee, mais comment gerer une personne qui est à la limite d'un carré ?

[smyley]

Si elle est exactement à la limite d'un carré tu pourrai décréter qu'elle est à l'intérieur comme cela tu pourrai ensuite calculer plus précisément une fois que tu aura fini ta découpe. Quitte à rajouter 2 ou 3 personnes en plus ça ne doit pas être très fréquent qu'une personne se trouve exactement à la limite. (en théorie la proba est nulle, mais ça c'est autre chose )

[topolino]

Comment tu referencies tous ces carrés ? l'arbre risque d'etre gigantesque.

En fonction de l'utilisateur qui se logue et qui va constater les personnes pres de lui, on est obligé de changer la localisation de chaque carré afin que l'utilisateur logué soit au centre du carré qui le concerne.

[smyley]

Comment tu referencies tous ces carrés ? l'arbre risque d'etre gigantesque.

ça c'est autre chose, je suis loin d'être pro de SQL SRV 2008. C'est juste comme cela que j'aurai fait. Et après tout un carré c'est sa dimension et ensuite ces carrés enfants. Et pour les derniers carrés les enfants ce sera les id des utilisateurs. Et vu qu'à chaque fois ça fait 4 enfants on obtiens pour chaque carré interne 4 champs pour les carrés enfants, et pour chaque feuille une liste des id ...

En fonction de l'utilisateur qui se logue et qui va constater les personnes pres de lui, on est obligé de changer la localisation de chaque carré afin que l'utilisateur logué soit au centre du carré qui le concerne.

Bah non, il faut juste être large. Imaginons que tu arrives à faire ta découpe, et que tu la termine à 1 km. La distance entre 2 personnes comprises dans deux carrés côtes à côtes sera comprise entre 0 et 2 km. Donc si l'utilisateur veux savoir qui est à au plus 5 km de lui, il faut voir qui est présent dans le carré que tu formes en ajoutant 5 carrés à gauche, à droite, en haut et en bas. Au mieux les gens seront à 0 km, au pire il seront à 6 km et il suffit alors de calculer la distance réelle pour les personnes se trouvant exactement dans le 5e carré (les autres des carrés d'avant seront forcément à moins de 5 km).
C'est sur ça fait beaucoup de calculs et si en général on veut savoir par exemple qui est à moins de 5 km, je pense que l'idéal c'est d'avoir au minium des carrés de 5 km, ça limite pour chaque carré à regarder qui est dans le carré formé par le carré du centre + les 8 carrés adjacents. (Dans le cas de carrés de 1 km, tu en as 121 si je me trompes pas alors que là tu en a plus que 9).

ps. et d'ailleurs avec une telle découpe le nombre minimum de carrés à scanner est 9 ...

[topolino]

Je vais essayer ta methode, par contre je ne vais pas le faire en temps reelle, car les utilisateurs ne vont pas changer d'adresse toute les 5 min.

Merci

[SaumonAgile]

Smyley, la méthode que tu décris ne sert pas à stocker les données mais à les indexer. Le stockage restera sur une base de coordonnées. SQL Server 2008 gère les index spatiaux d'une manière similaire à ce que tu décris. Mais il ne faut pas se tromper, c'est bien un index que tu as présenté, ce n'est pas un stockage.

[topolino]

Je rappel que je suis sous sql server 2005.
Quelle solution preconises tu alors saumonAgile ?

[smyley]

Smyley, la méthode que tu décris ne sert pas à stocker les données mais à les indexer. Le stockage restera sur une base de coordonnées. SQL Server 2008 gère les index spatiaux d'une manière similaire à ce que tu décris. Mais il ne faut pas se tromper, c'est bien un index que tu as présenté, ce n'est pas un stockage.

Je sais bien que c'est une indexation (d'ailleurs c'est une indexation spatiale), mais que je sache le but était de réduire le nombre de parcours de la table :

Car si j'ai 5000 utilisateurs ca va faire 5000 x 5000 en base de données et que lorsqu'un nouvel utilisateur s'inscrit, je vais devoir parcourir toute la table utilisateur afin de calculer sa distance avec les autres donc 5001 traitement.

Le stockage se fait sous forme d'arbre (avec une structure d'arbre ou "linéarisé" dans une table) et l'indexation permet de diminuer radicalement le nombre de calculs à faire pour obtenir les utilisateurs présents dans un certains rayons en s'abstenant de faire des calculs inutiles.
Après peut être que SQL Server supporte nativement cette découpe, ça je ne sais pas.

[Kelpan]

Je pense pas qu'une requête des personnes qui entournent la personne loguée soit si couteux que ça ?

Avec une fonction qui calcule la distance en fonction des coordonnées, tu peux facilement récupérer les données.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
 
@Coord = Coordonnées de la personne loguée
@Distance : Distance à vérifier...
 
SELECT
    Personnes.Id
  , Personnes.Coord
FROM Personnes
WHERE
    maFonctionQuiCalculeLADistance(Personnes.Coord, @Coord) <= @Distance

Une requête comme celle-ci ne me semble pas énorme ou alors j'ai manqué quelque chose...

[Graffito]

c'est une bonne idee, mais comment gerer une personne qui est à la limite d'un carré ?

Pour reformuler plus ou moins la proposition de smyley
Dans la table "Utilisateurs", Il suffit d'attribuer à chaque utilisateur :

• Un Index longitude fonction de ses coordonnées : entier avec un pas correspondant à 4' (environ 5300m pour le territoire métropolitain)
• Un Index latitude fonction de ses coordonnées : entier avec un pas correspondant à 3' (environ 5600m)

Ensuite une requete SQL sur la table Utilsateurs qui donne tous les utilisateurs de la base tels que :

• Leur IndexLatitude soit compris entre l'IndexLatitude-1 et l'IndexLatitude+1 de l'utilisateur de référence.
• ET leur IndexLongitude soit compris entre l'IndexLongitude-1 et l'IndexLongitude+1 de l'utilisateur de référence.

Cette requête renverra tous les utilisateurs situés dans un carré de environ 16x16 Km. Reste plus qu'à eliminer dans le résultat de la requète ceux qui sont à plus de 5000m.

Evidement, 16x16 peut encore faire beaucoup de monde à Paris si l'utilisateur est Quasimodo (adresse : Notre-Dame).

[smyley]

smiley

C'est juste smYley...

[topolino]

Merci à tous.