Geometría Computacional: Explorando conocimientos geométricos para la visión por computadora

Por Fouad Sabry

Qué es la geometría computacional

La geometría computacional es una rama de la informática dedicada al estudio de algoritmos que pueden expresarse en términos de geometría. Algunos problemas puramente geométricos surgen del estudio de algoritmos geométricos computacionales, y dichos problemas también se consideran parte de la geometría computacional. Si bien la geometría computacional moderna es un desarrollo reciente, es uno de los campos más antiguos de la informática con una historia que se remonta a la antigüedad.

Cómo se beneficiará

(I) Insights y validaciones sobre los siguientes temas:

Capítulo 1: Geometría computacional

Capítulo 2: Triangulación de Delaunay

Capítulo 3: Casco convexo

Capítulo 4: Diagrama de Voronoi

Capítulo 5: Geometría discreta

Capítulo 6: Triangulación de polígonos

Capítulo 7: Árbol de expansión mínimo euclidiano

Capítulo 8: Polígono simple

Capítulo 9: Triangulación de conjuntos de puntos

Capítulo 10: Triangulación (geometría)

(II) Respuestas las principales preguntas del público sobre la geometría computacional.

(III) Ejemplos del mundo real para el uso de la geometría computacional en muchos campos.

Para quién es este libro

Profesionales, estudiantes de pregrado y posgrado, entusiastas, aficionados y aquellos que quieran ir más allá del conocimiento o información básica para cualquier tipo de Geometría Computacional.

 

 

• Idioma: Español
• Editorial: Mil Millones De Conocimientos [Spanish]
• Fecha de lanzamiento: 4 may 2024

Vista previa del libro

Capítulo 1: Geometría computacional

La geometría computacional es un área de la informática dedicada al estudio de algoritmos que pueden expresarse en términos geométricos. Estos problemas también se consideran parte de la geometría computacional. A pesar de que la geometría computacional moderna es un fenómeno relativamente reciente, es uno de los temas más antiguos de la computación, con una historia que se remonta a la antigüedad.

Un elemento central de la geometría computacional es la complejidad computacional, si los métodos se aplican a conjuntos de datos muy grandes que contienen decenas o cientos de millones de puntos, esto tiene un enorme valor práctico.

En tales casos, la diferencia entre O(n2) y O(n log n) puede ser la diferencia entre días y segundos de cómputo.

El progreso en los gráficos por computadora y el diseño y fabricación asistidos por computadora (CAD / CAM) proporcionó la motivación principal para la formación de la geometría computacional como tema, sin embargo, muchos problemas en geometría computacional son de naturaleza clásica y pueden originarse en la visualización matemática.

La robótica (planificación de movimiento y problemas de visibilidad), los sistemas de información geográfica (SIG) (localización y búsqueda geométrica, planificación de rutas), el diseño de circuitos integrados (diseño y verificación de geometría IC), la ingeniería asistida por ordenador (CAE) (generación de mallas) y la visión por ordenador son otras aplicaciones importantes de la geometría computacional (reconstrucción 3D).

Las principales ramas de la geometría computacional incluyen:

La geometría computacional combinatoria, a menudo conocida como geometría algorítmica, se ocupa de objetos geométricos discretos. El término geometría computacional se utilizó por primera vez en este sentido en 1975, según un libro seminal sobre el tema de Preparata y Shamos.

La geometría computacional numérica, también conocida como geometría de máquinas, diseño geométrico asistido por computadora (CAGD) o modelado geométrico, se ocupa en gran medida de la representación de objetos del mundo real en sistemas CAD/CAM. Esta rama puede ser vista como una continuación de la geometría descriptiva y con frecuencia se clasifica como un subcampo de los gráficos por computadora o CAD. Desde 1971, el término geometría computacional se ha utilizado en este sentido).

El objetivo principal de la investigación en geometría computacional combinatoria es desarrollar algoritmos y estructuras de datos eficientes para resolver problemas expresados en términos de objetos geométricos fundamentales, como puntos, segmentos de línea, polígonos y poliedros.

Hasta la llegada de las computadoras, varios de estos problemas no se veían como problemas en absoluto, ya que parecen ser muy simples. Considere el problema del par más cercano como ejemplo:

Halla los dos puntos del plano con la distancia más corta entre ellos, dados n puntos en el plano.

Se podrían determinar las distancias entre cada par de puntos, qué número hay n(n-1)/2, y luego elegir el par con la separación más corta.

Este algoritmo de fuerza bruta tarda O(n2) tiempo, es decir,

Su tiempo de ejecución es proporcional al número de puntos al cuadrado.

Un resultado fundamental en geometría computacional fue el desarrollo de un algoritmo que requiere O (n log n).

Algoritmos aleatorios con un tiempo de ejecución anticipado de O(n), descubiertos adicionalmente.

Los problemas fundamentales de la geometría computacional se pueden clasificar de manera diferente en función de varios criterios. Se pueden distinguir las siguientes categorías generales:

En esta categoría de cuestiones, se proporciona una entrada y se debe construir o determinar la salida adecuada. Algunos problemas fundamentales con este tipo incluyen:

Envoltura convexa: Dado un conjunto de puntos, encuentre el poliedro/polígono convexo más pequeño que los contenga a todos.

Intersección de segmentos de línea: Determine las intersecciones entre una colección determinada de segmentos de línea.

Triangulación de Delaunay

Especificado un conjunto de puntos, divida el espacio de acuerdo con los puntos más cercanos a los puntos dados utilizando el diagrama de Voronoi.

Programación lineal

Dada una colección de puntos, identifique el par que tiene la distancia más corta entre ellos.

Par de puntos más distantes

Halla, dado un conjunto de puntos, el círculo más grande cuyo centro se encuentra dentro de su casco convexo y no encierra ninguno de ellos.

Conecte dos puntos en un espacio euclidiano (con obstrucciones poliédricas) utilizando el camino más corto.

Dado un polígono, triangula su interior dividiéndolo en triángulos.

Generación de mallas

Operaciones booleanas aplicadas a polígonos

La complejidad computacional de esta clase de problemas se evalúa en función del tiempo y el espacio (memoria de la computadora) necesarios para resolver una instancia específica del problema.

En los problemas de consulta geométrica, también conocidos como problemas de búsqueda geométrica, la entrada consta de dos componentes: el componente de espacio de búsqueda y el componente de consulta variable. Normalmente, el espacio de búsqueda debe procesarse previamente para que muchas consultas puedan abordarse de manera eficiente.

Una serie de cuestiones fundamentales de investigación geométrica son:

Procese previamente un conjunto de puntos para contar rápidamente el número de puntos dentro de una región de consulta.

Genere una estructura de datos que identifique eficazmente la celda en la que se coloca un punto de consulta, dada una partición basada en celdas del espacio.

Vecino más cercano: preprocese un conjunto de puntos para determinar rápidamente el punto más cercano a un punto de consulta.

Trazado de rayos: dado un conjunto de elementos en el espacio, genere una estructura de datos que identifique eficazmente el primer objeto con el que se cruza un rayo de consulta.

Si el espacio de búsqueda es fijo, la complejidad computacional de esta clase de problemas a menudo se evalúa utilizando el:

La cantidad de tiempo y espacio de almacenamiento necesarios para construir la estructura de datos que se va a buscar.

Tiempo (y ocasionalmente espacio extra) para responder preguntas.

Consulte Problemas dinámicos cuando se permita que el espacio de búsqueda fluctúe.

Otra clase significativa son los problemas dinámicos, para los cuales el objetivo es crear una técnica efectiva para localizar repetidamente una solución después de cada actualización de los datos de entrada (adición o eliminación de elementos geométricos de entrada). Normalmente, los algoritmos para estas situaciones utilizan estructuras de datos