Saltar al contenido ForoHackers

Geometría computacional: por dónde empezar

Geometría computacional
#3412 · · Citar · 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

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder