Maillage et distorsion de fonds de cartes pour la visualisation de flux géolocalisés // Meshing and Distortion of Base Maps for the Visualization of Geo-Located Flows

La visualisation de données relationnelles géolocalisées consiste à concevoir et proposer des algorithmes permettant de représenter, et éventuellement d'interagir avec, des entités géographiques reliées par des liens [SYP2021]. Parmi les approches proposées dans ce cadre, certaines concernent plus spécifiquement la visualisation de flux (e.g. échanges commerciaux). Introduites dès le XIXème siècle [R2018], les cartes de flux consistent à représenter les entités géographiques à l'aide d'un fond de carte, et d'y superposer les liens sous forme de courbes dont l'épaisseur représente la magnitude du flux [PXY2005, KSV2011, NB2013, DSA2014, JSM2017, S2018]. La plupart de ces approches utilisent des algorithmes par simulation de forces pour dessiner ces liens de façon à éviter leur superposition, et ainsi garantir leur visibilité. En revanche, peu d'attention a été portée à la visibilité des entités géographiques du fond de carte. Récemment, l'équipe ADVANSE du LIRMM a proposé une méthode de dessin de flux maritimes « un-à-plusieurs » (i.e. une seule origine et plusieurs destinations) tenant compte des entités géographiques contenues dans le fond de carte afin de dessiner des flux se superposant au minimum avec ces entités [VSR23]. Cette méthode est basée sur un « routage des flux » le long d'un maillage des zones maritimes construit de façon à privilégier les zones les plus éloignées des côtes. Le premier objectif de cette thèse est de généraliser cette approche à d'autres types de cartes (zones terrestres, urbaines) et à des flux « plusieurs-à-plusieurs » (plusieurs origines et plusieurs destinations). Différentes techniques de maillage pourront être envisagés (grilles régulières, triangulations de Delaunay, axes médians, squelettes rectilignes…). Elles devront s'adapter aux entités géographiques contenues dans le fond de carte pour garantir la visibilité de ces dernières.

Par ailleurs, la déformation de fonds de cartes est une approche régulièrement employée pour faciliter la lecture de données relationnelles géolocalisées. Elle a, par exemple, été employée pour la visualisation de réseaux de métros [NW2011], de réseaux routiers [HS2011, vDH2014] ou plus généralement de graphes [BKA2015] ou de distances [BDD2013]. Dans l'article [VSR23] précédemment introduit, l'équipe ADVANSE a également proposé une méthode de distorsion de fond de carte non pas pour encoder directement des données comme c'était fait dans les travaux antérieurs, mais pour faire en sorte que des données relationnelles affichées au-dessus du fond de carte ne masquent pas ce fond de carte. Le second objectif de cette thèse est d'explorer ce paradigme, notamment en généralisant la technique à d'autres types de fonds de cartes et à d'autres types de visualisations affichées au premier plan. Pour cela, le doctorant devra concevoir différentes approches de déformation basées sur des techniques de type fisheye polyfocal [KS1978], optimisation d'une fonction d'énergie [SRQ2014], ou encore inspirées des algorithmes de suppression de chevauchements des nœuds d'un graphe [CPP2020].
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

The visualization of geolocated relational data involves designing and developing algorithms that allow for the representation of and potentially interaction with geographic entities connected by links [SYP2021]. Among the approaches proposed in this context, some focus more specifically on the visualization of flows (e.g., trade exchanges). Introduced as early as the 19th century [R2018], flow maps represent geographic entities using a base map, over which links are drawn as curves whose thickness reflects the magnitude of the flow [PXY2005, KSV2011, NB2013, DSA2014, JSM2017, S2018]. Most of these approaches rely on force-directed algorithms to draw links in a way that avoids overlapping, thus ensuring their visibility. However, little attention has been given to the visibility of the geographic entities in the base map. Recently, the ADVANSE team at LIRMM proposed a method for drawing one-to-many maritime flows (i.e., a single origin and multiple destinations) that takes into account the geographic entities present in the base map, in order to minimize overlap between flows and those entities [VSR23]. This method is based on 'flow routing' along a mesh of maritime zones constructed to favor areas farthest from the coastline. The primary goal of this thesis is to generalize this approach to other types of maps (land or urban areas) and to 'many-to-many' flows (multiple origins and multiple destinations). Different meshing techniques may be considered (regular grids, Delaunay triangulations, medial axes, straight skeletons, etc.). These techniques must adapt to the geographic entities in the base map to ensure their visibility.

Additionally, map distortion is a commonly used approach to improve the readability of geolocated relational data. It has been applied, for instance, to the visualization of metro networks [NW2011], road networks [HS2011, vDH2014], and more generally to graphs [BKA2015] or distance representations [BDD2013]. In the previously introduced paper [VSR23], the ADVANSE team also proposed a method for map background distortion, not to directly encode data as in earlier works, but rather to ensure that relational data displayed on top of the map does not hide the base map itself. The second objective of this thesis is to explore this paradigm further, particularly by generalizing the technique to other types of base maps and foreground visualizations. To achieve this, the PhD student will design various distortion techniques, drawing from polyfocal fisheye approaches [KS1978], energy function optimization [SRQ2014], or algorithms inspired by node-overlap removal in graph layouts [CPP2020].
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Début de la thèse : 01/10/2025

Contrat doctoral

Concours pour un contrat doctoral

Université de Montpellier

166 I2S - Information, Structures, Systèmes

Idéalement, le candidat devra avoir des connaissances en visualisation de données, ou le cas échéant en computer graphics. Il devra également avoir de solides bases en algorithmique et en programmation. Une bonne maitrise de librairies de programmation graphique, telles que D3.js ou autres, sera appréciée, ainsi qu'un niveau solide d'anglais.
Ideally, the candidate should have knowledge in data visualization, or alternatively in computer graphics. They should also have a strong foundation in algorithms and programming. Proficiency in graphical programming libraries such as D3.js (or similar) will be appreciated, as well as a solid level of English.