Geometría computacional

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda
Cilindro renderizado mediante un programa de ordenador.

La geometría computacional es una rama de las ciencias de la computación dedicada al estudio de algoritmos que pueden ser expresados en términos de la geometría. Algunos de los problemas puramente geométricos surgen del propio estudio de dichos algoritmos, y este tipo de problemas también se considera parte de la geometría computacional. [1]

Descripción[editar]

Es una disciplina constructiva, de carácter abstracto, que utiliza técnicas de la geometría clásica, la topología, la teoría de grafos, la teoría de conjuntos y el álgebra lineal. La geometría computacional es independiente de la tecnología de las máquinas de computación, si bien pone atención en proporcionar soluciones que se comporten de forma computacionalmente robusta.

El principal impulso para el desarrollo de la geometría computacional se lo dio el avance de la computación gráfica y el diseño asistido por ordenador (CAD/CAM), que hacen uso intensivo de las técnicas de esta disciplina. Otras aplicaciones importantes de la geometría computacional incluyen la robótica (planificación de movimientos y problemas de visualización), los sistemas de información geográfica (SIG) (localización y búsqueda geométrica, planificación de rutas), diseño de circuitos integrados (diseño geométrico y verifición de CI), ingeniería asistida por computadora (CAE) (programación de máquinas controladas numéricamente).

Las principales ramas de la geometría computacional son:

  • Geometría computacional combinatoria, también llamada geometría algorítmica, que trata de objetos geométricos como entidades discretas. Un libro sobre el tema por Preparata y Shamos fecha la primera utilización del término "geometría computacional" en este sentido en 1975.[2] [1]
  • Geometría computacional numérica, que trata principalmente con la representación de objetos del mundo real en la forma adecuada para ser almacenada en un ordenador. Esta rama puede ser vista como un desarrollo de la geometría descriptiva y es a menudo considerada como una rama de los gráficos por ordenador o CAD. El término "geometría computacional", en este sentido ha estado en uso desde 1971.[3]

Geometría computacional combinatoria[editar]

Triangulación de un polígono. 1. Abanico. 2. Mínimo peso 3. Delaunay
Cálculo del cierre convexo de un conjunto de puntos por el Método de Graham.
Triangulación de Delaunay y Diagrama de Voronoi de un conjunto de puntos.

El objetivo principal de la geometría computacional combinatoria es el desarrollo de algoritmos y estructuras de datos eficientes para resolver problemas basado en términos de objetos geométricos: puntos, segmentos, polígonos, poliedros, etc...

Algunos de estos problemas parecen tan simples que no fueron considerados como tal hasta la llegada de los ordenadores. Por ejemplo, la determinación del cierre convexo de un conjunto de puntos puede ser realizada de forma intuitiva sobre un papel utilizando una regla, pero no es tan evidente dar las instrucciones a un ordenador para que lo resuelva. Otro problema, el de encontrar el par de puntos más cercanos puede ser implementado de forma sencilla mediante una búsqueda por fuerza bruta, calculando la distancia entre las n(n-1)/2 combinaciones posibles de pares de puntos y eligiendo la menor, pero esta solución no es aplicable para conjuntos con un elevado número de puntos. [4] [5]

Algunos problemas clásicos[editar]

A continuación se enumeran algunos problemas clásicos que han sido estudiados en el campo del la Geometría computacional combinatoria:[6] [7] [8] [9]

Estructuras de datos clásicas[editar]

Algunas estructuras empleadas en la resolución de problemas de forma eficiente:

  • Diagrama de Voronoi : Dado un conjunto de puntos, crear una partición del plano de acuerdo al punto más cercano.
  • Triangulación de Delaunay : Dado un conjunto de puntos, crear la mejor triangulación para interpolar valores en su interior.
  • Octree y Árbol kd : Organizar el espacio para realizar búsquedas geométricas de forma efectiva.

Geometría computacional numérica[editar]

Pieza modelada en Software CAD

Esta rama también llamada geometría máquina, diseño geométrico asistido por computador (CAGD), o modelado geométrico, trata principalmente del estudio de modelado y representación de curvas y superficies por ordenador. Para ello, emplea elementos como curvas y superficies paramétricas, (tipo curvas de Bézier o Splines) o curvas no paramétricas (como conjuntos de nivel).

Las áreas de aplicación incluyen industrias como diseño de naves, aeronaves y automóviles, diseño de escenarios y personajes de videojuegos, o animación por computadora, entre otras.

Referencias y enlaces externos[editar]

  1. a b Shamos, Michael (1978). «Computational Geometry» (PDF). Yale University. 
  2. Franco P. Preparata and Michael Ian Shamos (1985). Computational Geometry - An Introduction. Springer-Verlag. 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3. 
  3. Forrest, A. (1971). «Computational geometry». Proc. Royal Society London 321 (1545). doi:10.1098/rspa.1971.0025. 
  4. Khuller, Samir; Matias, Y. (1995). «A simple randomized sieve algorithm for the closest-pair problem». Information and Computation 118 (1): 34-37. doi:10.1006/inco.1995.1049. 
  5. Fortune, Steve; Hopcroft, J.E. (1979). «A note on Rabin's nearest-neighbor algorithm». Information Processing Letters 8 (1): 20-23. 
  6. Morales, Miguel Ángel (27 de junio de 2011). «Una interesante introducción a la Geometría Computacional». Gaussianos. Consultado el 1 de marzo de 2017. 
  7. Rivero, Francisco. «Geometría Computacional». Consultado el 1 de marzo de 2017. 
  8. Grima, Clara (2011). «Cada uno en su región y Voronoi en la de todos». Naukas. 
  9. O'Rourke, Joseph. Computational Geometry in C (2 edición). Cambridge University Press. ISBN 9780521649766. 

Otros recursos[editar]