- Particionado del espacio
-
Particionado del espacio
En matemáticas, el particionado del espacio es el proceso de dividir un espacio (normalmente un Espacio euclídeo) en dos o más conjuntos disjuntos (ver también Partición (matemáticas)). En otras palabras, el particionado del espacio divide un espacio en regiones no superpuestas. Cualquier punto en el espacio se encuentra en una, y sólo una, de las regiones.
Los sistemas de particionado suelen ser jerárquicos, lo que significa que un espacio (o una región del espacio) está dividida en varias regiones, y después el mismo sistema de particionado se aplica recursivamente a cada una de las regiones creadas. Estas regiones pueden organizarse en una estructura de árbol, llamada un árbol de particionado.
La mayor parte de los sistemas de particionado del espacio usan planos (o, en más dimensiones, hiperplanos) para dividir el espacio: los puntos de una de los lados del plano forman una región, y los puntos de la otra forman otra región. Los puntos que se encuentran exactamente en el plano normalmente son asignados arbitrariamente a uno u otro lado. El particionado recursivo emplean planos que de, de esta forma, producen un árbol BSP, una de las formas más comunes de particionado.
El particionado del espacio es especialmente importante en los gráficos por computadora, donde se emplean con frecuencia para organizar los objetos en una escena virtual. Almacenando los objetos en una estructura de datos de particionado hace más fácil y rápido realizar ciertas operaciones geométricas — por ejemplo, determinar si dos objetos cercanos están colisionando, o si un objeto está en la trayectoria de un rayo (Ray Tracing).
Los sistemas más comunes incluyen::- Árboles BSP
- Árboles cuaternarios
- Árboles octales
- Árboles kd
Categoría: Algoritmos geométricos
Wikimedia foundation. 2010.
