Master thesis : Symbolic representation of polygons in discrete spaces

Abstract

This master's thesis describes a new data structure called Discrete Polyhedron Decision Diagram (DPDD), suited for representing symbolically meshed polygons, i.e., the intersection between a discrete mesh and a convex polygon. We develop algorithms for manipulating the data structure such as performing the intersection of a meshed polygon with a set of constraints, or adding points to the structure. Each algorithm is thoroughly explained and presented in pseudo-code. Some examples are also given to illustrate important properties and operations. This master's thesis provides as well a prototype of the data structure in which all the main operations have been implemented.

The data structure is based on the double description method and automata-based representations. DPDD then explicitly stores the face lattice of the polygon while each of its faces also contain meshes. An advantage of this is that we can retrieve the canonical form of any meshed polygon thanks to a rounding process. This leads us to have more efficient operations over the data structure. We are able to easily and efficiently check whether two meshed polygons are equal, as example, and as we have the submesh of each face, we can avoid redundant computations.