La geometría computacional diseña algoritmos para objetos geométricos: puntos, segmentos, polígonos, círculos y formas de más dimensiones. Responde preguntas como qué puntos caen dentro de una región, cuál es el vecino más cercano o cómo mallar una superficie. Los mapas, los gráficos, la robótica, el CAD y los juegos dependen de ella.
Conceptos clave
- Prueba de orientación: el signo de un producto vectorial dice si tres puntos giran a la izquierda o a la derecha; la mayoría de los algoritmos se construyen sobre ella.
- Envolvente convexa: la menor forma convexa que contiene un conjunto de puntos, hallada en O(n log n) con el barrido de Graham o similar.
- Línea de barrido: mover una línea imaginaria por el plano y conservar solo los objetos que toca; así se hallan las intersecciones de segmentos.
- Triangulación y diagramas de Voronoi: la triangulación de Delaunay y su dual dividen el espacio según la proximidad.
- Índices espaciales: los árboles k-d, los quadtrees y los árboles R aceleran las consultas por rango y de vecino más cercano.
Vocabulario
- Degeneración: un caso especial, como tres puntos alineados, que rompe el código ingenuo.
- Predicados robustos: pruebas que dan la respuesta correcta incluso con error de redondeo, mediante aritmética exacta o adaptativa.
- Polígono: una cadena cerrada de segmentos; simple significa que no se cruza consigo mismo.
- Dualidad: una transformación que convierte puntos en rectas y viceversa, y facilita algunos problemas.
Qué estudiar, en orden
- Vectores, productos escalar y vectorial, y la prueba de orientación.
- Implementa la envolvente convexa de puntos aleatorios y dibújala.
- Comprueba si un punto está dentro de un polígono y si dos segmentos se cortan.
- Aprende la línea de barrido y construye una triangulación de Delaunay; luego dibuja su dual de Voronoi.
- Añade un árbol k-d para la búsqueda del vecino más cercano y contrástalo con la fuerza bruta.
Etiquetas relacionadas
#algorithms #computer-graphics #data-structures #spatial-data #linear-algebra