Diferencia entre revisiones de «Geometría computacional»
Contenido eliminado Contenido añadido
m ElTioTradec trasladó la página Geometría computacional a Geometría algorítmica |
Sin resumen de edición Etiquetas: Revertido Edición visual |
||
Línea 1:
[[Archivo:Cilindro comp.jpg|thumb|Cilindro renderizado mediante un programa de ordenador.]]
La '''geometría
== Introducción ==
Una parte significativa del crecimiento que la [[Matemática discreta|Matemática Discreta]], como un todo, ha experimentado en los últimos años, ha consistido en un desarrollo sustancial de la [[Geometría discreta|Geometría Discreta]]. Esto ha sido impulsado, en parte, por el desarrollo de ordenadores cada vez más potentes, y por la reciente explosión de actividad en el campo relativamente joven de la
Hasta hace poco,
En los últimos años ha aumentado el número de áreas en las que se aplican los resultados de esta disciplina. Entre las mismas se incluyen la [[ingeniería]], [[cristalografía]], diseño asistido por computador, sistemas de posicionamiento global, [[robótica]], sistemas de detección de errores, modelado geométrico, gráficos por ordenador, optimización combinatorial, visión por ordenador, reconocimiento de patrones y modelado sólido.
==Descripción==
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
La [[Teoría de la complejidad computacional|complejidad computacional]] es fundamental para la geometría
El principal impulso para el desarrollo de la geometría
Las principales ramas de la geometría
* ''
|autor = [[Franco P. Preparata]] and [[Michael Ian Shamos]] | título = Computational Geometry - An Introduction | editorial = [[Springer-Verlag]]| año = 1985 | id = 1st edition: ISBN 0-387-96131-3; 2nd printing, corrected and expanded, 1988: ISBN 3-540-96131-3}}</ref><ref name=shamos1978/>
* ''
== Complejidad algorítmica ==
Línea 51 ⟶ 52:
3. ''"f es theta de g" y se notará f(n) = O(g(n)) si f(n) = O(g(n)) y f(n) = Q(g(n)).''
==
[[File:Convex Polygon triangulations.svg|thumb|Triangulación de un polígono. 1. [[Triangulación en abanico|Abanico]]. 2. [[Triangulación de peso mínimo|Mínimo peso]] 3. [[Triangulación de Delaunay|Delaunay]] ]]
[[File:GrahamScanDemo.gif|thumb|Cálculo del [[cierre convexo]] de un conjunto de puntos por el [[Método de Graham]].]]
[[File:Delaunay Voronoi.svg|thumb|[[Triangulación de Delaunay]] y [[Diagrama de Voronoi]] de un conjunto de puntos.]]
El objetivo principal de la geometría
Algunos de estos problemas parecen tan simples que no fueron considerados como tal hasta la llegada de los [[ordenador]]es. 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 ''[[problema del par de puntos más cercanos|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.
Línea 61 ⟶ 62:
<ref name=Fortune>{{Cita publicación|apellidos=Fortune |nombre=Steve |enlaceautor=Steve Fortune |apellidos2=Hopcroft|nombre2=J.E. |título=A note on Rabin's nearest-neighbor algorithm |publicación=Information Processing Letters |volumen=8 |número=1 |año=1979 |doi= |páginas=20-23 |url=https://ecommons.cornell.edu/handle/1813/7460 }}</ref>
=== Algunos problemas clásicos ===
A continuación se enumeran algunos problemas clásicos que han sido estudiados en el campo del la
* [[Cierre convexo]]: Dado un conjunto de puntos, encontrar el polígono convexo de menor área que los contenga.
Línea 74 ⟶ 75:
===Problemas dinámicos===
Otra gran clase es la de los problemas dinámicos, en la cual el objetivo es encontrar un algoritmo eficiente para encontrar la solución repetidamente tras cada modificación incremental de los datos de entrada (adición o supresión de los elementos geométricos de entrada). Los algoritmos para los problemas de este tipo típicamente supone estructuras dinámicas de datos. Cualquiera de los problemas de geometría
La complejidad computacional para esta clase de problemas se estima mediante:
*El tiempo y espacio requeridos para construir la estructura de datos que se va a buscar.
Línea 88 ⟶ 89:
En algunos contextos de problemas de consultas hay expectativas razonables en la secuencia de las consultas, la cual puede ser aprovechada ya sea por estructuras de datos eficientes o por estimaciones de la complejidad computacional más ajustadas. Por ejemplo, en algunos casos es importante saber el peor caso para el tiempo total de la secuencia de ''N'' consultas antes que el de una única consulta.
== Aplicaciones de la geometría
Uno de los aspectos más interesantes de la [[Geometría computacional|
El significado del término computación se ha expandido notoriamente desde la introducción de los ordenadores, hará ahora unos cincuenta años.
Línea 95 ⟶ 96:
Atendiendo a los objetos que procesan, destacan tres tipos de aplicaciones de los ordenadores. La primera generación va a ser la de los cálculos numéricos, aplicados sobre todo a problemas científicos y técnicos. La segunda, propiciada por necesidades más comerciales y administrativas, incorporaba largas listas de datos (por ejemplo alfabéticos), con vistas a cómo leer, almacenar, modificar, seleccionar, e imprimir esos datos.
Todo esto naturalmente pervive, y con fuerza, pero vivimos una tercera generación de aplicaciones dominada por el procesamiento de información geométrica y gráfica, presente en áreas tan diversas como son la [[medicina]], la [[cartografía]], el [[Robótica|control de robots]] o el [[Dirección de arte|diseño artístico]]. La
Se podría decir que las aplicaciones van a preceder la disciplina, y ahora que ésta tiene ya un núcleo teórico sólidamente constituido, como sus vertientes prácticas corresponden a tecnología de máxima vanguardia, la demanda de resultados continúa con la misma fuerza y exigencia que al principio. Por eso diremos que, en
Dentro de los campos de aplicación más directamente relacionados con la disciplina se destacan:
Línea 118 ⟶ 119:
=== Gráficos por ordenador ===
Lo que se entiende hoy por Gráficos por Ordenador (o Informática Gráfica), pese a ser una rama de [[Informática]] que también se ocupa de los fenómenos geométricos desde el punto de vista del cálculo, es un área bien distinta de la
Mientras que ésta se ocupa de proporcionar los fundamentos teóricos involucrando el estudio de algoritmos y de estructuras de datos para hacer cálculos geométricos, la Informática Gráfica se ocupa del desarrollo práctico del [[software]], [[hardware]] y algoritmos necesarios para crear gráficos en la pantalla del ordenador.
Sin embargo, ambas tienen algunas técnicas similares (otras muy distintas), y sin duda alguna, se influencian mutuamente. Desde el ámbito de los informática gráfica se dan a conocer problemas prácticos a la comunidad de estudiosos de la
La
Una cuestión muy importante en informática gráfica es la representación realista de escenas complejas. Uno de los requisitos es la eliminación de líneas y superficies ocultas a partir de un modelo tridimensional. Las primeras soluciones razonablemente satisfactorias van a iniciar áreas importantes de investigación dentro de la geometría
Otros problemas fundamentales que aparecen en Gráficos son: el trazado de rayos, la aproximación de contornos mediante poligonales y la triangulación de polígonos. En todos ellos la
En una habitación poligonal ([[galería de arte]]) en el plano se colocan cuatro cámaras de manera que se pueda vigilar con ellas toda la sala. Si se está interesado en averiguar cuál es la región que es visible por una sola cámara esto es equivalente a eliminar las porciones del polígono que quedan ocultas. Uno de los algoritmos estándar usado para resolver este problema de líneas ocultas en el plano es el debido a [[Freeman Dyson|Freeman]] y Loutrel hace más de diez años antes de lo que se atribuye como el nacimiento de la
Utilizando técnicas desarrolladas para el diseño de algoritmos en
=== Fabricación industrial ===
Línea 145 ⟶ 146:
==== Robótica ====
Una de las principales aplicaciones de
En el primero, el problema típico involucra un robot, generalmente modelizado como un punto, un disco, o un polígono en dos dimensiones, o bien como un poliedro en tres dimensiones que ha de moverse en el espacio entre una colección de obstáculos. Una de las preguntas usuales es ¿puede moverse el robot desde un punto A a otro B sin colisionar con los obstáculos?
Línea 159 ⟶ 160:
* [[Octree]] y [[Árbol kd]] : Organizar el espacio para realizar búsquedas geométricas de forma efectiva.
==
[[Archivo:CAD3D.jpg|thumb|right|Pieza modelada en Software CAD]]
{{principal|Diseño asistido por computadora}}
| |||