Polígono de visibilidad desde un lado

González Díaz-Carralero, Alberto Isidro (2009). Polígono de visibilidad desde un lado. Proyecto Fin de Carrera / Trabajo Fin de Grado, Facultad de Informática (UPM) [antigua denominación].

Descripción

Título: Polígono de visibilidad desde un lado
Autor/es:
  • González Díaz-Carralero, Alberto Isidro
Director/es:
  • Hernández Peñalver, Gregorio
Tipo de Documento: Proyecto Fin de Carrera/Grado
Fecha: 7 Julio 2009
Materias:
Palabras Clave Informales: Geometría Computacional, Visibilidad, Cola Concatenable, Polígono en Forma Estándar, Polígono de Visibilidad desde un Punto, Polígono de Visibilidad desde un Lado
Escuela: Facultad de Informática (UPM) [antigua denominación]
Departamento: Matemática Aplicada
Licencias Creative Commons: Reconocimiento - No comercial - Compartir igual

Texto completo

[img]
Vista Previa
PDF (Document Portable Format) - Se necesita un visor de ficheros PDF, como GSview, Xpdf o Adobe Acrobat Reader
Descargar (791kB) | Vista Previa

Resumen

El algoritmo central que se trata en este trabajo es el presentado por Lee y Lin (1986) para calcular V(a,b). En el trabajo desarrollamos una implementación de dicho algoritmo de complejidad O(n log n). Para ello nos apoyamos en una estructura de datos llamada (Aho, Hopcroft y Ullman 1974) cola concatenable, para la cual desarrollamos una implementación particular que hemos llamado árbol-pila binario. Desarrollamos una segunda implementación para la cola concatenable con una lista para poder mostrar los estados intermedios del algoritmo y poder analizarlo paso a paso. Esta segunda implementación al realizar búsquedas secuenciales en lugar de binarias eleva la complejidad del algoritmo total a O(n2). Presentamos un algoritmo para calcular el polígono de visibilidad desde un vértice, basado en el algoritmo de Lee y Lin para un lado. Este algoritmo tiene complejidad lineal. Implementamos igualmente este algoritmo basándonos en la implementación anterior para un lado. Por último hemos desarrollado un algoritmo para pasar un polígono a forma estándar.

Más información

ID de Registro: 1736
Identificador DC: http://oa.upm.es/1736/
Identificador OAI: oai:oa.upm.es:1736
Depositado por: Sr. Alberto Isidro González Díaz-Carralero
Depositado el: 09 Jul 2009
Ultima Modificación: 20 Abr 2016 06:58
  • Open Access
  • Open Access
  • Sherpa-Romeo
    Compruebe si la revista anglosajona en la que ha publicado un artículo permite también su publicación en abierto.
  • Dulcinea
    Compruebe si la revista española en la que ha publicado un artículo permite también su publicación en abierto.
  • Recolecta
  • e-ciencia
  • Observatorio I+D+i UPM
  • OpenCourseWare UPM