Optimización de algoritmos basados en capas de simplices mediante descomposiciones espaciales

Abstract

El objetivo de la Tesis consiste en la mejora de la representación L-REP basada en las cadenas simpliciales subordinadas. Por un lado se presentan nuevos algoritmos para el cálculo de las relaciones de subordinación entre símplices 2D y también se introducen nuevos métodos, basados en un barrido del plano, que optimizan la construcción de las capas de símplices. La idea que explota la Tesis es la de utilizar la indexación espacial para poder optimizar el acceso y que ayuda a organizar las capas de símplices. Esta nueva indexación es denominada descomposición multi L-REP. Se intenta demostrar la mejora que supone el añadir esta nueva estructura sobre la L-REP. En particular se estudian las tres opciones para la partición del plano, en el caso 2D, según se tome una partición regular o recursiva del plano o bien se opte por una descomposición basada en un barrido rotacional. En la Tesis se explican los tres métodos y se comentan de forma comparativa las ventajas en cada caso. Cómo aplicaciones principales se presentan el test de inclusión en un polígono y las operaciones booleanas entre polígonos. Como conclusión se demuestra que el método de la multi L-REP mejora sustancialmente los resultados, especialmente cuando se trata de polígonos con muchas aristas.