Partición del espacio - Space partitioning
En geometría , la partición del espacio es el proceso de dividir un espacio (generalmente un espacio euclidiano ) en dos o más subconjuntos disjuntos (ver también partición de un conjunto ). En otras palabras, la partición del espacio divide un espacio en regiones que no se superponen. Entonces se puede identificar cualquier punto del espacio para que se encuentre exactamente en una de las regiones.
Visión de conjunto
Los sistemas de división del espacio son a menudo jerárquicos , lo que significa que un espacio (o una región del espacio) se divide en varias regiones, y luego el mismo sistema de división del espacio se aplica de forma recursiva a cada una de las regiones así creadas. Las regiones se pueden organizar en un árbol , llamado árbol de partición de espacio .
La mayoría de los sistemas de división del espacio utilizan planos (o, en dimensiones superiores, hiperplanos ) para dividir el espacio: los puntos en un lado del plano forman una región y los puntos en el otro lado forman otra. Los puntos que se encuentran exactamente en el plano suelen asignarse arbitrariamente a uno u otro lado. La división recursiva del espacio utilizando planos de esta manera produce un árbol BSP , una de las formas más comunes de división del espacio.
Usos
En gráficos por computadora
La partición del espacio es particularmente importante en los gráficos por computadora , especialmente utilizada en el trazado de rayos , donde se usa con frecuencia para organizar los objetos en una escena virtual. Una escena típica puede contener millones de polígonos. Realizar una prueba de intersección de rayo / polígono con cada uno sería una tarea muy costosa desde el punto de vista computacional.
Almacenar objetos en una estructura de datos de partición de espacio ( árbol k -d o árbol BSP, por ejemplo) facilita y agiliza la realización de ciertos tipos de consultas de geometría; por ejemplo, para determinar si un rayo se cruza con un objeto, la partición de espacio puede reducir el número de la prueba de intersección a unos pocos por rayo primario, lo que arroja una complejidad de tiempo logarítmica con respecto al número de polígonos.
La partición de espacio también se usa a menudo en algoritmos de línea de exploración para eliminar los polígonos del frustum de visualización de la cámara , lo que limita el número de polígonos procesados por la tubería. También hay un uso en la detección de colisiones : determinar si dos objetos están cerca uno del otro puede ser mucho más rápido usando la partición de espacio.
En el diseño de circuitos integrados
En el diseño de circuitos integrados , un paso importante es la verificación de las reglas de diseño . Este paso asegura que el diseño completo se pueda fabricar. La verificación involucra reglas que especifican anchos y espaciamientos y otros patrones geométricos. Un diseño moderno puede tener miles de millones de polígonos que representan cables y transistores. La verificación eficiente depende en gran medida de la consulta de geometría. Por ejemplo, una regla puede especificar que cualquier polígono debe tener al menos n nanómetros de cualquier otro polígono. Esto se convierte en una consulta de geometría al ampliar un polígono en n / 2 en todos los lados y consultar para encontrar todos los polígonos que se cruzan.
En teoría de probabilidad y aprendizaje estadístico
El número de componentes en una partición espacial juega un papel central en algunos resultados de la teoría de la probabilidad. Consulte la función de crecimiento para obtener más detalles.
En Geografía y SIG
Son muchos los estudios y aplicaciones donde la Realidad Espacial Geográfica está dividida por criterios hidrológicos , administrativos , matemáticos o muchos otros.
En el contexto de Cartografía y GIS - Sistema de Información Geográfica , es común identificar las celdas de la partición mediante códigos estándar . Por ejemplo, el código HUC que identifica cuencas y subcuencas hidrográficas, los códigos ISO 3166-2 que identifican países y sus subdivisiones, o DGG arbitrarios : cuadrículas globales discretas que identifican cuadrantes o ubicaciones.
Estructuras de datos
Los sistemas comunes de partición de espacios incluyen:
Numero de componentes
Suponga que el espacio euclidiano n-dimensional está dividido por hiperplanos que son -dimensionales. ¿Cuál es la cantidad de componentes en la partición? El mayor número de componentes se alcanza cuando los hiperplanos están en posición general , es decir, no hay dos paralelos ni tres tienen la misma intersección. Denote este número máximo de componentes por . Entonces, se cumple la siguiente relación de recurrencia:
- - cuando no hay dimensiones, hay un solo punto.
- - cuando no hay hiperplanos, todo el espacio es un solo componente.
Y su solución es:
- si
-
si
- (considere, por ejemplo, hiperplanos perpendiculares; cada hiperplano adicional divide cada componente existente en 2).
que está delimitado superior como:
