presentación de powerpoint - ua€¦ · introducción a la geometría computacional copyright ©...
TRANSCRIPT
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante 1
Librerías geométricas
Computación Geométrica
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante 2
Librerías geométricas
• java.awt.geom• CGAL• Carácterísticas de una biblioteca geométrica
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante 3
La librería java.awt.geom
• En el paquete java.awt:• Interfaz Shape• Clase Polygon
• En el paquete java.awt.geom:• Interfaz PathIterator• Clases de utilidad matemática (AffineTransform,
Dimension2d)• Objetos geométricos (Arc2D, CubicCurbe2D,
Ellipse2D, Line2D, Point2D, QuadCurve2D, Rectangle2D, RoundRectangle2D)
• Clase Area
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante 4
Clases de la librería java.awt.geom
AffineTransform
Arc2D Arc2D.Double Arc2D.Float
Area
CubicCurve2D CubicCurve2D.Double CubicCurve2D.Float
Dimension2D
Ellipse2DEllipse2D.Double Ellipse2D.Float
FlatteningPathIterator GeneralPath
Line2D Line2D.Double Line2D.Float
Point2D Point2D.Double Point2D.Float
QuadCurve2D QuadCurve2D.Double QuadCurve2D.Float
Rectangle2D Rectangle2D.Double Rectangle2D.Float
RectangularShape
RoundRectangle2D RoundRectangle2D.Double RoundRectangle2D.Float
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante 5
Formas básicas
Shape line = new Line2D.Float(x1, y1, x2, y2); Shape arc = new Arc2D.Float(x, y, w, h, start, extent, type);Shape oval = new Ellipse2D.Float(x, y, w, h);Shape rectangle = new Rectangle2D.Float(x, y, w, h); Shape roundRectangle = new RoundRectangle2D.Float( x, y, w, h, arcWidth, arcHeight);
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante 6
Interfaz Shape
• La implementan: Area, CubicCurve2D, GeneralPath, Line2D, Polygon, QuadCurve2D, Rectangle, RectangularShape
• Métodos:
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante 7
Clase Area
• Implementa el interfaz Shape• Además implementa operaciones de CAG
(Constructive Area Geometry) con otras áreas cerradas como rectángulos, elipses y polígonos: Add, Substract, Intersect, ExclusiveOR
Area shape = new Area(shape1); shape.add(new Area(shape2)); shape.subtract(new Area(shape3)); shape.intersect(new Area(shape4)); shape.exclusiveOr(new Area(shape5));
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante 8
GeneralPath
• Representa un camino geométrico compuesto de líneas rectas, curvas cuadráticas y cúbicas. Puede contener múltiples sub-caminos.
GeneralPath shape = new GeneralPath(); shape.moveTo(x, y); shape.lineTo(x, y); shape.quadTo(controlPointX, controlPointY, x, y); shape.curveTo(controlPointX1, controlPointY1, controlPointX2, controlPointY2, x, y); shape.closePath();
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante 9
PathIterator
• Interfaz que permite recorrer el borde de cualquier objeto Shape.
• Cualquier objeto que implementa la interfaz Shape debe implementar el método getPathIterator
• Métodos:• currentSegment• next• isDone
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante
CGAL
• Proyecto Open Source financiado inicialmente por la UE (página web)
• Librería C++ para algoritmos geométricos• Gráficos por ordenador, visualización científica, métodos
numéricos, biología molecular, y muchos otros proyectos• Algoritmos: triangulaciones, diagramas de Voronoi,
polígonos, algoritmos de convex hull, etc.• Objetos geométricos: puntos (2D y 3D), polígons,
polihedros, mallas, curvas, ...• Módulos y paquetes
10
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante
Algoritmos y estructuras de datos
11
(Curso CGAL, Siggraph 2008)
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante 12
Estructura de CGAL
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante
Algunos paquetes
13
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante
Algunos paquetes
14
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante
Algunos paquetes
15
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante
Ejemplo de código
• Uso extensivo de los templates y de la sobrecarga de operadores
• Se parametriza el tipo básico de los puntos:• Cartesiano, homogéneno• Coordendas: float,double,rational, intervalo
16
Point_2< Cartesian<double> > p(1.0, 1.0), q;Vector_2< Cartesian<double> > v;v = p - ORIGIN;q = ORIGIN + v; assert( p == q );
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante
Más información
• Web de CGAL (http://www.cgal.org/)• Curso Siggraph 2008• Filosofía de CGAL• Paquetes de CGAL
17
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante 18
Carácterísticas de una bib. geométrica
• Una buena biblioteca geométrica debe ser:• Correcta• Robusta• Flexible• Fácil de usar• Eficiente
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante 19
Correcta
• La corrección se refiere a conformidad con la especificación.
• Una biblioteca es correcta cuando se comporta como está especificado.
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante 20
Robusta
• Pequeños cambios en los datos de entrada no deben cambiar una solución correcta
• Se deben tratar correctamente:• Errores producidos por el redondeo• Casos degenerados
• Soluciones:• Algoritmos más elaborados• Aritmética racional exacta
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante
Un ejemplo de problema con double
21
(Curso CGAL, Siggraph 2008)
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante
Otro ejemplo
• Dos rectas paralelas cuando sus tangentes son iguales (o el denominador de la ecuación de intersección es 0)
• Desplazamos la primera recta una distancia de 1/3 y la segunda 1000/3000
• Las rectas dejan de ser paralelas por problemas de redondeos
22
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante 23
Ejemplos de casos degenerados
(tomado del tutorial de CGAL)
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante 24
Flexible
• Modular• Adaptable• Extensible• Abierta
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante 25
Fácil de usar
• Uniforme en los nombres (de paquetes, clases, interfaces, constantes, parámetros, …)
• Módulos completos y mínimos• Funcionalidad completa y rica
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante
NodeBox: una librería de última hora
• NodeBox: http://nodebox.net/code/index.php/Home• Basada en Python• Orientada a visualización
26
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante
Ejemplo de código
27
n = 80for i in range(n): r = 50.0 dy = random(n) d = 1.0*i/n for j in range(i/2): nostroke() fill(d*0.9, d*0.6, 1.0*j/i/2, 0.2*d) stroke(d*0.9, d*0.8, 1.0*j/i/2, d*0.7) push() translate(i/0.75, dy) rotate(10*j) r2 = 4+ 10.0 * j/i oval(0-r2*0.5+j*5, 0-r2*0.5, r2, r2) line(j*5, 0, 0, 0) pop() fill(d*0.9, d*0.6, 0, 1.0-d) nostroke() rotate(5)
Introducción a la Geometría Computacional Copyright © 2010-2011 Universidad de Alicante
Ejemplos
28