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...