Técnicas Gráficas y de Modelización Geométrica 


Curso 09/10


 
  • Profesores 
Ana Belén Cabello
anabelen.cabello@urjc.es

Despacho 024 (Departamental II) 
Tutorías: Previa petición.
 
  • Introducción
En distintas situaciones el hombre ha intentado representar la realidad desde un punto de vista artístico (pintura, escultura...), matemático (representación de curvas y superficies, ecuaciones implícitas o paramétricas...) o industrial (curvas que representan piezas de aviones, barcos..). El ordenador es un potente instrumento para que esta representación se pueda efectuar (capacidades computacionales) o representar (capacidades gráficas).

En este contexto la matemática y la informática trabajan juntas para conseguir buenas representaciones de curvas, adecuados modelos en tres dimensiones, algoritmos rápidos y que ocupen poca memoria para resolver modelos geométricos.

La asignatura que presentamos tiene dos partes bien diferenciadas. 

En la primera abordaremos problemas geométricos de naturaleza discreta, centrándonos en tres de ellos. Envolventes convexas, diagramas de Voronoi y Triangulaciones de Delaunay. Son problemas de naturaleza geométrica con aplicaciones prácticas.  Los estudiaremos matemáticamente y daremos algoritmos que los resuelven, estudiando la complejidad de dichos algoritmos y de los propios problemas. 

En la segunda abordaremos el problema de la construcción de curvas que tienen algunos datos predeterminados (pasan por unos puntos, son lisas, son derivables...) definiendo los conceptos con precisión y dando algoritmos para realizarlas.
 
 

  • Objetivos 
Comprender los conceptos de modelo computacional, complejidad de algoritmos y problemas.
Conocer las nociones geométricas involucradas en los distintos problemas: convexidad, distancias, particiones, triangulaciones.
Comprender los algoritmos que se presentan y saber aplicarlos.
Desarrollar capacidades geométricas y computacionales para diseñar algoritmos que afronten situaciones diferentes.
Conocer el algoritmo de De Casteljau y saber utilizarlo para dibujar una curva de Bezier a partir de un conjunto de puntos de control.
Conocer y utilizar las propiedades geométricas de las curvas de Bezier.
Construir una curvas de Bezier a trozos.
 
  • Programa 
I. Geometría computacional

Tema 1. Preliminares. Modelos de computación. Algoritmos. Complejidad de algoritmos y complejidad inherente a un problema. El plano afín. Transformaciones baricéntricas.

Tema 2. Envolventes convexas.  Definiciones y enunciado del problema. Aplicaciones. Algoritmos de construcción de envolventes convexas en 2D y sus complejidades.

Tema 3.  Diagramas de Voronoi. Definiciones y enunciado del problema. Aplicaciones. Grafos planos. Algoritmo basado en la caracterización de vértices y aristas. Algoritmo de Fortune.

Tema 4. Triangulaciones.  Triangulaciones de polígonos. Triangulaciones de nubes de puntos: triangulación de Delaunay. Aplicaciones.

II. Herramientas para el diseño asistido por ordenador

Tema 5. Interpolación polinómica.  Parametrización de curvas. Interpolación de Lagrange. Algoritmo de Aitken. Interpolación de Hermite.

Tema 6. Curvas de Bezier. El algoritmo de Casteljau. Algunas propiedades de las curvas de Bezier. “The Blossom”. Polinomios de Bernstein. Derivadas de curvas de Bezier. Elevación y disminución de grado.

Tema 7. Curvas de Bezier a trozos. Interpolación polinomial a trozos. Curvas C1 y C2.
 

  • Bibliografía básica 
  1. Computational geometry.  M. De Berg, M. Van Kreveld, M. Overmars, O. Scwarzkopf. Springer 1997.
  2. Computational geometry. An introduction. F. P. Preparata, M. I. Shamos. Texts and Monographs in Computer Science. Springer 1985.
  3. Computational geometry in C. J. O’Rourke. Cambridge University Press 1994.
  4. Curves and surfaces for CAGD. G. Farin. Academic Press 1993.
  5. Mathematical methods for CAD. J.J. Risler. Cambridge University Press 1992.
  6. Curvas y superficies para Modelado Geométrico. J. M. Cordero y J. Cortés. Ra-Ma. 2002.
  • Normas de evaluación 
Habrá un sistema de evaluación continua con los siguientes porcentajes:
 
    Examen final 50% (nota mínima: 3.5)
    Nota de clase: 50%


La nota de clase se establecerá mediante la entrega de las hojas de problemas, de las prácticas propuestas y de otros trabajos que se determinarán en clase. Se podrá trabajar en grupo (máximo tres personas).

Quienes no deseen seguir el sistema de evaluación continua, realizarán únicamente el examen final.

     

  • Prácticas

Las prácticas serán los viernes en el Aula 109 Laboratorio III

Habrá prácticas de distintos tipos:

  • resolución de problemas de matemáticas con maple,
  • uso de programas accesibles en la red,
  • implementación de algunos de los algoritmos descritos.
Prácticas de repaso:

Para aprender la sintáxis de Maple (práctica primera de la asignatura de Bases de Matemáticas).
Para iniciarse en la programación en Maple (práctica primera de la asignatura de matemática discreta).
Posición relativa de una recta y un punto (problema inicial, de comienzo de la asignatura).
Algoritmos de búsqueda (para el repaso, ejemplos de algoritmos y de cómo se estudia su complejidad).
Algoritmos de ordenación (para el repaso, ejemplos de algoritmos).

Prácticas del curso:

Práctica 1. Repaso de geometría afín.
Práctica 2 . Envolventes convexas.
Práctica 3. Envolventes convexas y diagramas de Voronoi con programas disponibles en la red.
Práctica 4. Triangulaciones.
Práctica 5. Algunas ideas sobre curvas.
Práctica 6. Interpolación.
Práctica 7. Curvas de Bezier.
Práctica 8. Curvas de Bezier a trozos.

  • Anuncios
En esta sección se irán publicando diversos anuncios de interés para los alumnos y el desarrollo de la asignatura. Se recomienda leer de vez en cuando su contenido, sobre todo en el caso de no acudir a clase.

Entrega de la práctica 1: viernes 19 de febrero

Entrega de la práctica 2: viernes 5 de marzo (ampliado al 12 de marzo)

Entrega de la hoja 5: viernes 12 de marzo

Entrega de la práctica 3: viernes 26 de marzo

Entrega de la práctica 4: viernes 9 de abril

  • Clase 
  • Enlaces de interés

    •  
     En clase hemos usado el applet denominado VoroGlide para computar diagramas de Voronoi, triangulaciones y envolventes convexas.

    La página web del profesor Manuel Abellanas contiene distintos archivos de interés, entre ellos, en la parte dedicada a trabajos de fin de carrera un applet del algoritmo de Fortune para el cómputo de Diagramas de Voronoi. También contienen muchos enlaces reseñables y un artículo introductorio muy sugerente.
     

    También queremos destacar la página web del profesor G. Touissant, donde encontramos un muy interesante artículo introductorio sobre geometría computacional.