Etape 6 – Conversion OSM vers géométrie

1 Introduction

Ayant écrit les classes permettant de représenter les entités géométriques des cartes, ainsi que celles permettant de charger les entités OpenSteetMap en mémoire à partir d'un fichier OSM, il reste à faire le lien entre les deux. C'est le but de cette étape, qui consiste à écrire une classe permettant de représenter les cartes — en coordonnées projetées — ainsi qu'une classe de conversion des entités OSM en entités géométriques attribuées.

Seuls deux types d'entités OSM doivent être convertis en entités géométriques : les chemins et les relations décrivant des multipolygones.

1.1 Conversion des chemins

La conversion d'un chemin OSM est très simple : s'il est fermé et que ses attributs indiquent qu'il décrit une surface, alors il est converti en polygone sans trou ; sinon, il est converti en polyligne. Dans les deux cas, la conversion consiste à projeter la position des nœuds composant le chemin pour obtenir une séquence de points, puis à construire un polygone ou une polyligne avec ces points.

Un chemin fermé décrit une surface soit s'il possède l'attribut area avec la valeur yes, 1 ou true, soit s'il possède l'un des attributs ci-dessous, avec une valeur quelconque :

"aeroway", "amenity", "building", "harbour", "historic",
"landuse", "leisure", "man_made", "military", "natural",
"office", "place", "power", "public_transport", "shop",
"sport", "tourism", "water", "waterway", "wetland"

(Cette liste d'attributs vous est donnée en syntaxe Java pour faciliter sa copie dans votre code.)

1.2 Conversion des multipolygones

La conversion d'une relation décrivant un multipolygone est passablement plus complexe que celle d'un chemin et mérite donc d'être décrite en détail.

Afin de faciliter la compréhension de la conversion, celle-ci sera illustrée sur l'exemple de la figure ci-dessous, qui montre une relation décrivant un multipolygone. Cette relation possède 8 membres de type chemin, nommés C₁ à C₈ et différenciés par leur couleur. Trois de ces chemins — C₅, C₆ et C₈ — ont le rôle inner et sont dessinés en traitillés, tandis que les autres ont le rôle outer et sont dessinés de manière continue.

Figure 1 : Une relation multipolygone composée de 8 chemins

Le multipolygone décrit par cette relation doit être converti en les trois polygones suivants :

un polygone sans trou dont l'enveloppe est le chemin C₁,
un polygone à trou dont l'enveloppe est composée des chemins C₂, C₃ et C₄ et l'unique trou des chemins C₅ et C₆,
un polygone à trou dont l'enveloppe est le chemin C₇ et l'unique trou le chemin C₈.

La conversion se fait en trois étapes :

les chemins de la relation sont séparés en deux ensembles en fonction de leur rôle — d'un côté les chemins extérieurs (rôle outer), de l'autre les chemins intérieurs (rôle inner),
les chemins de chacun de ces ensembles sont regroupés en fonction des nœuds à leurs extrémités pour former des polylignes fermées que nous nommerons anneaux (intérieurs et extérieurs),
pour chaque anneau extérieur un polygone est créé, dont les trous sont tous les anneaux intérieurs qu'il contient et qui ne sont pas contenus dans un autre anneau extérieur plus petit.

La séparation des chemins par rôle (étape 1) est très simple puisque chaque membre d'une relation multipolygone doit avoir soit le rôle inner soit le rôle outer. Les deux étapes suivantes sont quant à elles plus complexes et méritent chacune une description plus détaillée.

Construction des anneaux

Pour construire les anneaux correspondant à un ensemble de chemins, on peut s'aider d'un graphe non orienté dont les nœuds sont les nœuds des chemins. Deux nœuds de ce graphe sont reliés par une arête si et seulement si ils se suivent dans l'un des chemins. Pour le multipolygone d'exemple, le graphe correspondant aux chemins extérieurs est représenté dans la figure ci-dessous.

Figure 2 : Graphe des chemins extérieurs du multipolygone

Une fois ce graphe construit, il reste à en extraire les anneaux. Pour ce faire, nous utiliserons une technique qui a l'avantage d'être simple mais l'inconvénient de ne pas fonctionner dans la totalité des cas, comme cela est expliqué plus bas. Heureusement, les cas problématiques se rencontrent très rarement en pratique.

La limitation de cette technique est qu'elle ne fonctionne que si tous les nœuds du graphe ont exactement deux voisins. Si tel n'est pas le cas, elle échoue simplement en produisant un ensemble d'anneaux vide.

Par contre, si chaque nœud du graphe possède exactement deux voisins, elle en extrait les anneaux en procédant ainsi : tant que le graphe contient au moins un nœud non visité, l'un d'entre-eux est choisi comme premier nœud d'un nouvel anneau. Ensuite, l'un de ses voisins non visité est également ajouté à l'anneau. Et ainsi de suite, jusqu'à ce que l'on retombe sur le nœud de départ, ce qui signale que l'anneau est terminé. Cette procédure est répétée tant et aussi longtemps qu'il reste au moins un nœud non visité dans le graphe.

La figure ci-dessous montre les cinq anneaux extraits par cette technique pour le multipolygone d'exemple. Trois d'entre-eux — nommés E₁, E₂ et E₃ — sont des anneaux extérieurs et ils ont été obtenus à partir du graphe des chemins extérieurs présenté ci-dessus. Les deux autres anneaux sont des anneaux intérieurs, obtenus à partir du graphe des chemins intérieurs, qui n'a pas été présenté.

Figure 3 : Anneaux intérieurs et extérieurs du multipolygone

Construction des polygones

Il est évident qu'à chaque anneau extérieur doit correspondre un polygone. Par contre, décider à quel polygone attacher chacun des anneaux intérieur est moins évident.

On pourrait imaginer qu'il suffit d'attacher chaque anneau intérieur à l'anneau extérieur qui le contient, mais ce n'est pas le cas car un anneau intérieur peut très bien être inclu dans plusieurs anneaux extérieurs. Dans notre exemple, il en va ainsi de l'anneau intérieur I₂.

Toutefois, en raffinant un peu cette idée, on obtient une solution valide : tout anneau intérieur doit être associé au plus petit anneau extérieur qui le contient.

En appliquant cette règle aux anneaux extraits lors de la phase précédente, on obtient finalement les trois polygones correspondant à la relation d'exemple, présentés dans la figure ci-dessous. Comme d'habitude, les couleurs distinguent les différents objets — ici les polygones — tandis que le type de trait permet de différencier les enveloppes des trous.

Figure 4 : Polygones du multipolygone

Limitations

La technique de conversion de relations multipolygones en polygones décrite ci-dessus permet de convertir correctement l'immense majorité de ces relations présentes dans les données OpenStreetMap, mais malheureusement pas toutes. Parfois, cela est dû au fait qu'une relation est invalide, p.ex. car elle ne comporte aucun chemin avec le rôle outer. Mais il existe aussi des relations multipolygones valides selon le modèle OpenStreetMap que la technique ci-dessus ne sait convertir correctement.

La figure ci-dessous illustre une telle relation valide mais problématique pour notre algorithme de conversion. Le problème ici est dû aux deux nœuds partagés entre les chemins intérieurs C₂ et C₃. Lors de la tentative de construction des anneaux intérieurs, les nœuds du graphe leur correspondant auront plus de 2 voisins, rendant le graphe inutilisable par la technique présentée plus haut.

Figure 5 : Une relation multipolygone valide mais problématique

Il est possible de définir un algorithme de conversion plus complexe gérant également ces cas, mais étant donné que celui donné ci-dessus convertit l'immense majorité des relations valides des données OpenStreetMap, nous nous en contenterons.

1.3 Attributs

En plus de leur géométrie dont la conversion est décrite ci-dessus, les entités OpenStreetMap comportent des attributs. Lors de la conversion de données OSM en carte composée d'entités géométriques attribuées, il convient donc de savoir comment gérer ceux-ci.

Attachement

N'importe quelle entité OpenStreetMap — nœud, chemin ou relation — peut posséder des attributs. Les entités géométriques que nous avons définies — polylignes et polygones — et à partir desquelles nous dessinerons nos cartes ne possèdent quant à elles pas directement d'attributs. Pour attacher un ensemble d'attributs à une telle entité, il convient d'utiliser la classe Attributed pour former une paire composée d'une entité géométrique et d'un ensemble d'attributs.

Cette différence a une conséquence importante en ce qui concerne les relations. En effet, une relation étant une entité OpenStreetMap, elle peut posséder des attributs. Mais ses membres, en tant qu'entités OpenStreetMap à part entière, peuvent aussi en posséder. Dès lors, la question se pose de savoir comment déterminer les attributs à attacher à un polygone obtenu à partir d'une relation OpenStreetMap.

Les règles « officielles » du projet OpenStreetMap à ce sujet sont complexes et ambigües. Nous ne les utiliserons donc pas ici, et nous contenterons d'une règle très simple qui, en pratique, fonctionne extrêmement bien avec les données réelles : les attributs de tous les polygones produits à partir d'une relation multipolygone sont ceux attachés à cette relation. En d'autres termes, les éventuels attributs des membres de la relation sont totalement ignorés pour le calcul des attributs des polygones correspondant à cette relation.

Filtrage

Les entités OpenStreetMap possèdent souvent une très grande quantité d'attributs, mais seul un petit sous-ensemble d'entre-eux est utile au dessin des cartes. Il en va par exemple ainsi de l'attribut permettant de donner la vitesse maximale autorisée sur une route.

Afin de minimiser la taille des données stockées en mémoire, il est donc judicieux de filtrer les attributs attachés aux données OpenStreetMap pour n'en garder que le sous-ensemble utile par la suite.

Pour les polylignes, seuls les attributs ci-dessous doivent être gardés, quelle que soit leur valeur :

"bridge", "highway", "layer", "man_made", "railway",
    "tunnel", "waterway"

tandis que pour les polygones, seuls les attributs ci-dessous doivent l'être :

"building", "landuse", "layer", "leisure", "natural",
    "waterway"

Notez que si, après filtrage, une entité géométrique ne possède plus aucun attribut, elle doit être ignorée. En effet, le dessin des cartes se fera en fonction des attributs, et une entité qui n'en possède aucun ne saurait avoir de représentation graphique.

2 Mise en œuvre Java

2.1 `Map`

La classe Map du paquetage ch.epfl.imhof, publique, finale et immuable, représente une carte projetée, composée d'entités géométriques attribuées. Bien entendu, malgré le nom identique, cette classe n'a rien à voir avec l'interface Map de la biliothèque Java.

La classe Map ne possède qu'un constructeur public :

Map(List<Attributed<PolyLine>> polyLines, List<Attributed<Polygon>> polygons), qui construit une carte à partir des listes de polylignes et polygones attribués donnés.

La classe Map est de plus dotée des méthodes publiques d'accès suivantes :

List<Attributed<PolyLine>> polyLines(), qui retourne la liste des polylignes attribuées de la carte,
List<Attributed<Polygon>> polygons(), qui retourne la liste des polygones attribués de la carte.

2.2 `Map.Builder`

La classe Map.Builder, publique et imbriquée statiquement dans la classe Map, sert de bâtisseur à cette dernière. Elle ne possède pas de constructeur autre que celui par défaut mais est dotée des trois méthodes publiques ci-dessous :

void addPolyLine(Attributed<PolyLine> newPolyLine), qui ajoute une polyligne attribuée à la carte en cours de construction,
void addPolygon(Attributed<Polygon> newPolygon), qui ajoute un polygone attribué à la carte en cours de construction,
Map build(), qui construit une carte avec les polylignes et polygones ajoutés jusqu'à présent au bâtisseur.

2.3 `OSMToGeoTransformer`

La classe OSMToGeoTransformer du paquetage ch.epfl.imhof.osm, publique, finale et immuable, représente un convertisseur de données OSM en carte. Elle possède un unique constructeur public :

OSMToGeoTransformer(Projection projection), qui construit un convertisseur OSM en géométrie qui utilise la projection donnée.

Cette classe est également dotée de la méthode publique suivante :

Map transform(OSMMap map), qui convertit une « carte » OSM en une carte géométrique projetée.

Même si cette classe ne comporte qu'une seule méthode publique, il est fortement conseillé, au vu de sa complexité, de définir plusieurs méthodes privées. Par exemple, une solution pourrait être de définir les méthodes privées suivantes :

List<ClosedPolyLine> ringsForRole(OSMRelation relation, String role), qui calcule et retourne l'ensemble des anneaux de la relation donnée ayant le rôle spécifié. Cette méthode retourne une liste vide si le calcul des anneaux échoue.
List<Attributed<Polygon>> assemblePolygon(OSMRelation relation, Attributes attributes), qui calcule et retourne la liste des polygones attribués de la relation donnée, en leur attachant les attributs donnés.

La méthode ringsForRole se charge des étapes 1 et 2 mentionnées plus haut, tandis que la méthode assemblePolygon se charge de l'étape 3, en s'aidant de la méthode ringsForRole.

Une manière efficace d'attacher chaque anneau intérieur au plus petit anneau extérieur qui le contient consiste à parcourir les anneaux extérieurs du plus petit au plus grand. A chacun de ces anneaux extérieurs sont attachés tous les anneaux intérieurs qu'il contient.

Pour trier les anneaux par aire croissante, on peut utiliser la variante de la méthode sort de la classe Collections qui prend un comparateur en argument. Ce dernier doit savoir comparer deux anneaux — de type ClosedPolyLine — en fonction de leur surface.

Pour déterminer si un anneau en contient un autre, vous pouvez faire l'hypothèse que les anneaux ne se chevauchent pas. Dès lors, un anneau en contient un autre si et seulement si il contient l'un de ses points.

2.4 Tests

Comme précédemment, nous ne vous fournissons pas de tests unitaires pour cette étape mais uniquement un fichier de vérification de noms, contenu dans une archive Zip à importer dans votre projet.

3 Résumé

Pour cette étape, vous devez :

écrire les classes Map, Map.Builder et OSMToGeoTransformer en fonction des spécifications données plus haut,
vous assurer que le fichier de vérification de noms fourni, une fois importé dans votre projet, ne contient aucune erreur,
tester votre code et corriger les éventuels problèmes rencontrés,
documenter la totalité des entités publiques que vous avez définies,
rendre votre code avant le 27 mars 2015 à 16h00 via le système de rendu.

Attention : ce rendu est le rendu testé, qui compte pour 25% de la note du projet. N'oubliez donc pas rendre votre projet bien avant la date limite — quitte à continuer à l'améliorer et à refaire un rendu ultérieurement — car comme d'habitude aucun rendu ne sera accepté en retard !