Thèse numérisée par la Direction des bibliothèques de l'Université de Montréal.

Thèse : Mécanique : Faculté des sciences de Paris : 1852. Thèse : Astronomie : Faculté des sciences de Paris : 1852. / Titre provenant de l'écran-titre.

Les travaux présentés dans cette thèse visent à proposer des méthodes pour résoudre les problèmes de la sectorisation multicritère en cartographie. En premier temps, nous avons défini les problèmes différents de la sectorisation et nous avons établi les liens entre ces problèmes avec les problèmes classiques qui sont bien étudiés dans la littérature : le problème de découpage de district politique, les problèmes de localisation et le problème du partitionnement de graphe. Deux types de méthodes ont été abordés pour résoudre les problèmes de sectorisation. Des heuristiques ont été développées et elles consistent à calculer un optimum de Pareto pour les différents problèmes. Et pour le problème de sectorisation à partir de pôles, nous avons aussi utilisé et expérimenté un algorithme de boîte pour trouver une représentation du front de pareto. La méthode exacte branch and bound a été utilisée pour résoudre le problème de sectorisation sans pôle prédéfini optimalement. Avant que nous appliquons cette procédure, nous ajoutons quelques inégalités valides dans la formulation mathématique pour restreindre l'espace des solutions et nous développons une procédure de prétraitement pour réduire la taille du problème. / The work presented in this thesis aims to propose methods to solve the multicriteria map sectorization problem in cartography. Firstlly, we have defined the different sectorization problems and we have established the links between these problems with some classical problems which are well studied in the literature : political districting problem, locationallocation problems and constrained graph partitioning problems. Two types of methods have been proposed to solve the sectorization problem. Heuristics have been developed and they compute an optimum Pareto for the different sectorization problems. And for the sectorization problem with predefined centers, we have used a box algorithm and experimented it to find a representation of the Pareto front. The branch and bound method was used to solve optimally the sectorization problem without predefined centers. Before we apply this procedure, we add some valid inequalities in the mathematical formulation for restrict the space of solutions and we develop a preprocessing procedure to reduce the size of the problem.

Les systèmes de projection cartographique adaptés aux services de cartographie web, suscitent encore de nombreuses questions de recherche. La majorité des services de cartographie Web (ex. Google Maps, Bing Maps) utilise la Projection Web Mercator(WMP), mais cette dernière présente de grandes distorsions systématiques notamment dans les régions nordiques. Il nous est alors paru nécessaire de développer une autre méthode permettant de projeter la surface du globe avec un minimum de distorsion. Notre approche s’inspire de la projection myriahedrale qui suppose que chaque face du myriahedron est suffisamment petite de telle sorte que les distorsions soient négligeables. La méthode proposée consiste à explorer une nouvelle approche de tessellation de la surface du globe et qui permet de projeter la surface du globe sur les faces de la tessellation et à plusieurs niveaux de détails. Cela permet de compenser la faiblesse des méthodes de tessellations existantes utilisées dans la cartographie Web. Cette tessellation utilise un icosaèdre comme modèle géométrique de base avec une densité de partitionnement des faces de l’icosaèdre entre les niveaux de récursivité égale à 4.La méthodologie proposée consiste en quatre étapes successives: a) la construction d'une structure hiérarchique qui résulte de la subdivision récursive des faces de l'icosaèdre ; b) la définition d’un système de projection approprié à la tessellation icosaédrique; c) la projection des données géospatiales de la sphère terrestre sur chaque face de l’icosaèdre; d) le dépliage de la tessellation icosaédrique résultante sur un plan en utilisant des algorithmes de calcul du plus court chemin afin de maintenir le voisinage autour du point d’intérêt. Nous présenterons les étapes de développement et d’implémentation du système proposé et les résultats obtenus dans le cadre de ce projet de recherche. L’étude comparative avec d’autres systèmes de projection montre que notre approche minimise mieux les déformations par tout sur le globe et surtout dans les régions nordiques. / Map projection systems adapted to web mapping services still raise many research questions. The majority of web mapping services (ex. Google Maps, Bing Maps) use Web Mercator Projection (WMP) which introduces large systematic distorsionsin spatial data especially in polar rigions. Therefore, it is necessary to develop an alternative method for projecting these regions with minimal distortions. Our approach is inspired of myriahedral projections which assume that each face of a myriahedron is small enough so that the distortions are negligible. Here, in this research work we propose a new approach for the tessellation of the surface of the globe and the projectionof the spatial information from the glob to the faces of the tessellation at differentlevels of details. This compensates for the weakness of the methods used for tessellation in the existing web mapping systems. The proposed tessellation is created based on an icosahedron with a partitioning density of the faces equal to 4. The proposed methodology consists of four stages: a) constructing of a hierarchical structure resulting the recursive subdivision of the faces of the icosahedron, while maintaining topological relationships between the triangles in each level of detail; b) defining of an appropriate projection system to the icosahedral tessellation; c) projecting of geospatial data of the terrestrial sphere on each face of the icosahedron; d) unfolding the resulting icosahedral tessellation on a plane around a point of interest. Here we present different stages of development and implementation of the proposed system and the results obtained in the framework of this research project. The comparative study with other projection systems shows that our approach allows to better minimize different distortions every where on the globe and specially in the polar rigions.

Cette thèse présente une méthode de détection et de correction des intersections visuelles et singulières entre courbes B-splines adaptée à la généralisation des cartes marines. Dans une première partie, nous nous intéressons à la détection des intersections. La méthode proposée effectue d'abord un partitionnement du plan. Les courbes sont reparties dans les cellules sans calcul numérique. Le partitionnement est donc rapide et robuste. Ensuite, les intersections sont calculées à l'aide de schémas de subdivision. La deuxième partie concerne la correction des conflits par déformation respectant les contraintes cartographiques. Nous présentons une première méthode où le polygone de contrôle est assimilé à un réseau de barres déformé par l'application de forces externes. Une deuxième méthode est ensuite présentée où le déplacement est représenté par un snake soumis a des énergies définies en fonction des conflits. Les paramètres de forme sont réglés automatiquement.

La généralisation de données géographiques est l'opération de simplification de ces données effectuée lors de la diminution de leur échelle de représentation. Cette thèse s'appuie sur le modèle de généralisation automatique à base d'agents de (Ruas et Duchêne, 2007), qui a été mis en oeuvre avec succès pour la généralisation des objets géographiques discrets (bâtiments, routes, etc.). L'objectif est de permettre une prise en compte d'un nouveau type de thèmes, appelés "thèmes champ", comme le relief ou l'occupation du sol. Ces thèmes ont pour particularité d'être définis en tout point de l'espace. Nous souhaitons permettre une préservation des relations pouvant exister entre les objets géographiques et les champs, comme par exemple le fait qu'un cours d'eau s'écoule sur le relief. Pour répondre à cet objectif, nous proposons le modèle de généralisation GAEL (Généralisation à base d'Agents Elastiques) qui permet d'appliquer des déformations aux champs pour préserver les relations objet-champ. Les champs sont modélisés comme des agents, dits élastiques, qui ont la capacité de se déformer pour amortir les opérations de généralisation appliquées aux objets géographiques (bâtiments, routes, etc.). Ces déformations sont obtenues en s'appuyant sur une décomposition des champs en petits éléments contraints (points, segments, triangles, etc.) et sur une modélisation des points composant les champs sous forme d'agents. Couplé au modèle de (Ruas et Duchêne, 2007), le modèle GAEL permet de disposer d'un modèle de généralisation hybride, capable d'effectuer à la fois des opérations discrètes et continues

Les cartes représentent l'information géographique d'une zone donnée de manière d'autant plus simplifiée que l'échelle de la carte est petite. Le procédé de simplification, appelé généralisation cartographique, est soumis au respect de contraintes de lisibilité, d'adéquation de la représentation avec le niveau d'abstraction souhaité et de cohérence avec la réalité. La volonté d'automatiser le processus de création de cartes à partir de bases de données géographiques, a conduit à la création d'algorithmes permettant d'effectuer cette simplification objet par objet. Néanmoins, les choix des algorithmes, tout comme leur paramétrage, sont autant influencés par l'objet sur lequel ils s'appliquent que par les autres objets en relation (e.g. bâtiment à proximité d'un autre, route parallèle à un alignement de bâtiments). Ce constat a motivé l'utilisation de modèles multi-agents pour la généralisation automatisée de cartes. Le principe de ces modèles multi-agents repose sur la modélisation des objets (e.g. bâtiment, tronçon de route, îlot urbain) sous forme d'agents qui cherchent à se généraliser de façon à satisfaire leurs contraintes. Plusieurs modèles multi-agents ont été proposés, chacun ayant une approche différente des interactions entre niveaux. Ici, nous entendons par niveau, par exemple, la distinction entre les agents individuels comme un bâtiment, des agents représentant un groupe d’autres agents, comme un îlot urbain composé des routes l’entourant et des bâtiments inclus dans l’îlot.Nous étudions l'unification de ces modèles en nous appuyant sur le paradigme multi-niveaux PADAWAN, afin de faciliter les interactions entre agents de niveaux différents. Nous proposons ainsi le modèle DIOGEN, adaptant les principes d’interaction entre agents de niveaux différents à la généralisation cartographique guidée par des contraintes, ce qui a permis d’unifier les précédents modèles AGENT, CartACom et GAEL, tout en disposant de nouvelles capacités prometteuses.Nous avons évalué notre proposition sur un ensemble de cas d’étude. Parmi ces cas, nous nous sommes penchés sur la généralisation de carte de randonnée, où les itinéraires sont symbolisés individuellement avec des symboles différents, à la manière des plans de bus. La présence de plusieurs symboles d’itinéraires sur une même route support amène des problèmes de généralisation particuliers, comme le choix du positionnement des itinéraires de part et d’autre de la route, ou les implications pour les autres objets de la carte (e.g. points d’intérêts, bâtiments) se retrouvant sous le symbole de l’itinéraire, problèmes que nous essayons de résoudre en nous appuyant sur notre proposition de représentation formelle multi-niveaux.Ce travail nous a ensuite conduit à identifier des comportements multi-niveaux récurrents. Nous les avons exprimés de façon générique sous forme de patterns d’analyse, affranchies des spécificités de la généralisation cartographique, et de la résolution de problèmes contraints / Maps show geographic information of a given area in a simplified way, particularly when the scale is small. The simplification process, called cartographic generalisation, is submitted to several constraints : legibility, adequation to the abstraction level, and consistency with reality. The will to automate the maps creation process from geographical databases led to the creation of algorithms allowing the simplification object by object. However the choice of the algorithms, as their settings, are influenced by the object on which it is applied, and by the other objects in relation with this object (e.g. a building close to another one, a road parallel to a buildings alignment). This motivates the use of multi-agents models for automated map generalisation. Several multi-agent models were proposed, each of them having a different approach to manage multi-levels relations. Here, what we call a level is, for instance, the distinction between individual agents, like a building, and agents representing a group of other agents, like a urban block composed by the surrounding roads and buildings inside.We study the unification of existing models, using the multi-level paradigm PADAWAN, in order to simplify interactions between agents in different levels. We propose the DIOGEN model, in which the principle of interactions between agents of different levels is adapted to cartographic generalisation guided by constraints, those allowing to unify the existing models AGENT, CartACom and GAEL, and giving promising features.We evaluate our proposal on different case studies. Among them, we study the generalisation of trekking maps, where the routes are symbolized individually by a different couloured line symbols, like on bus maps. The presence of several route symbols on a same road leads to specific generalisation issues, like the choice of the side of each route symbol position, or the implications for the other objects on the map (e.g. points of interest, buildings) under the route symbol – issues tackled using our proposal of formal multi-levels representation.This work leads us to the identification of recurrent behaviours. We express them as analysis patterns, in a way that is independent from cartographic generalisation and constraint solving problems

Cette thèse traite de l'automatisation de la généralisation cartographique qui est le procédé de simplification d'une base de données géographique vectorielle pour sa représentation sur une carte lisible. La recherche dans le domaine a abouti aujourd'hui au développement de nombreux processus automatiques de généralisation cartographique, chacun étant spécialisé pour un problème particulier comme un type de paysage, un thème de donnée, un type de conflit ou un mélange des trois (proximité entre bâtiments en zone urbaine). L'objectif de cette thèse est de tirer parti de cette diversité pour mettre en place la généralisation complète d'une carte en faisant collaborer des processus de généralisation complémentaires. Pour répondre à cet objectif, nous proposons le modèle CollaGen (Collaborative Generalisation) qui permet, par un système multi-agent, la collaboration des processus : les données sont découpées de manière pertinente par rapport aux processus à disposition en espaces géographiques (une zone urbaine ou le réseau routier par exemple) ; la généralisation d'un espace par un processus est ensuite orchestrée par CollaGen. CollaGen associe de manière itérative un espace à généraliser et un processus adapté, notamment par un mécanisme de registre type pages jaunes. L'interopérabilité entre les processus est assurée par une ontologie du domaine sur laquelle s'appuie un format de spécifications formelles d'une carte généralisée. Chaque généralisation est évaluée globalement en temps réel pour permettre un retour en arrière en cas de problème. Enfin, du fait du principe de découpage en espaces, CollaGen doit vérifier après chaque généralisation si des effets de bord sont apparus avec les objets géographiques situés juste à l'extérieur de l'espace, auquel cas il les corrige au mieux. Dans, cette thèse, le modèle CollaGen est mis en œuvre pour la généralisation de cartes topographiques (notamment au 1 : 50000) et les résultats sont comparés à d'autres approches et discutés / This phd thesis deals with cartographic generalisation, the process that simplifies a geographic database to allow its representation on legible map. Past research lead to the development of many automatic generalisation processes, each one being specialised for a specific problem like a particular landscape, a given data theme, a particular graphic conflict or a mix of the three (like ‘proximity between buildings in urban areas). The aim of the thesis is to benefit from this diversity to carry out a complete map generalisation by collaboration between complementary processes. To meet this objective, the CollaGen model is proposed (Collaborative Generalisation) as it allows, based on multi-agent techniques, generalisation processes collaboration : data is relevantly partitioned into geographic spaces (e.g. an urban area or the road network) ; then CollaGen orchestrate the generalisation of a space by an adapted process. CollaGen iterately maps a space to be generalised and an adapted process thanks to a yellow pages registry mecanism. The interoperability between processes is managed by a domain ontology on which formal map specifications are based. Each generalization is globally assessed online to allow backtracks if necessary. Finally, because of the space partitioning, CollaGen has to check after each generalisation if side effects appeared with spaces just outside the one that has been generalised. If some side effects occurred, they are corrected. In this thesis, CollaGen is implemented for topographic map generalisation (to 1 : 50000) and results obtained are compared to other approaches and discussed

Dans cette thèse nous étudions une nouvelle approche de visualisation cartographique appelée « îles de mémoires ». Le terme « îles de mémoires » a été inspiré par la méthode des «loci» (pluriel de « locus » en latin qui signifie « endroit » ou « lieu») de l’ancien « Art de la mémoire». Une carte bien représentée dans l’esprit peut donner un sens à la connaissance, ce qui améliore une de recherche d'information (une recherche intuitive), et contribue à enrichir les connaissances issues de cette carte. Pour cela, la technique « îles de mémoires » consiste à associer chaque entité de connaissance à un endroit désigné sur une île virtuelle. Grâce aux les métaphores géographiques que nous avons définies, une représentation en « îles de mémoires » peut inférer des phénomènes souvent difficile à identifier et comprendre dans la connaissance. Dans une première partie, nous détaillons notre approche de visualisation d’une hiérarchie de connaissances en île de mémoire. Nous présentons les algorithmes que nous avons définis pour générer automatiquement une belle carte réaliste, fonctionnelle, intuitive et inspirante. Nous présentons aussi l’interface de visualisation "overview+detail" qui permet de naviguer dans les îles de mémoire. Dans une deuxième partie, nous détaillons les expérimentations réalisées avec notre outil dans le cadre du projet LOCUPLETO et des exemples issus du domaine des humanités numériques (Projet OBVIL, InPhO, etc.). Les résultats obtenus avec notre approche de visualisation sont prometteuses. En effet, les résultats démontrent que la navigation est intuitive et est capable d’augmenter la mémorisation des connaissances chez les utilisateurs de l’outil. Nous concluions notre thèse par le bilan des travaux menées et nous proposons un ensemble de travaux futurs basé sur notre approche de visualisation « îles de mémoires ». / This thesis is devoted to the study of an original cartographic visualization approach named Memory Island. We discuss how hierarchical knowledge can be meaningfully mapped and visualized as an insightful island. Our technique is inspired by the "loci" (plural of Latin "locus" for places or locations) method of the ancient "Art of Memory" technique. A well-designed map in mind can make sense of knowledge, which leads to the accomplishment of one's information seeking tasks, and helps to extend one's knowledge. To this end, Memory Island technique consists of associating each entity of knowledge to a designated area on a created virtual island. With the geographic visual metaphors we define, Memory Island can present phenomena found in knowledge, which is often difficult to understand. In this thesis, we discuss how we design our visualization technique to make it achieve the great features of visualization: automatically generate a truthful, functional, beautiful, insightful, and enlightening island with its technical details. In order to make Memory Island more convenient for its users, we present our "overview+detail" interface, to support them with visual exploration and knowledge analysis. We also demonstrate how to create knowledge maps using Memory Island technique, by giving some example on different datasets of Digital Humanities (Project OBVIL), e-books (Project LOCUPLETO) and other domains. Then, we propose our validation and evaluation protocols with two preliminary user experiments. The results from these studies indicate that the use of Memory Island provides advantages for non-experienced users tackling realistic browsing, helps them improve their performances in knowledge navigation and memorization tasks, and that most of them choose to use it for navigation and knowledge discovery. We end up by concluding our researches and listing some perspectives and future works that can be based on our Memory Island technique.

L’analyse des systèmes naturels globaux est divisée selon les organismes régionaux, nationaux et internationaux. Leurs travaux sont encadrés par une gestion scientifique et juridique notamment par des directives tel que la DCE ou INSPIRE, basée sur la communication. La comparaison des données d’origines différentes et sans prise en compte des frontières n’est possible qu’à l’aide d’une harmonisation fondée sur les normes internationales. La carte est à ce titre un outil de transmission de l’information organisée à partir des bases de données.Cette thèse propose une analyse sémiologique de la représentation cartographique qui traite de la thématique de la gestion de l’eau dans un cadre européen. Il s’agit de comprendre et d’interpréter la mise en oeuvre des processus de communication basés sur les cartes ; la Hongrie et la France sont prises comme exemple.L’harmonisation est nécessaire mais en même temps très difficile à mettre en place au sein d’un monde où les disparités sont très grandes. Les compromis nécessaires à l'harmonisation et à l'uniformisation du langage cartographique impliquent des concessions de la part des acteurs mais aussi des producteurs de cartes.L’importance des innovations dans la visualisation cartographique aboutissant à une meilleure communication n’est pas encore reconnue à l’heure actuelle. Le public, quel qu’il soit, est souvent habitué à une représentation traditionnelle ; pourtant les effets que l’on peut ajouter à une carte, fruits de l’innovation technologique, ouvrent de nouveaux horizons pour la cartographie et peuvent servir de nouvelles bases au raisonnement dans la prise de décisions. / Water, which is one of our most important natural resources, stops at neither political nor artificial boundaries. This is why it is necessary to treat it globally instead of the present situation, where water is managed nationally and regionally. A possible solution for this is an international unified water management system, and effective information is a key requirement for this to happen. Maps contain visual information which is independent of language, and map visualization is an important tool of communication. Therefore I have been comparing two European Union countries (France and Hungary) to understand the processes of map communication in relation to EU regulations. The first objective of my research has been the examination of how far the harmonization of map communication has been achieved in the European directives, particularly concerning water-related directives. Secondly, to the extent that harmonization has not occurred, I have investigated into the reasons why this has happened and whether there are any solutions to this issue. Effectiveness of map-based communication is closely related to uniform data systematization. This is why I have endeavored to discover and develop a harmonizationhelping system for visualization. Finally, I have examined whether, in this legally-regulated research environment, there is the possibility of innovative rather than traditional map representations. As results I gave an overview of the European directives and projects, and I examined the relations between them. At the same time I determined the role of the cartographer concerning the directives. I created an examining system based on the rules of the French and Hungarian thematic cartography. I made certain that the directives are necessary but not sufficient conditions of harmonized map communication. The necessary condition of this is a uniform and harmonized system of thematic data. I verified that the maps created by existing processes do not meet the claims of the three different user circles aimed at by the WFD. I created my own communicative model for maps associated with water after studying Robinson-Petchenik-and Kolácný’s communicative models. I took into consideration every element of map-forming, which may have an influence on the decision made based on the map. I developed innovative prototypes for certain types of WFD maps to the general public and decision-makers. / Elsisorban szeretnék köszönetet mondani témavezetiimnek Philippe Quodverte-nek és José Jesús Reyes Nunez-nek, akik a doktori kezdetétil tanácsaikkal folyamatosan segítettek. Philippe Quodverte-nek külön szeretném megköszönni, hogy Erasmusos orléans-i tartózkodásom után három évvel újbóli támogatásáról biztosított és elvállalta a doktori témám vezetését, illetve azt a türelmet, amivel segített a francia doktori kutatásra vonatkozó eliírások és térképészeti hagyományok elsajátításában. Nagyon élveztem a vele való beszélgetéseket és térképészeti eszmecseréinket. Emellett köszönettel tartozom Zentai Lászlónak és Verebiné Fehér Katalinnak a nekem nyújtott segítségükért és hasznos tanácsaikért, illetve az ELTE Térképtudományi és Geoinformatikai Tanszék minden munkatársának volt tanáraimnak, akik támogatásával jutothattam el a doktoriig. Továbbá köszönöm Guillame Giroir-nak, a Földrajzi Doktori Iskola (CEDETE) vezetijének, hogy befogadott csapatába, és részese lehetek a CEDETE életének. Köszönet az Orléans-i Egyetemen kollégáimnak Anabelle Mas-nak, Stéphane Grivel-nek, Frank Guéritnek és Bertrand Sajaloli-nak, akik tanácsaikkal támogattak és segítették munkámat. Külön köszönet Matthieu Lee-nek, a CEDETE térképészének, aki észrevételeivel segítette a doktoriban bemutatott térképek elkészítését. Külön szeretném megköszönni mindazoknak, akik magyar és francia részril segítettek a Víz Keretirányelv és az INSPIRE végrehajtásának megismerésében, illetve az adatok elérésében, azaz név szerint François Robida (BRGM), Janik Michon (ONEMA), Jelinek Gabriella (Vidékfejlesztési Minisztérium), Tahy Ágnes (VKKI). Köszönettel tartozom Vikor Zsuzsának a dolgozat nyelvhelyességének ellenirzéséért. Köszönöm emellett családomnak, szüleimnek, nagyszüleimnek és testvéremnek, hogy bátorítottak és mellettem álltak. Nem utolsó sorban szeretném megköszönni doktorandusz társaimnak, Anh Tu-nak, Cristina-nak, Sylvain-nak, Eszternek, és barátaimnak, Virgine-nek Anabella-nak, Alexandranak, Chloë-nak és Dávidnak, hogy a nehéz pillanatokban segítettek és jó tanácsokkal láttak el. Külön köszönet Virginie Anne-nak a francia összefoglaló nyelvhelyességének ellenirzéséért és baráti támogatásáért.