image/svg+xml $ $ ing$ ing$ ces$ ces$ Res Res ea ea Res->ea ou ou Res->ou r r ea->r ch ch ea->ch r->ces$ r->ch ch->$ ch->ing$ T T T->ea ou->r

Serveur de points d'intérêt

  1. Des points très intéressants
  2. Obtention des points les plus proches
  3. Verticle des points les plus proches
  4. Utilisation depuis l'activité Android
  5. Navigation de point en point
  6. Affichage sur une carte

Wikipedia regorge d'informations intéressantes ; on remarquera notamment que certains articles sont géolocalisés lorsqu'ils se rapportent à un lieu. Nous souhaiterions réaliser un serveur web capable de nous retourner les points d'interêt référencés sur Wikipedia les plus proches de notre position géographique.

Des points très intéressants

Wikimedia propose en téléchargement le contenu des bases de données alimentées par le travail collaboratif des contributeurs de Wikipedia. Ces bases sont assez volumineuses : nous pouvons par exemple télécharger un fichier compressé bzip2 contenant l'ensemble des articles au format XML. On constate alors que certains articles comportent une latitude et une longitude dans leur corps exprimée de la façon suivante. Prenons l'exemple de l'article "Conférence de Yalta" :

<text>
{Infobox Événement
|image = Yalta Conference 1945 Churchill, Stalin, Roosevelt.jpg
|légende = Les dirigeants [[Alliés de la Seconde Guerre mondiale|alliés]] à la conférence. De gauche à droite : [[Winston Churchill|Churchill]], [[Franklin Delano Roosevelt|Roosevelt]] et [[Joseph Staline|Staline]].
|type = Conférence diplomatique
|création =
|édition =
|pays = URSS 1923-1955
| latitude = 44.467778
| longitude = 34.143333
|localisation = [[Palais de Livadia]], [[Yalta]]
|commissaire =
|date = [[4 février|4]] au {{date|11|février|1945}}
|participant = {{drapeau|Union soviétique|1923}} [[Joseph Staline]]<br>{{drapeau|USA|1912}} [[Franklin Delano Roosevelt|Franklin D. Roosevelt]]<br>{{UK-d}} [[Winston Churchill]]
|fréquentation =
|site web =
|précèdent =
|suivant =
|géolocalisation=Crimée/Europe
}}
La '''conférence de Yalta''' est une réunion des principaux responsables de l'[[Union des républiques socialistes soviétiques|Union soviétique]] ([[Joseph Staline]]), du [[Royaume-Uni]] ([[Winston Churchill]]) et des [[États-Unis]] ([[Franklin Delano Roosevelt|Franklin D. Roosevelt]]).
...
</text>

Les coordonnées géographiques sont exprimées sous la forme | latitude = ... | longitude = .... Pour extraire ces informations, nous pouvons utiliser une bibliothèque XML pour analyser le fichier, récupérer le contenu de l'article entre balises <text>...</text> puis ensuite écrire une expression régulière pouvant capturer les informations géographique.

Le fichier XML compressé occupant environ 5 Go (et plusieurs dizaines de Go décompressé), l'extraction de ces informations pour tous les articles peut prendre plusieurs dizaines de minutes.

Pour ce TP, vous n'avez pas à mettre en œuvre cette étape : vous pouvez télécharger directement ici un fichier avec les titres d'articles associés à leur coordonnées géographiques (informations extraites depuis frwiki-20211020-pages-articles.xml.bz2). Ce fichier comporte 219469 entrées.

Pour charger ce fichier de points en mémoire dans un programme Java, nous ouvrons un Scanner ou un BufferedReader, et nous le lisons ligne par ligne.

Nous pouvons ensuite créer pour chaque ligne un GeoPoint, instance de la classe suivante :

public class GeoPoint {
	public final String name;
	public final float latitude;
	public final float longitude;
	
	public GeoPoint(String name, float latitude, float longitude) {
		this.name = name;
		this.latitude = latitude;
		this.longitude = longitude;
	}
	
	public static GeoPoint fromFileLine(String line) {
		String[] parts = line.split("\t");
		return new GeoPoint(
			parts[0].
			Float.parseFloat(parts[1]),
			Float.parseFloat(parts[2]));
	}
}

Ecrivez une méthode List<GeoPoint> loadGeoPoints(String filepath) chargeant tous les points provenant d'un fichier et retournant une liste de ces points. Testez la méthode écrite sur le fichier des points Wikipedia fourni en écrivant une méthode main.

Obtention des points les plus proches

Nous souhaitons rechercher les points les plus proches de notre position actuelle. Pour cela nous allons trier la liste de points selon leur distance à notre position. On utilise la méthode sort(Comparator<? super T> cmp) de List<T>. Nous allons devoir écrire un comparateur à passer en paramètre à sort : ce comparateur prend deux points en paramètres et retourne une valeur pour indiquer si le 1er point est à une distance inférieure de nous du 2ème (valeur <0) ou alors si le 1er point est plus éloigné que le 2ème (valeur >0). Si les deux points sont les mêmes (mêmes coordonnées), il retourne 0.

Ecrivez le comparateur requis ; vous pourrez alors à partir de celui-ci écrire une méthode void sort(List<GeoPoint> pointList, float lat, float lon) triant la liste selon la position actuelle. Pour calculer la distance entre deux coordonnées, vous pouvez utiliser la distance à vol d'oiseau sur le globe terrestre qui utilise la formule de Haversine. Vous pouvez en trouver une implantation en Java ici (n'oubliez pas de créditer la source lorsque vous utilisez du code extérieur).

Verticle des points les plus proches

Nous allons maintenant proposer un service web permettant à tout client web de récupérer les points d'interêts les plus proches d'une position qu'il spécifie. Notre service web pourra par exemple s'interroger en utilisant l'URL :

http://localhost:8080/nearestPoints/:latitude/:longitude

Nous retournons les 10 points les plus proches des coordonnées. Pour cela nous devons :

Nous retournons les points sous la forme d'un JsonArray contenant des JsonObject pour chacun des points (avec ses propriétés) :

req -> {
	JsonArray ja = ...; // to be created with all the points
	req.response()
		.putHeader("Content-Type", "application/json")
		.end(ja.encodePrettily());
}

Pour vous aider à créer le JsonArray, vous pouvez doter la classe GeoPoint d'une méthode toJsonObject() retournant un JsonObject à partir de this.

Nous pouvons constater que le calcul (tri de la liste) de la réponse n'est pas instantané. Une seule requête peut ainsi être traitée à la fois par Vert.x. Pour un traitement long comme cela a lieu ici, nous devons envelopper le calcul long avec vertx.executeBlocking(() -> { ... }). D'autre part, il est possible que plusieurs requêtes puissent être traitées simultanément et donc que plusieurs tris de liste soient exécutés en concurrence : ceci est problématique car la structure de liste serait alors mise dans un état incohérent. Pour éviter ce soucis, nous pouvons conserver une liste immuable obtenue par le chargement du fichier puis cloner cette liste avant chaque tri :

private List<GeoPoint> points; // immutable list

List<GeoPoint> getNearestPoints(float latitude, float longitude, int number) {
	List<GeoPoint> clonedPoints = new ArrayList<>(points);
	clonedPoints.sort((p1, p2) -> { ... }); // sort with the comparator
	return new ArrayList<GeoPoint>(clonedPoints.subList(0, 10));
};

☞ Il est possible de faire encore mieux en utilisant un TreeSet pour stocker uniquement les k point les plus proches de la position communiquée. On rajoute les k premiers points de la liste dans le TreeSet puis on ajoute les points suivants un par un tout en prenant le soin à chaque itération d'éliminer le point le plus éloigné. A la fin, le TreeSet contient les k points lesp lus proches. On peut aussi utiliser une PriorityQueue avec une complexité similaire.

Utilisation depuis l'activité Android

Reprenez l'activité Android d'interrogation du serveur du TP précédent et réalisez une requête vers le verticle que vous venez d'écrire en utilisant la position géographique indiquée. Affichez les points d'intérêt les plus proches dans un TextView. Vous pouvez ensuite remplacer le TextView par une ListView (scrollable par défaut) affichant la liste des points.

Pour utiliser une ListView, vous pouvez récupérer la référence de la ListView installée sur le layout et lui associer un ArrayAdapter comme ceci :

// points is the ArrayList containing the points
ListView lv = findViewById(R.id.listView);
ArrayAdapter<GeoPoint> itemsAdapter = 
    new ArrayAdapter<String>(this, android.R.layout.simple_list_item_1, points);
lv.setAdapter(itemsAdapter);

Par défaut, l'ArrayAdapter permet l'afficheage de chaque item sur un TextView avec l'appel à la méthode toString() de GeoPoint. Cette méthode doit donc être redéfinie.

Il est possible aussi dans un second temps d'utiliser un layout personnalisé pour l'affichage de chaque item en redéfinissant la méthode getView() de l'ArrayAdapter :

ArrayAdapter<GeoPoint> itemsAdapter = 
	new ArrayAdapter<GeoPoint>(this, android.R.layout.simple_list_item_1, points) {
		@Override
		public View getView(int position, View convertView, ViewGroup parent) {
			if (convertView == null) { // the view must be initialized
				convertView = LayoutInflater.from(getContext()).inflate(R.layout.point_item, parent, false);
			}
			// now we fetch the views and cell the setters to assign values to them
			...
       }
	};

Navigation de point en point

Ajoutez une action lorsque vous cliquez sur l'un des points d'intérêt sur la liste afin de remplacer les coordonnées indiquées par celles du point. Réalisez ensuite une nouvelle requête pour trouver les points les plus proches de cette nouvelle position (qui comprendra le point lui-même en première position).

Pour pouvoir agir lors d'un clic sur un item de la liste, nous pouvons ajouter un OnItemClickListener :

listView.setOnItemClickListener(new OnItemClickListener() {
    @Override
    public void onItemClick(AdapterView<?> arg0, View arg1, int position, long arg3) {
        GeoPoint point = points.get(position);
        // ... set the coordinates of the point as the new coordinates 
        // and order to fetch new points from the webservice
    }
});

Affichage sur une carte

A venir si on a le temps...