Bonjour,
Dans le cadre du développement d'un site web, comment réaliser la fonction qui permet de sélectionner une distance max à partir de la position de l'internaute (géolocalisation par ip ou par déclaration)?
Par exemple, si je cherche toutes les annonces émanant de personnes qui soient à moins de 10 km de chez moi...
J'ai donc besoin d'une base de données des latitudes et longitudes des principales villes du monde (celles utilisées par ip)
Et j'ai surtout besoin de la formule qui permet de déterminer les longitudes et latitudes comprises dans le cercle de définition...
Bref, j'ai besoin de réaliser la fonction qui existe sur de nombreux sites d'annonces, de ventes au enchères, etc...
Merci de me guider dans cette recherche !

Quelles recherches as-tu effectuées jusqu'à présent ?
 
Pour ce qui est de la géo-localisation IP, je trouve que c'est un peu de la connerie. Les rares fois où je vois une pub localisée sur un site, c'est à côté de la plaque (j'ai constaté ce phénomène en surfant à deux endroits différents, en Belgique).
 
De plus, je trouve cette pratique très discutable. Mieux vaut s'en tenir à une déclaration volontaire de l'internaute.
 

Oui mais bon c'est normal si c'est des IP belges aussi. )  
Sans rire, moi je n'ai vu qu'un seul exemple et ça m'a bien repéré comme étant à Caen. Mais bon c'est vrai qu'un seul exemple c'est un peu pauvre, et puis que c'est pas agréable de se sentir repéré. Y en a qui vont faire des crises de paranoïa et tu seras responsable. ;o)
Sinon si t'a besoin d'une base de données des régions, departements, communes de France j'en ai une, mais sans les coordonnées.

Ca peut marcher avec les grandes agglomérations, mais sans doute pas en deça.

Mon problème est moins un problème de localisation qu'un problème de tri et sélection des annonces émanant d'internautes situés dans un rayon de X km d'un point déterminé...
Si l'internaute est à Madrid et qu'il recherche toutes les annonces dans un rayon de 10 km, comment faire pour que ma base de données mouline un résultat et affiche toutes les annonces par ordre croissant de distance et jusqu'à 10 km maximum ???
ça ne doit pas être bien compliqué puisque tous les sites d'annonces offrent cette possibilité...
Merci pour vos réponses.

En admettant que tu ais les coodonnées de tes villes, il suffit de récupérer les coodonnées de toutes les villes dans un tableau. Ensuite tu calcules la distance qui sépare la ville recherchée de chacune de ces villes (avec Pythagore je pense). Tu stockes ces distances dans un autre tableau. Tu tri ton tableau. Tu n'affiche que les villes qui sont à moins de X Km.

ben c'est lui qui indique où il se trouve et le rayon dans lequel il veut les annonces...

Je pars en effet d'une base avec les coordonnées longiitude/latitude de toutes les villes.
Si tu t'identifies comme étant à Paris et que tu cherches toutes les annonces dans un rayon de 20 km, l'objectif est bien de te sortir l'ensemble des annonces présentes dans la base, classées par distance croissante à partir de Paris.  
Il ne me semble pas vraiment raisonnable de calculer à chaque requête toutes les distances... la limite sera vite atteinte avec la taille de la base... bonjour le tableau !... ebay qui offre ce type de fonction mettrait des heures avant de te sortir la liste des produits..

Oui c'est vrai que ça peut relentir un peu. Mais je vois pas du tout comment faire  d'autre. Peut-être que ça peut se faire avec des graphes. Mais ça demande que tu construise le graphe toi même et ça prendrais beaucoup de temps je pense. Sinon, tu peux peut-être utilisé ma méthode en te restreignant au departement qui contient la ville et aux departements voisins. Si tu fais ça en php, l'algo sera effectué côté serveur. Il y a 36000 communes en France. 36000 divisé par 100 departements = 360 villes en moyenne par departement. Si tu fais ta recherche sur 4 ou 5 departements à la fois, ça fais moins de 2000 entrées à traiter. A moins que ton serveur ne soit très lent, je pense que c'est raisonnable.

pb du plus court chemin avec la distance < rayon spécifié?

arbre BSP!
edit: quoiqu'un simple parcours de graphe en largeur devrait suffir.

Les arbres BSP ça permet d'utiliser les distances?
Moi je pensais à un graphe qui représenterait les villes avec la distance entre chaque ville (enfin les villes pas trop éloignées). Ca m'interesse un peu parce que j'ai manqué les cours sur ça pour cause de grève anti CPE.

> Les arbres BSP ça permet d'utiliser les distances?
- oui, mais je reconnais que ça risque d'être un peu lourd pour ce qu'il veut faire
 
> graphe
- c'est la deuxième solution. Il y a deux parcours de base dans un graphe: en profondeur, et en largeur. Pour ces deux parcours, il te faut un booléen dans chaque sommet pour indiquer si le sommet a été traversé.
- parcours en largeur: d'abord mettre le booléen ``parcourru`` de tous les sommets à ``faux``. Ensuite on part d'un sommet, en l'occurence pour ce problème la ville à partir de laquelle s'effectue la recherche. C'est le sommet courant. Pour chaque sommet adjacent au sommet courant (chacune des villes les plus proches) qui n'a pas encore été parcourru, ajouter ce sommet à la liste des sommets parcourus et mettre le booléen ``parcourru`` à Vrai. Puis recommencer l'opération avec chaque nouveau sommet découvert précédemment. Pour ce problème, s'arrêter quand la distance devient trop grande, ou que le nombre de villes parcourrues atteint une limite. Trier le résultat.
- parcours en longueur: idem, sauf au lieu de parcourrir d'un coup tous les sommets adjacents, marquer la position en ajoutant le sommet dans une pile, aller au premier sommet adjacent, recommencer. Quand il n'y a plus de sommet adjacent non parcourrus pour le sommet courant, dépiler l'ancien sommet courant, recommencer. Quand la pile est vide, on a terminé.
 
Dans ce problème, il reste à construire le graphe, c'est à dire déterminer par avance quelles sont les villes adjacentes à chaque ville.

le systeme de ebay basé sur les codes postaux

Je vous confirme que la solution repose uniquement sur un calcul orthodromique à partir des latitudes et longitudes des villes....
Ce qui permet de traiter globalement le problème car il existe des bases qui reprennent les principales villes du monde avec leurs coordonnées exprimées en latitude et longitude.
La solution consiste à convertir le rayon d'action en 'entier' applicable sur les coordonnées de l'origine et trier en fonction du résultat obtenu...
Ce qui est utilisé sur tous les sites de rencontres ou d'annonces, tant en france qu'aux usa... (imaginez un graphe US...!)
Par exemple, des sites comme topannonces.fr ou vivastreet.fr permettent de sélectionner la ville, code postal ou département puis un rayon d'action en km... et cette recherche marche pour le monde et pas uniquement la france...
Je recherche donc la formule à appliquer sur les latitude et longitude et à inclure dans un select de ma base...

> Je recherche donc la formule à appliquer sur les latitude et longitude et à inclure dans un select de ma base...
- c'est un calcul de distance: long²+lat²
- ne pas calculer la racine carrée, calculer le carré du rayon à la place: long²+lat²<rayon²