Skip to the content ForoHackers
Log inJoin

Geometría computacional: por dónde empezar

Computational geometry
#3412 · · Quote · Report

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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply