Saltar al contenido ForoHackers

Geometría computacional: por dónde empezar

Geometría computacional
#906 · Ophuscado · · Denunciar

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

  1. Vectores, productos escalar y vectorial, y la prueba de orientación.
  2. Implementa la envolvente convexa de puntos aleatorios y dibújala.
  3. Comprueba si un punto está dentro de un polígono y si dos segmentos se cortan.
  4. Aprende la línea de barrido y construye una triangulación de Delaunay; luego dibuja su dual de Voronoi.
  5. 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

Inicia sesión o únete para responder.