Discussion :

[heretik25]

Bonjour,


I] Présentation :

J'ai un script qui me permet de parser un fixhier XML (au format .GPX) et de le rentrer dans une base MYSQL. Ces fichiers GPX sont des traces issues d'un GPS. Ils contiennent l'altitude, une latitude, une longitude et un datetime.

Au niveau de l'insertion en base, tout fonctionne bien.

II] Le problème

Parfois, lorsque l'on fait un très grand parcours, on obtient des milliers de points. Pour ne pas encombrer la base de données, j'aimerais mettre en place un système qui permettrait de simplifier ces points. L'idée est donc de ne pas intégrer certains points pour simplifier la trace.

Quel algorythme pourrait-on utiliser ? J'ai pensé à ne pas intégrer un point sur deux tant que l'on atteint pas un nombre de point précis.

III] Le code d'insertion des points GPS :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
	$xml = $DESTINATION_FOLDER.'/'.$nom_gpx;
	$obj = simplexml_load_file($xml, 'SimpleXMLIterator');
 
	$sql_insert_coordonnee = $bdd->prepare('INSERT INTO pevtt_coordonnee_gps (id_fichier_gps, id_coord_gps, coord_gps_lat , coord_gps_lon, coord_gps_altitude, coord_gps_date)' 
										. ' VALUES (:id_fichier_gps, :id_coord_gps, :coord_gps_lat, :coord_gps_lon, :coord_gps_altitude, :coord_gps_date)');
	$id_coord_gps = 1;
	foreach($obj->trk->trkseg->trkpt as $trkpt)
	{        
		$tableau_gpx = array(
			':coord_gps_lat' => $trkpt['lat'],
			':coord_gps_lon' => $trkpt['lon'],
			':coord_gps_altitude' => $trkpt->ele,
			':coord_gps_date' => strftime("%Y-%m-%d %H:%M:%S", strtotime($trkpt->time)),
			':id_fichier_gps' => $id_fichier_gps,
			':id_coord_gps' => $id_coord_gps	
		);
		$sql_insert_coordonnee->execute($tableau_gpx);
		$id_coord_gps++;	
	}

Si vous avez une idée sur le comment faire, je suis preneur !

Merci pour votre aide.

[heretik25]

Peut-être que ce script (utilisant l'algo de Douglas Peuker) pourrait aider.

Si quelqu'un a le temps de jeter un oeil et y comprend comment cela fonctionne, ce serait super

EDIT : Pseudo fonction issue de wikipédia

Quelqu'un saurait la traduire en php ?

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function DouglasPeucker(PointList[], epsilon)
  // Trouve le point le plus éloigné du segment
  dmax = 0
  index = 0
  for i = 2 to (length(PointList) - 1)
    d = DistancePointSegment(PointList[i], Segment(PointList[1], PointList[end])) 
    if d > dmax
      index = i
      dmax = d
    end
  end
 
  // Si la distance dmax est supérieure au seuil, on simplifie
  if dmax >= epsilon
    // Appel récursif de la fonction
    recResults1[] = DouglasPeucker(PointList[1…index], epsilon)
    recResults2[] = DouglasPeucker(PointList[index…end], epsilon)
 
    // Construit la liste des résultats à partir des résultats partiels
    ResultList[] = {recResults1[1…end-1] recResults2[1…end]}
 
  else
    // Tous les points sont proches ? renvoie un segment avec les extrémités
    ResultList[] = {PointList[1], PointList[end]}
  end
 
  // Renvoie le nouveau résultat
  return ResultList[]
end

[heretik25]

Personne pour un coup de main ?

[ericd69]

c'est un algo de segmentation...

l'idée est de supprimer les points dont l'écart est inférieur à un seuil...

dans tous les cas, tu auras une approximation qui engendrera des artefacts sur la courbe...

[heretik25]

Bonsoir,

Merci pour votre réponse.

Effectivement, il y aura des suppressions de points et donc une perte de précision. Cependant, sur des centaines de kilomètres, la précision nécessaire est relative et beaucoup de points sont trop proches les uns des autres.

Si on pouvait réussir à implémenter cela en php, je suis sûr que cela pourrait aider du monde.

J'aimerais pouvoir faire une fonction générale qui simplifie le nombre de point et une autre (ou alors à l'aide d'un autre paramètre) qui simplifie le tracé tant qu'on est pas arrivé à un certain nombre de points.

[ericd69]

ça dépend de ce que tu as besoin de faire vraiment et si tu as besoin de points réels...

en gros, l'approximation peut drastiquement changer ta courbe...

prenons un algo tout bête:

• on garde les points dont l'indice est espacé de n
• on fait la moyenne des points intermédiaires

ça fait moins brutal que de juste sauter n points
mais si tu veux superposer ça à une route sur une carte tu auras des écarts forcément...
si c'est du pédestre ou de l'aérien, ça peut être simple et efficace... car tu te fous un peu plus de la précision...

[heretik25]

Bonjour,

ce sera pour des tracés de sport nature au sol (rando, vélo, vtt...). L'objectif est de trouver le bon compromis entre nombre de point et précision du tracé.

Au niveau de la méthode, je pensais que l'algorithme de Douglas Peucker ferait l'affaire. Qu'en pensez-vous ?

[ericd69]

oui peu importe...

n'importe quel algo va bien du moment qu'il est paramétrique

le mien se base sur le nombre de point indépendamment de la métrique, le tien sur la métrique indépendamment du nombre de point me il semble...

il peut être intéressant de stocker de manière intermédiaire la liste des points dans un fichier genre csv si l'extraction te semble longue (plusieurs secondes) car vouloir faire l'épuration des points dans le même script peut engendrer un temps d'exécution trop long

de plus mettre l'épuration à part permet de tester plusieurs résultats avant de choisir le plus adapté...

[heretik25]

A ce jour, je parse le gpx et envoi le tout en base. Parfois, ça met un peu de temps, c'est normal car il peut y avoir des milliers de lignes à insérer.

Maintenant, l'idée est de faire la simplification avant d'envoyer en base. A voir si le temps s'allonge tant que ça étant donné que l'on enverra moins de point en base.

Je ne sais pas si cet algorithme sera gourmand au point d'exploser les temps d'insertion.

Dans tous les cas, je suis preneur d'un exemple car je n'arrive pas à implémenter cette fonction en php.

Merci pour votre aide et le partage si vous avez quelque chose d'opérationnel et de libre.

[ericd69]

je te parle en terme de prétraitement avant l'envoi

tu développes sur ta machine ou un hébergement?

je crains que le parsage de gpx+simplification+insertion soient un peu trop long en une fois et que ça risque de dépasser les 30 secondes fatidiques mais ça dépend du temps de parsage+insertion actuel

tu vois pas comment implémenter mon algo?

[heretik25]

Je développe en hébergement pour réaliser ce genre de page : http://partir-en-vtt.com/php/article...id_article=395

Affichage de la trace GPS sur fond carto Openstreetmap, affichage des statistiques de la balade, affichage des photos géolocalisées grâce au timestamp des photos et des points gps...et on ajouterait la simplification.

Sachant que sur un gpx de 3000 points avec insertion d'un texte de quelques pages, la moulinette met moins de 10 secondes. Ces 10 secondes prennent en compte le temps d'upload du fichier.

Concernant l'algorithme, j'ai effectivement besoin d'aide car j'ai du mal à conceptualiser la chose.

[ericd69]

Code php :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
<?php
	/***
	 * @name	pathSimplification	simplification d'un groupe de point selon un pas
	 * @param	$tab	tableau valide des coordonnées avec ['la']['lo'] pour chaque ligne
	 * @param	$ret	tableau valide des coordonnées simplifié à partir de $tab
	 * @param	$step	pas entre chaque point à préserver	
	 */
	function pathSimplification(&$tab,&$ret,$step)
	{
		$ret=array();
		$inter=array();
		$j=0;
		for($i=0;$i<sizeof($tab);$i++)
		{
			if($i % $step)
			{
				$inter[]=$tab[$i];
				$j++;
			}
			else
			{
				if($i==0)
					$ret[]=$tab[0];
				else
				{
					$la=0;
					$lo=0;
					for($k=0;$k<$j;$k++)
					{
						$la+=$inter[$k]['la'];
						$lo+=$inter[$k]['lo'];
					}
					$ret[]=array('la' => $la/$j,'lo' => $lo/$j);
					$ret[]=$tab[$i];
					$j=0;
				}
			}
		}
		if($i % $step)
		{
			$la=0;
			$lo=0;
			for($k=0;$k<$j;$k++)
			{
				$la+=$inter[$k]['la'];
				$lo+=$inter[$k]['lo'];
			}
			$ret[]=array('la' => $la/$j,'lo' => $lo/$j);
		}
	}
?>

ça devrait marché... j'ai pas testé
l'un des secrets est de passer les tableaux à brasser par référence au lieu de par valeur (sans le &)... du coup tu évite de te taper des copies inutiles

tu devrais facilement pouvoir l'insérer dans ton code
le format une ligne de $tab ou $ret est un tableau avec 2 indices associatif 'la' pour la latitude et 'lo' pour la longitude

à voir le temps d'exécution...
tu peux je pense déjà tenté avec $step à 5 ou 10, ce qui te donnerait 600 à 300 points
faut faire des essais
peut-être même que 15 ou 20 serait jouable... la trace est clairement trop précise vu le le temps d'affichage

tu as le principe... tu peux très facilement rajouter la prise en charge de l'altitude dans la fonction...

[heretik25]

Bonjour,

Merci pour ce code que je vais essayer de comprendre.

Par rapport à ta remarque sur l'altitude. Quel avantage pourrait-on tirer en gérant l'altitude ?

[heretik25]

J'ai essayé de faire ça pour passer mes coordonnées dans la fonction

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
$sql_select_pts_gps = $bdd->query('SELECT coord_gps_lat AS la,coord_gps_lon AS lo,coord_gps_altitude AS alti '
									. ' FROM pevtt_coordonnee_gps '
									. ' WHERE id_fichier_gps = 55');
 
$array = array();
	while($tab_pts_gps = $sql_select_pts_gps->fetch())
	{
		$array[ $tab_pts_gps['la'] ] = $tab_pts_gps['lo'];
	} 
 
	echo '<pre>';
	echo print_r( pathSimplification($array,null,10));
	echo '</pre>';

Résultat :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Array
(
    [0] => 
    [1] => Array
        (
            [la] => 0
            [lo] => 0
        )
 
    [2] => 
    [3] => Array
        (
            [la] => 0
            [lo] => 0
        )
 
    [4] => 
    [5] => Array
        (
            [la] => 0
            [lo] => 0
        )

Je ne comprend pas le résultat. Pourriez-vous m'aider ?
Pourriez-vous également me dire à quoi sert le paramètre

Code :

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

$ret

et s'il fallait ajouter

Code :

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

 return $ret;

dans la fonction comme je l'ai fait.


Merci.

[ericd69]

non surtout pas!!!

car j'évite les copies intempestives de ces gros tableaux grâce au passage par référence

le 2ème paramètre c'est le tableau qui recevra les valeur en retour...

Code php :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
$sql_select_pts_gps = $bdd->query('SELECT coord_gps_lat AS la,coord_gps_lon AS lo,coord_gps_altitude AS alti '
									. ' FROM pevtt_coordonnee_gps '
									. ' WHERE id_fichier_gps = 55');
 
$array = array();
	while($tab_pts_gps = $sql_select_pts_gps->fetch())
	{
		$array[]=array('la' =>$tab_pts_gps['la'], 'lo'=> $tab_pts_gps['lo']);
	} 
        $retour=array();
        pathSimplification($array,$retour,10)
 
	echo '<pre>';
	echo print_r($retour);
	echo '</pre>';

tu as du mal avec les tableaux et leurs indices
avec ma fonction non modifiée bien sur...

faut que tu comprennes l'idée, quand tu passes un paramètre de façon classique, par valeur, tu travailles dans la fonction sur une copie pas sur la variable ou valeur passée directement...
c'est parfois très utile mais sur des gros tableau c'est juste une perte de ressource et de temps... d'où le passage par référence...

[heretik25]

Merci de m'avoir remis dans le droit chemin.

Et par rapport à l'altitude, que pourrait-on gagner si en travaillait avec ce "paramètre" ?

D'après vous, vaut-il mieux intégrer puis ensuite simplifier ou simplifier avant d'intégrer ?

[ericd69]

comme j'ai vu que tu faisais des graph d'altitude sur le parcours...

ça le générerait plus rapidement qu'avec 3000 points non?

[heretik25]

comme j'ai vu que tu faisais des graph d'altitude sur le parcours...

ça le générerait plus rapidement qu'avec 3000 points non?

On se moque pas

Effectivement, j'ai besoin de récupérer toutes ces informations :

• long/lat
• Altitude
• Datetime

Comment faut-il faire dans ce cas ?

A ce jour, je parse le gpx et j'intègre tout

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
	//3) integration des coordonnées gps à partir du fichier gpx stocké
	$xml = $DESTINATION_FOLDER.'/'.$nom_gpx;
	$obj = simplexml_load_file($xml, 'SimpleXMLIterator');
 
	$sql_insert_coordonnee = $bdd->prepare('INSERT INTO pevtt_coordonnee_gps (id_fichier_gps, id_coord_gps, coord_gps_lat , coord_gps_lon, coord_gps_altitude, coord_gps_date)' 
										. ' VALUES (:id_fichier_gps, :id_coord_gps, :coord_gps_lat, :coord_gps_lon, :coord_gps_altitude, :coord_gps_date)');
	$id_coord_gps = 1;
	foreach($obj->trk->trkseg->trkpt as $trkpt)
	{        
		$tableau_gpx = array(
			':coord_gps_lat' => $trkpt['lat'],
			':coord_gps_lon' => $trkpt['lon'],
			':coord_gps_altitude' => $trkpt->ele,
			':coord_gps_date' => strftime("%Y-%m-%d %H:%M:%S", strtotime($trkpt->time)),
			':id_fichier_gps' => $id_fichier_gps,
			':id_coord_gps' => $id_coord_gps	
		);
		$sql_insert_coordonnee->execute($tableau_gpx);
		$id_coord_gps++;	
	}

Maintenant, il faut que je simplifie puis que j'intègre.

[ericd69]

pour la date je pense que tu dois la convertir en unix timestamp...pour faire la somme et la division et tu reconvertis en date juste après... c'est le seul truc un peu pénible

mais rien de dur maintenant tu as compris le principe...

[heretik25]

Si tu as 5 minutes, tu pourrais commenter ta fonction afin de bien la comprendre ?

Merci :-)