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

  1. Martínez del Río, Francisco
Dirigida per:
  1. Antonio Jesús Rueda Ruiz Director/a
  2. Francisco Feito Higueruela Director

Universitat de defensa: Universidad de Jaén

Fecha de defensa: 12 de de març de 2010

Tribunal:
  1. Robert Joan Arinyo President/a
  2. Lidia M. Ortega Alvarado Secretària
  3. Antoni Susín Sánchez Vocal
  4. Juan Carlos Torres Cantero Vocal
  5. Pedro Cano Olivares Vocal
Departament:
  1. INFORMÁTICA

Tipus: Tesi

Teseo: 307645 DIALNET

Resum

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.