scoutant.org    blog  apps  about

mardi, octobre 4 2011

Affichage de polylines dans application Android avec Google Maps

Vous avez besoin d'afficher des routes ou des itinéraires dans une application Android?

Ce billet présente comment afficher des polylines dans une application Android, en utilisant l'API Google Maps.

La polyline Google Maps...

Oui, la première étape est bien : comment définir le tracé?

Pour cela, on peut s'appuyer sur le service de calcul d'itinéraire de l'API Google Maps. On pourra se référer au billet Itinéraires Google Maps et Encoded Polyline Algorithm Format .

On précise les points de départ et d'arrivée et si nécessaire également des points de passage obligé. On peut même préciser de retourner au point de départ, ci-dessus on obtient, pour le coup, le tracé de la rocade de Bordeaux.

bordeaux

L'image ci-dessus est issue d'une intégration JavaScript, démo en ouvrant : bordeaux.html. Autre exemple avec le périphérique de Paris : paris-periph.html

A titre d'exemple, l'ensemble de la rocade a été obtenu en utilisant l'API web services :

http://maps.google.com/maps/api/directions/xml?sensor=false&origin=44.88792,-0.57966&destination=44.88743,-0.57318&waypoints=44.85494,-0.66433|44.789994,-0.61213|44.8383,-0.501

Le service Directions de l'API Googole Maps propose, en retour, une description textuelle de l'itinéraire. Et aussi, en bonus, une description graphique de celui-ci sous forme de polyline, dans un format encodé par soucis de bande passante.

A la fin de la réponse on note :

<overview_polyline>
<points>
od~pGzepB_MpnEJxK`@pEz@hFjAzDxAlDzBtDtB~BrB~AxC~A|LfEvB`AnDjCdDbExIzPbiAp`CnQt^vJlQpKhObI|IhFzElJnHrI|FbyA``AjIxDjJfChHx@`EJ~EG`Iq@bsBsWzCm@`F}AxC{A|CwBnDiDrEoGnl@{jAfEaHzDoExDcDdb@yZzDuDhB{BjDaGnCwGlByGxAyI`A}M@aMsAu^mJgxBQoMPwKXwFhAiLhCoN`]}iAtFsU`FoVbDwRzDqY`J}z@bAuLZmGF_Jk@cMuBoQsHmj@oAuH{@}CkA_DkCwEqD{DcDuBsB{@gE}@yi@wHkGmAsHqBcKoE{JyGaV_SeJsFmCiCmDkFm[cj@mD_FoDcDoDoBkEmAoCYaBCcKt@yBEoCa@gA_@cE_CkAgAwBuCmB_Ek@kBoDqPaCqG_DqFqAaBkIqIgDsFsCuHuC}LeCoGsCaE}AwAgBmAeF{BuFkBaGmAuDMmBH}E~@qK|D_F|@sCT{MMaEPiC^ek@nPcH|AqCVkEHqDOs^wEkJi@qHA_GPsE\aJfA_HxAmMdEcj@tVsPtGuAV{AGkE_CqAUaBf@c@f@c@fAOfBDjAj@`CHpCLTY~GDrFXrE~@zFbA`EdChG`Sz\tBfEx@rCv@xEZdEH`FIrBcArJoYzgCkDjWqCdPiF|WiBzLqApLmAnS
</points>
</overview_polyline>

Décodage de la polyline

Le billet mentionné précédemment indique comment réaliser le décodage en Java.

On pourra notamment télécharger le code source Java : polyline-decoder .

On se ramène alors à la manipulation d'une liste de points en latitude et longitude.

Dans la démo html/JavaScript ci-dessus, on a réalisé une manipulation simple en créant des markers relatifs à ces positions GPS.

L'API JavaScript propose l'objet Polyline : in fine, une liste de points GPS. On obtient le tracé parfait de notre itinéraire, sous forme de polyline, simplement en ajoutant la polyline à la Map.

Ensuite, lorsqu'on déplace la carte, les markers ou la polyline suivent le mouvement en restant bien ancrés à la carte.

Est-ce aussi simple dans le cas d'un application Android?

Affichage dans une MapView Android

bordeaux-android

L'API pour une application Android est de plus bas niveau. Il n'y a pas de notion de polyline ou de markers géographiques.

Il convient alors de recourir à un tracé brutal dans le canvas. Et pour déduire la position (i,j) dans le canvas, il convient d'appliquer une projection...

Projection pj = map.getProjection();
	Point p = new Point();
	pj.toPixels(f, p);

Tracer une polyline parallèlement à une autre?

bordeaux-android-offset

Imaginons qu'on veuille visualiser le trafic routier le long d'un itinéraire, par exemple avec un code couleur vert/orange/rouge. Les conditions de circulation ne sont pas les mêmes dans un sens ou dans l'autre.

Pour faire propre, il convient alors de faire le tracé "traficolor" légèrement décalé de l'axe de la route. Ce qui permet de tracer les deux sens de part et d'autre de la route.

Comment faire? Ce n'est pas trivial. En quelque sorte c'est : 'décaler d'une distance fixe perpendiculairement au tracé local'.

Et aussi, quelque soit le zoom appliqué à la carte, la distance est constante.

bordeaux-android-zoom

Décalage local par géométrie euclidienne

Un peu de geométrie euclidienne permet de résoudre le problème. Notre polyline est une liste de points entre lesquels on trace des segments.

Considérons 2 points, à la suite, dans la liste, appelons les from et to. Ces deux points sont bien dans l'axe de la route. On cherche le point décalé de la distance fixe d, perpandiculairement au segment (from,to).

Considérons justement ce vecteur (from,to). Dans le plan, ce vecteur à la composante :

double a = to.x-from.x;
double b = to.y-from.y;

Si on chercher un vecteur normal à (a,b), on peut prendre (-b,a). Aussi, la droite qui passe par "to" et qui est perpendiculaire au segment (from,to) peut avoir une représentation paramétrique simple comme suit : x = -b*t; y=+a*t.

Pour toute valeur du paramètre t, la distance entre le point correspondant et "to" est simplement x²+y², soit aussi : b²*t² + a²*t².

Bref, on cherche le paramètre t, tel que cette distance vaut exactement la distance fixe d.

double t = Math.sqrt( d*d/(a*a+b*b));

Du coup, le point que l'on cherche est bien :

Point p = new Point();
p.x = -new Double(b*t).intValue() ;
p.y = +new Double(a*t).intValue() ;

D'accord, on voit maintenant comment déterminer chaque point localement décalé de façon perpendiculaire.

Performances?

Avec la MapView Android, à chaque fois qu'on effectue un panning du doigt, on a le redraw(.) qui est invoqué. Ce qui veut dire qu'on a systématiquement les calculs de projection et de trigonométrie qui s'applique sur tous les points de la polyline.

A-t-on bien une réactivité temps réel? Il s'avère qu'on a bien une réacivité parfaite. Pour preuve la démonstration suivante à ouvrir avec un téléphone Android : bordeaux.apk .

On prend tout de même le soin d'écarter du traitement les points qui sont en dehors de la zone visible de la carte.

Pour ne pas qu'il y ait de phénomène de bord pour les segments, on considère la zone d'exclusion plus grande que la zone visible.

/**
 * @return Rect corresponding to twice the @param mapView viewport
 */
public static Rect toRectx2(MapView mapView) {
	int w = mapView.getLongitudeSpan();
	int h = mapView.getLatitudeSpan();
	int cx = mapView.getMapCenter().getLongitudeE6();
	int cy = mapView.getMapCenter().getLatitudeE6();
	return new Rect(cx-w, cy-h, cx+w, cy+h);
}

Avec un test du genre :

Rect viewRect = toRectx2(map);
boolean visible = viewRect.contains(f.getLongitudeE6(), f.getLatitudeE6());

Trafic Futé, application Android de trafic routier

Ces divers recettes on permis de réaliser trafic-futé ' une application Android qui présente le trafic routier sur une Google Maps. Avec pour source de données Bison Futé, une garantie de données pertinentes aux abords des villes, là où on retrouve la plupart de bouchons.

tf_lyon

Trafic Futé disponible dans l'Android Market, voir la page coutant .

Je la distribue en open-source GPL v3, le code source est disponible ici : github.com/scoutant/tf

vendredi, août 13 2010

Itinéraires Google Maps et Encoded Polyline Algorithm Format

On a tous utilisé les services web en ligne de calcul d'itinéraire avec maps.google.com...

On peut aussi utiliser la Google Maps API si on souhaite faire une intégration dans son propre site web ou blog. Et on peut aussi utiliser les serices web REST de la Google Maps API pour une intégration coté server.

L'itinéraire est explimé de façon textuelle et aussi à travers un tracé founi de façon encodé via l'Encoded Polyline Algorithm Format. C'est ce que nous alons voir ici. Et notamment une solution de décodage en Java.

Calcul d'itinéraire avec Google Maps API

L'API Google Maps est là depuis longtemps. On notera simplement que depuis le V3, il n'est plus nécessaire d'avoir à manipuler de clé. Pour ce qui est de l'accès gratuit, on peut invoquer 2500 fois les services web Google Maps par tranche de 24h.

Pour ce qui est de la techno client, on peut opter classiquement pour du JavaScript. Mais on a aussi la Google Maps API for Flash.

On a aussi aussi la possibilité d'invoquer les services web de cartographie de façon agnostique : par simples requêtes Http en style REST pour obtennir un résultat textuel en Xml ou Json avec Google Maps API Web services .

Par exemple pour un calcul d'itinéraire, ici de Concorde au Trocadero :

concorde-trocadero

L'url pour obtenir une version purement textuel de cet itinéraire : http://maps.google.com/maps/api/directions/json?sensor=false&origin=trocadero,paris&destination=concorde,paris&mode=walking

On notera dans la réponse l'élément overview_polyline :

{
  "status": "OK",
. . .
      "duration": {
        "value": 1902,
        "text": "32 minutes"
      },
      "distance": {
        "value": 2579,
        "text": "2,6 km"
      },
    "overview_polyline": {
      "points": "isfiH{t}L@aBf@{@eHma@i@uFw@o_@LmAx@aDRqCMyE}@}|ABa@Vw@@_DMm@H[?mCCi@e@MqA{@",

On a une description textuelle de l'iténéraire avec aussi une description graphique sous forme de polyline : ensemble de segments ou liste de points GPS.

Cette liste est verbeuse et Google en propose une version encodé au format Encoded Polyline Algorithm Format : un encodage base64 de la latitude et de la longitude.

Polyline et encodage Encoded Polyline Algorithm Format

Le mathématicien McClure propose sur son site les algorithmes d'encodage et de décodage. Par exemple on peut utiliser le décodeur en ligne pour obtenir les 20 points GPS correspondant à l'itinéraire ci-dessus.

Avec le décodeur ci-dessus, la polyline Concorde-Trocadero encodée en isfiH{t}L@aBf@{@eHma@i@uFw@o_@LmAx@aDRqCMyE}@}|ABa@Vw@@_DMm@H[?mCCi@e@MqA{@ donne :

48.86341, 2.28702
48.86340, 2.28751
48.86320, 2.28781
48.86467, 2.29332
. . .
48.86516, 2.32041
48.86557, 2.32071

markers-trocadero-concorde

Un click dans l'image ci-dessus, permet d'accéder à la version interactive...

Ce décodeur est écrit en Javascript, voir le code source : decode.js.

Décodage de la polyline en Java

Cas de figure : on souhaite développer un serveur en Java, s'appuyant sur les services web REST de calcul d'itinéraire Google Maps. Notre serveur pourra décoder la polyline représentant l'itinéraire pour, par exemple, insérer l'insérer dans une base de données géographique : typiquement dans PostGIS.

Sur son site web, McClure mentionne un portage Java de son algorythme d'encodage : JavaPolylineEncoder. Mais pas de lien pour l'opération inverse : le décodage.

Le code javascript decode.js, vu ci-dessus, peut facilement être porté en Java. C'est ce que j'ai été amené à faire. github Si vous en avez l'utilité, vous pouvez télécharger le code de GitHub : polyline-decode. C'est un petit projet complet avec build Maven et tests unitaires. Vous pouvez utiliser uniquement la classe PolylineDecoder.java.