Discussion :

[yohann26]

Bonjour je sui a la recherche d'un petit script php ou/et d'idées de démarche.

J'ai une table1 contenant toutes les villes de france avec leur coordonnées longitude et latitude respective.
J'ai une table2 contenant uniquement le nom de certaines villes qui m'interresse.

J'aimerai que mon script me sorte toutes les villes de la table2 qui sont dans un rayon de x km (25 km par exemple) à partir d'une ville que je choisi (paris par exemple).

Connaissez des scripts ou une démarche optimisé ?
Certaines formules mathématiques utiles ?

Merci

[batataw]

Avec un bon vieux Therome de Pythagore tu devrais pouvoir calculer facilement la distance entre tes villes.

Si tu ne dois faire qu'une seule fois le calcul, tu peux créér une requete SQL qui fera pour toi ce calcul et qui enregistrera en base le resultat. A mon avis tu n'as pas besoin de PHP. 36000 communes x N communes ca sera tres long.

En revanche si ce calcul se fait a la volée, il faudra que tu optimises ton code pour ne traiter que les departments limitrophes par exemple.

[yohann26]

Réflections très interressantes !
Je le fais "à la volée" la ville ne sera jamais la meme (choisie par l'internaute)
Pour limiter la recherche au departement d'à coté, c'est une bonne idee mais des fois des departement ne se touche pas et pourtant sont tres proche...difficile a mettre en place, il faut aussi surement une base qui ressence les departement limitrophes par rapport à un department.


Pour pythagore (je connais) je ne vois pas trop coment faire...

Merci

N'hésitez pas si vous avez des idées..

[batataw]

Par exemple:
SELECT table1.ville, table2.ville, SQRT(POW((table1.x - table2.x),2) + POW((table1.y - table2.y),2)) from table1, table2
where table1.id = selectId
limit 10;

Sinon tu peux eliminer les communes qui ont une certaines longitude ou latitude.
On va dire que ta commune est a la latidtude 50 ben tu elimines toutes celle qui sont au dessus de 70 et celles au dessous de 30 car elles sont d'office trop loin.
En faite tu créés un rayon sur X et Y

where abs(tabe1.x - tabe2.x) < 20 and bs(tabe1.y - tabe2.y) < 20

[yohann26]

Merci je vais potasser tout ça...
Bonne idée pour la réduction/marge de lat et long.
Mais qu'est-ce que SQRT et POW ???

sinon j'ai trouvé cette formule :

Code X :

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

(6366*acos(cos(radians($LAT))*cos(radians(`nomville`.`latitude`))*cos(radians(`ville`.`longitude`)-radians($LONG))+sin(radians($LAT))*sin(radians(`nomville`.`latitude`))))

[batataw]

C'est pythagore a²+b²=c² donc c = √(a²+b²)
POW = puissance de
SQRT = racine carré de

Tu peux faire ta recherche en une requete je pense.

------------------------------------------------------
En revanche je ne vois pas tres bien a quoi correspond ta formule

[jeca]

Code X :

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

(6366*acos(cos(radians($LAT))*cos(radians(`nomville`.`latitude`))*cos(radians(`ville`.`longitude`)-radians($LONG))+sin(radians($LAT))*sin(radians(`nomville`.`latitude`))))

Cette formule est correcte ; elle correspond au calcul de la distance orthodromique entre 2 points du globe. Beucoup de renseignements ici :
http://www.lion1906.com/
Contrairement aux idées reçues, la plus court chemin d'un point à un autre sur une planishère n'est pas la ligne droite, mais plutôt une courbe, car la terre est ronde. Donc, le théoreme de pythagore n(est pas adapté car il calcul sur un plan, et non pas sur une shpère. Il est évident que sur de courtes distances, l'écart n'est pas important.

Cette première requête permet de définir un carré dans lequel la recherche va s'effectuer en fonction d'une ville de référence et d'une distance :

Code :

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

1
2
3
4
5
6
7
8
9
10
<?php 
$sql = 'select ville, cp, longitude, latitude,
               round(radians(longitude), 6) as longrad, round(radians(latitude), 6) as latrad,
               round((radians(latitude) - ' . $km . '/ 6378), 6) as latMin,
               round((radians(latitude) + ' . $km . ' / 6378), 6) as latMax,
               round((radians(longitude) - ' . $km . ' / 6378 / cos(radians(latitude))), 6) as longMin,
               round((radians(longitude) + ' . $km . ' / 6378 / cos(radians(latitude))), 6) as longMax
        from villes
        where id = ' . $villeId; 
?>

Cette seconde requête recherche dans la table les villes dont les coordonnées se trouvent dans le carré précédemment défini, en filtrant celles dont l'éloignement est supérieur à la distance de recherche :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
<?php 
$sql = 'select round(6378 * 
                     Acos(Cos(' . $latrad . ') * 
                     Cos(radians(a.latitude)) * 
                     Cos(radians(a.longitude) - ' . $longrad . ') + 
                     Sin(' . $latrad .') * Sin(radians(a.latitude))), 1) as distance
        from villes
        where radians(latitude) between ' . $latMin . ' and ' . $latMax . '
        and radians(longitude) between '. $longMin . ' and ' . $longMax . '
        having distance <= ' . $km;
 
?>

Ces requêtes sont évidemment à adapter en fonction de tes tables, et autres.

[fenkys]

Toutefois, sur 25 km, le théorème de pythagore est utilisable. Les villes lointaines seront fausse ? Qu'importe, elles seront rejetée.

La demande du posteur initial n'est pas de calculer la distance entre deux villes mais de répartir les villes en deux groupes, celles en deça d'une certaine limite et celle au dela. Dans ces conditions, il n'est pas grave si la formule est inexacte tant que les relations d'ordre entre villes sont respectées.

[jeca]

Il me semble avoir précisé :

Il est évident que sur de courtes distances, l'écart n'est pas important.

Mais, s'il faut faire une fonction, pourquoi ne pas en faire une qui s'adapte à toutes les distances ?

D'autre part, si le fait de trouver les villes se trouvant dans un rayon de 25 km d'une ville de référence ne consiste pas à calculer la distance qui les sépare, je ne comprends plus rien.

[fenkys]

Tout simplement parce que la formule exacte est complexe. Et s'il doit calculer tous les cas en PHP, ca risque de prendre du temps. Et en PHP, la vitesse c'est important car certains sites killent les scripts au delà d'une certaine durée.

Ce qui compte est la position relative des villes, pas la distance exacte. Si tu prend pythagore par exemple, la formule est :c² = a²+b², d'ou on titre C
c = √(a²+b²)

Et en mathématique, si (A >= 0, B >= 0) et A >= B alors A² >= B² (or une distance est toujours positive par définition, la première condition est donc toujours vraie)
Il n'est donc pas utile de calculer c, on peut se contenter de c² et faire les comparaison face à lui. Techniquement ici, on ne calcule pas la distance, mais le résultat final de l'algorithme sera inchangé.