Minimum Cost Polygon Overlay (MCPO) is a unique two-dimensional optimization problem that involves the task of covering a polygon shaped area with a series of rectangular shaped panels. The challenges in solving MCPO problems are related to the interdependencies that exist among the parameters and constraints that may be applied to the solution.This thesis examines the MCPO problem to construct a model that captures essential parameters to be solved using optimization algorithms. The purpose of the model is to make it possible that a solution for an MCPO problem can be generated automatically. A software application has been developed to provide a framework for validating the model.The development of the software has uncovered a host of geometric operations that are required to enable optimization to take place. Many of these operations are non-trivial, demanding novel, well-constructed algorithms based on careful appreciation of the nature of the problem.For the actual optimization task, three algorithms have been implemented: a greedy search, a Monte Carlo method, and a Genetic Algorithm. The behavior of the completed software is observed through its application on a series of test data. The results are presented to show the effectiveness of the software under various settings. This is followed by critical analysis of various findings of the research.Conclusions are drawn to summarize lessons learned from the research. Important issues about which no satisfactory explanation exists are given as material to be studied by future research.

Minimum Cost Polygon Overlay (MCPO) is a unique two-dimensional optimization problem that involves the task of covering a polygon shaped area with a series of rectangular shaped panels. The challenges in solving MCPO problems are related to the interdependencies that exist among the parameters and constraints that may be applied to the solution.This thesis examines the MCPO problem to construct a model that captures essential parameters to be solved using optimization algorithms. The purpose of the model is to make it possible that a solution for an MCPO problem can be generated automatically. A software application has been developed to provide a framework for validating the model.The development of the software has uncovered a host of geometric operations that are required to enable optimization to take place. Many of these operations are non-trivial, demanding novel, well-constructed algorithms based on careful appreciation of the nature of the problem.For the actual optimization task, three algorithms have been implemented: a greedy search, a Monte Carlo method, and a Genetic Algorithm. The behavior of the completed software is observed through its application on a series of test data. The results are presented to show the effectiveness of the software under various settings. This is followed by critical analysis of various findings of the research.Conclusions are drawn to summarize lessons learned from the research. Important issues about which no satisfactory explanation exists are given as material to be studied by future research.

Les systèmes d’information géographique (SIG) sont largement utilisés pour représenter, gérer et analyser les données spatiales dans plusieurs disciplines incluant les géosciences, l’agriculture, la foresterie, la météorologie et l’océanographie. Néanmoins, malgré l’avancement récent des technologies des SIG, ils sont encore limités dans la représentation et la simulation des processus spatiotemporels. Ce travail de recherche définit le cadre théorique, conceptuel et applicatif qui vise à améliorer les méthodes de compréhension, de représentation et de simulation des processus dynamiques continus. Il vise plus précisément à améliorer les structures de données dans les SIG en développant une structure de données hiérarchique qui est la base d’un automate cellulaire capable de répondre aux principales caractéristiques de ces processus. L’exploration du potentiel des automates cellulaires pour simuler et représenter les processus dynamiques continus dans les SIG en respectant leur caractère irrégulier et hiérarchique fait l’objet de ce travail de recherche dans lequel une application dans le contexte hydrologique est mise en place. Nos objectifs spécifiques se résument dans 1) la construction d’une tessellation irrégulière et hiérarchique permettant de représenter les processus spatiotemporels et 2) la simulation de ces processus en utilisant un automate cellulaire opérant sur cette tessellation. Nous étudions la discrétisation de l’espace en tessellation irrégulière basée sur le diagramme de Voronoï et nous proposons une procédure de hiérarchisation de cette tessellation dans un objectif de représentation multi-échelle afin d’offrir une solution d’aide à la décision dans la gestion du territoire. Nous expliquons notre méthodologie et les algorithmes de sélection de données pour la génération de différents niveaux d’échelles spatiales. Un automate cellulaire non traditionnel est mis en place pour lequel nous définissons une grille à géométrie irrégulière de type Voronoï, des règles de transition spécifiques et un type particulier de voisinage orienté. Nous validons le fonctionnement de ce prototype dans le Bassin Expérimental de la Forêt Montmorency à Québec où des comparaisons sont possibles grâce à des données de débits d’eau mesurées in situ. / Geographic information systems (GIS) are widely used to represent, manage and analyse spatial data in many disciplines including geosciences, agriculture, forestry, meteorology and oceanography. However, despite recent advances in GIS technologies, they are still limited when it comes to representation and simulation of spatiotemporal processes. This research work, deals with a theoretical, conceptual and practical framework which aims to improve the representation of dynamic continuous processes. It aims especially to improve GIS capabilities by developing a CA based on a hierarchical irregular tessellation which is able to take into account the main characteristics of these processes. The exploration of the cellular automata potential to simulate and represent dynamic continuous processes regarding their irregular and hierarchic characteristics is the subject of this work where an application in the hydrologic field is established. Our specific objectives are 1) to build an irregular and hierarchic grid that can be used to represent spatiotemporal processes, 2) to simulate those processes with a cellular automata operating on this grid. We give details about the irregular geometric grid based on a Voronoï Diagram, the characteristics of a specific oriented neighbourhood and the transition rules that are governing the cells update. In addition, we discuss the hierarchical perspective of the build lattice that is essential for easy move between different spatial scales. We explain our methodology of data selection in order to generate the spatial levels of representation by demonstrating the used selection algorithms. This facilitates the representation of spatial dynamic phenomena and contributes to the better understanding of the complex behaviour of the whole system at different levels of details. We also present the data structures and general functioning of the whole simulation system. We finally, validate our framework by simulating the water flow process in a specific watershed in the region of Montmorency Forest of Quebec where in situ data are available. To validate our simulation results we compare them with measured data.

Cette thèse propose de développer des mécanismes déployables pour applications spatiales ainsi que des modes d’actionnement permettant leur déploiement et le contrôle de l’orientation en orbite de l’engin spatial les supportant. L’objectif étant de permettre le déploiement de surfaces larges pour des panneaux solaires, coupoles de télécommunication ou sections de station spatiale, une géométrie plane simple en triangle est retenue afin de pouvoir être assemblée en différents types de surfaces. Les configurations à membrures rigides proposées dans la littérature pour le déploiement de solides symétriques sont optimisées et adaptées à l’expansion d’une géométrie ouverte, telle une coupole. L’optimisation permet d’atteindre un ratio d’expansion plan pour une seule unité de plus de 5, mais présente des instabilités lors de l’actionnement d’un prototype. Le principe de transmission du mouvement d’un étage à l’autre du mécanisme est revu afin de diminuer la sensibilité des performances du mécanisme à la géométrie de ses membrures internes. Le nouveau modèle, basé sur des courroies crantées, permet d’atteindre des ratios d’expansion plans supérieurs à 20 dans certaines configurations. L’effet des principaux facteurs géométriques de conception est étudié afin d’obtenir une relation simple d’optimisation du mécanisme plan pour adapter ce dernier à différents contextes d’applications. La géométrie identique des faces triangulaires de chaque surface déployée permet aussi l’empilement de ces faces pour augmenter la compacité du mécanisme. Une articulation spécialisée est conçue afin de permettre le dépliage des faces puis leur déploiement successivement. Le déploiement de grandes surfaces ne se fait pas sans influencer lourdement l’orientation et potentiellement la trajectoire de l’engin spatial, aussi, différentes stratégies de contrôle de l’orientation novatrices sont proposées. Afin de tirer profit d’une grande surface, l’actionnement par masses ponctuelles en périphérie du mécanisme est présentée, ses équations dynamiques sont dérivées et simulées pour en observer les performances. Celles-ci démontrent le potentiel de cette stratégie de réorientation, sans obstruction de l’espace central du satellite de base, mais les performances restent en deçà de l’effet d’une roue d’inertie de masse équivalente. Une stratégie d’actionnement redondant par roue d’inertie est alors présentée pour différents niveaux de complexité de mécanismes dont toutes les articulations sont passives, c’est-à-dire non actionnées. Un mécanisme à quatre barres plan est simulé en boucle fermée avec un contrôleur simple pour valider le contrôle d’un mécanisme ciseau commun. Ces résultats sont étendus à la dérivation des équations dynamiques d’un mécanisme sphérique à quatre barres, qui démontre le potentiel de l’actionnement par roue d’inertie pour le contrôle de la configuration et de l’orientation spatiale d’un tel mécanisme. Un prototype à deux corps ayant chacun une roue d’inertie et une seule articulation passive les reliant est réalisé et contrôlé grâce à un suivi par caméra des modules. Le banc d’essai est détaillé, ainsi que les défis que l’élimination des forces externes ont représenté dans sa conception. Les résultats montrent que le système est contrôlable en orientation et en configuration. La thèse se termine par une étude de cas pour l’application des principaux systèmes développés dans cette recherche. La collecte de débris orbitaux de petite et moyenne taille est présentée comme un problème n’ayant pas encore eu de solution adéquate et posant un réel danger aux missions spatiales à venir. L’unité déployable triangulaire entraînée par courroies est dupliquée de manière à former une coupole de plusieurs centaines de mètres de diamètre et est proposée comme solution pour capturer et ralentir ces catégories de débris. Les paramètres d’une mission à cette fin sont détaillés, ainsi que le potentiel de réorientation que les roues d’inertie permettent en plus du contrôle de son déploiement. Près de 2000 débris pourraient être retirés en moins d’un an en orbite basse à 819 km d’altitude. / This thesis presents the design of deployable mechanisms for space applications and means of actuation for the control of their deployment and the attitude control of their satellite base. For this purpose, the triangular geometry is selected as a planar deployable basic unit to tessellate any surface. Each such module needs to achieve a high expansion ratio. From the literature, planar mechanisms based only on rigid links and developed for deployable Platonic solids are optimized and adapted for open geometries such as a cupola. The resulting expansion ratio is above 5, but the corresponding prototype shows instability of the deployment movement close to the retracted position. The paradigm of power transmission is revised to reduce the sensitivity of the mechanism to its internal transmission angles. The novel solution, based on timing belts, can achieve expansion ratios above 20 in particular configurations. The influence of the principal geometric parameters of design on the expansion ratio is discussed to allow the derivation of a simple optimization relation. The optimization can be performed to adapt this mechanism to different contexts of application. In order to further improve the compactness of the mechanism for transport purposes, a novel joint is presented, allowing two successive phases of rotation on non parallel axes. This way the triangular units can be piled before being deployed. The deployment of a large surface in orbit is prone to impact the spacecraft attitude and maybe its course. Hence, control strategies are proposed to manage these effects. Since the deployment targets a large surface, its edges are far from the centre of mass and are advantageous to induce torque from the linear motion of point masses. The dynamic equations are derived based on the conservation of the angular momentum and the resulting matrix form of the equation set is used to simulate the system and assess its performances. The results validate the strategy for orientation control without obstruction of the spacecraft central space, but a flywheel of equivalent mass still outperforms this design. Redundant actuation by flywheel on each link of a multibody mechanism composed only of passive revolute joints is presented. The dynamic equations are derived for a two-body architecture and a four-bar planar mechanism. The closed-loop control of the four-bar mechanism is using a PD controller to achieve the control of a scissor mechanism unit. The results are then extended to a four-bar spherical mechanism and its simulation demonstrates the potential of this strategy for the control of both the configuration and the orientation of a spatial mechanism. A two-body prototype, linked by a passive revolute joint, is manufactured and controlled with visual tracking feedback. The results confirm that the system is controllable in orientation and configuration. This thesis ends with a case study for the application of the main components developed in this research. The capture of small to medium sized orbital debris is introduced. The triangular deployable unit based on timing belts is replicated in order to create a cupola of hundreds of metres to catch and slow down the debris. The parameters of such a mission are detailed as well as the flywheel potential to control the spacecraft attitude on top of the mechanism deployment. It is estimated that almost 2000 pieces of debris can be removed from the orbit at 819 km altitude in a one year mission.