Proximité des villes françaises
SIG - Les villes de France et leurs proximité
J'ai pour but d'analyser les 38052 communes de France par rapport à une ville "pivot", et parmi celles qui comptent plus de 5000 habitants, d'en déduire une liste triée des villes les plus proches. Bien évidemment les données sont stockées dans une base de données (MySQL pour ne pas la nommer), que j'ai reprise depuis ce site très intéressant et la volonté ici est d'être le plus performant possible, d'où mon choix du C++.
Tout d'abord il me faut présenter la structure de la base de données, dans un pseudo-langage de description qui m'est propre mais simple à comprendre :
<component name='erpCity' basedOn="qbase" language="FR" fullName="Villes" Gender="female" tableName='erpCities'>
<fields>
<shorttext name='inseeCode' formHeader='Code INSEE'/>
<shorttext name='name' formHeader='Nom de la ville'/>
<float name='latitude' formHeader='Latitude (en radians)'/>
<float name='longitude' formHeader='Longitude (en radians)'/>
<shorttext name='zipCode' formHeader='Code postal'/>
<integer name='pop' formHeader='Population'/>
<float name='density' formHeader='Densité de population'/>
</fields>
</component>
L'insertion de ces données dans une base MySQL se fait de façon directe en PHP :
<html>
<head>
<title>Création de la base de données des villes</title>
<meta http-equiv='Content-Type' value='test/html; charset=utf-8'/>
</head>
<body>
<?
include_once "./dir.php";
include_once $gIncludeDir."/__helpers.php";
include_once "component.php";
$Datas = file_get_contents("villes.csv");
$FieldNames = array("Insee"=>"inseeCode", "Nom"=>"name",
"LatitudeRadian"=>"latitude", "LongitudeRadian"=>"longitude",
"CodePostal"=>"zipCode", "NombreHabitants"=>"pop", "Densite"=>"density");
$Lines = explode("\n", $Datas);
$NbLines = count($Lines);
echo "Nombre de communes : $NbLines<br/>\n";
$Comp = new Component("city");
$Comp->CreateTable(); //On réinitialise la table à chaque fois
$GlobalRet = true;
for($i=0; $i<$NbLines; $i++) {
if (!$i) continue; //On ignore la première ligne
$Values = explode(";", $Lines[$i]);
//
$Query = "insert into qt_erpCities (id, inseeCode, name, latitude, longitude, zipCode, pop, density) values (0, \"$Values[0]\", \"$Values[1]\", $Values[2], $Values[3], \"$Values[4]\", $Values[5], $Values[6]);";
if (!($Ret = DB_ExecQuery($Query))) echo "Problème d'insertion : <blockquote>".mysql_error()."</blockquote>\n";
$GlobalRet &= $Ret;
}
if (!$GlobalRet) echo "<p>Il y a eu au moins un problème d'insertion.</p>";
?>
</body>
</html>L'exécutable qui tournera sur le serveur utilise un tri Radix et un wrapper MySQL pour simplifier l'écriture :
class CityRanks : public Application
{
struct City
{
float latitude, longitude;
float distance;
};
public:
CityRanks() { }
virtual int run()
{
int i;
//On parse les paramètres de la ligne de commandes
int NbParamsToParse = _argc-1;
if (NbParamsToParse < 2) return EXIT_FAILURE;
if (NbParamsToParse > 2) NbParamsToParse = 2;
int* Params = new int[2];
for(i=0; i<NbParamsToParse; i++) sscanf(_argv[i+1], "%d", &Params[i]);
//Paramètres de la ligne de commande :
int Pivot = Params[0];
int NbResults = Params[1];
//
MySQL* DB = new MySQL();
City** Cities = new City*[1700];
char** CityNames = new char*[1700];
memset(CityNames, 0, sizeof(char*)*1700);
int NbCities = 0;
//
DB->serverInit();
if (DB->init() && DB->connect("Nom de la base de données", "Nom de l'utilisateur", "Mot de passe de l'utilisateur")) {
if (DB->query("select name,latitude,longitude from qt_erpCities where pop>=5000 group by inseeCode order by pop desc;")) {
City* CurCity = NULL;
MYSQL_ROW Row;
while (DB->fetchRow(Row)) {
CurCity = Cities[NbCities] = new City;
string_affectCopy(&CityNames[NbCities], Row[0]);
sscanf(Row[1], "%f", &CurCity->latitude);
sscanf(Row[2], "%f", &CurCity->longitude);
NbCities++;
}
DB->freeResult();
} else return EXIT_FAILURE;
} else return EXIT_FAILURE;
//Je me suis inspiré de http://en.wikipedia.org/wiki/Great-circle_distance
float EarthRadius = 6372.795f;
float PivotLongitude = Cities[Pivot]->longitude;
for(i=0; i<NbCities; i++) {
//On calcule la distance entre la ville <i> et la ville témoin/pivot
float Lat1 = Cities[i]->latitude;
float Lat2 = Cities[Pivot]->latitude;
float dLat = Lat1 - Lat2;
float dLong = Cities[i]->longitude - PivotLongitude;
float SinLat = sin(dLat/2);
float SinLong = sin(dLong/2);
float dSigma = 2.0f * asin(sqrt(SinLat*SinLat+cos(Lat1)*cos(Lat2)*SinLong*SinLong));
Cities[i]->distance = EarthRadius * dSigma;
}
//On trie les résultats en fonction de la distance
//On prépare le tableau à trier
int* Distances = new int[NbCities*2];
for(i=0; i<NbCities; i++) {
Distances[2*i] = (int) Cities[i]->distance;
Distances[2*i+1] = i; //La clé
}
int* Result = new int[NbCities*2];
Radix_sort(Distances, NbCities, 2, Result);
printf("Distance par rapport à %s :\n", CityNames[Pivot]);
for(i=1; i<NbResults+1; i++) printf("%s : %d km\n", CityNames[Result[2*i+1]], Result[2*i]);
Radix_release();
ReleaseArray(Distances);
ReleaseArray(Result);
//
Release(DB);
for(i=0; i<NbCities; i++) Release(Cities[i]);
ReleaseArray(Cities);
for(i=0; i<NbCities; i++) string_release(&CityNames[i]);
ReleaseArray(CityNames);
//
ReleaseArray(Params);
//
return EXIT_SUCCESS;
}
};
FFW_MAINENTRY(CityRanks);
Le temp moyen d'exécution sur un Sempron 2200+, avec 768Mo de RAM, est de l'ordre de 120ms, sachant que plus de 99% (si, si) de ce temps est consacré à l'accès à la DB. A noter que je voulais avoir un exécutable le plus petit possible (on pourra certainement faire mieux que moi, mais je suis déjà très content !). Avec la commande ci-dessous, ce programme prend 7860 octets :
strip --strip-unneeded -R .comment -R .gnu.version cityquery
Pour exécuter la requête depuis un navigateur, qui est le but de cette entrée, le script PHP suivant se chargera du travail (qui n'est pas bien lourd) :
<html>
<head>
<title>Requête de distance géographiques</title>
<meta http-equiv='Content-Type' value='test/html; charset=utf-8'/>
</head>
<body>
<?
$Pivot = isset($_GET["pivot"]) ? $_GET["pivot"] : "";
$NbResults = isset($_GET["nbResults"]) ? $_GET["nbResults"] : 30;
if (!strlen($Pivot) || !$NbResults) die("");
if (!is_numeric($Pivot) || !is_numeric($NbResults)) die("");
if ($Pivot > 38052 || $Pivot <= 0 || $NbResults > 100 || $NbResults <=0) die("");
$Output = shell_exec("/usr/local/bin/cityquery $Pivot $NbResults");
echo str_replace("\n", "<br/>\n", $Output);
?>
</body>
</html>
On pourra consulter le résultat de tout ceci sur les images ci-dessous, en attendant que je donne accès à ce script directement depuis ce site (ça ne serait peut-être pas très prudent) :
