I. CURVAS POLINOMIALES
Combinaciones baricéntricas. Noción de combinación baricéntrica. Representación geométrica. Envolvente convexa. Interpolación lineal. Razón simple de tres puntos alineados. Interpolación lineal geométrica. Disminución de la oscilación.
Aplicaciones afines. Conservación de las combinaciones baricéntricas. Expresión matricial de las aplicaciones afines. Ejemplos. Conservación de ángulos y distancias.
Polinomios. Representación de polinomios mediante aplicaciones multiafines simétricas: desarrollos de Berstein. Curvas polinomiales a pedazos: nudos y diferenciabilidad. Grados de libertad.
Interpolación. Interpolación polinomial. Solución de Vandermonde. Algoritmo de Aitken. Ventajas de la interpolación polinomial a pedazos.
II. CURVAS DE BÉZIER
Algoritmo de De Casteljau. Algoritmo de interpolación: puntos y polígono de control, triángulo de interpolación. Blossom y desarrollo de Berstein. Subdivisión. Ejemplos cuadrático y cúbico.
Propiedades básicas. Invarianza afín. Interpolación de extremos, permanencia en la envoltura convexa, inversión del sentido, precisión lineal.
Diferenciabilidad. Derivadas en función de los puntos de control. Tangentes en los extremos. Derivadas en función del triángulo de interpolación. Tangentes en un punto intermedio. Aplicación a la determinación geométrica de una curva de Bézier cuadrática y su subdivisión.
Variaciones de grado. Elevación del grado de una curva de Bézier. Elevación repetida del grado. Métodos de disminución del grado.
III. SPLINES
Forma de Bézier de un spline. Polígono de control de un spline. Condiciones de diferenciabilidad del spline. Agregación de curvas de Bézier.
Splines cuadráticos y cúbicos. Polígonos de De Boor para grados 2 y 3. Interpolación mediantes splines cúbicos. Teorema de Halladay de minimización de la energía
Algoritmo de De Boor. Sucesión de nudos con multiplicidad, abscisas de Greville y ordenadas de De Boor. Algoritmo de inserción de nudos y función de De Boor. Cálculo de la función de De Boor.
Splines según De Boor. Simetría del algoritmo de inserción de nudos y diferenciabilidad de la función de De Boor. Forma de De Boor de un spline.
IV. COMPLEMENTOS
Secciones cónicas. Proyecciones y conservación de la razón doble. Transformaciones de Moebius. Representación racional de una cónica: polícono de control y pesos. Interpretación geométrica. Ecuación implícita y clasificación.
Curvas racionales. Coordenadas homogéneas y proyecciones cónicas. Curvas de Bézier racionales. Algoritmo de De Casteljau con pesos. Control geométrico de los pesos. Invarianza proyectiva.
Curvas racionales a pedazos. NURBS. Adaptación del algoritmo de De Boor.
Superficies. Interpolación bilineal y algoritmo de De Casteljau. Producto tensorial y parches de Bézier. Derivadas parciales, twists. Interpolación por parches de Bézier. Splines de dos variables. Diferenciabilidad. Interpolación mediante splines bicúbicos.
V. PROBLEMAS DISCRETOS
Intersección de segmentos. Algoritmo óptimo de ordenación. Algoritmo de barrido para obtener los puntos de intersección de los segmentos de un conjunto dado. Costo del algoritmo en función del resultado final.
Triángulación de polígonos. ¿Cómo vigilar una galeria de arte? Polígonos simples cerrados. Área y orientación. Existencia de triangulaciones. Caras, aristas, vértices y fórmula de Euler. Triangulación dual y orejas. Triangulación por desorejamiento. Polígonos monótonos y triangulación.
Cálculo de envolturas convexas. Polígonos y poligonales. Orientación. Algoritmos directos torpes. Quick hull. Algoritmo óptimo de Graham. Algoritmo incremental. Divide y vencerás. Cálculo de envolventes convexas 3D.
Diagramas de Voronoi. ¿Cómo decidir a que buzón llevar las cartas? Celdas de Voronoi. Casos degenerados. Caras aristas y vértices del diagrama de Voronoi. Algoritmo directo de cálculo. Triangulación de Delaunay. Diagramas de Voronoi y envolturas convexas.
Bibliografía
[1] G. Farin: Curves and Surfaces for Computer Aided Geometric Design: A Practical Guide,(4th. Edition) Academic Press, Inc., Boston , 1997.
[2] M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf: Computational Geometry, Springer-Verlag, Berlin, 1997.
[3] J. O’Rourke: Computational Geometry in C, Cambridge University Press, 1994.
