ÁRBOLES BSP

Un árbol BSP ( Binary Space Partitioning) representa recursividad, una partición jerárquica, o subdivisión de del espacio 

en n-dimensiones. La construcción de un árbol BSP es un proceso en el cuál se toma un sub-espacio y se particiona en 

cualquier hiper-plano que se intersecta  en el interior del sub-espacio. El resultado son 2 nuevos sub-espacios que pueden 

estar a su vez particionados por medio de una aplicación recursiva del método.

Un hiper-plano en un objeto en un espacio de n-1 dimensiones en el cuál se puede utilizar para dividir el espacio en 2 

mitades de espacios. Por ejemplo, en un espacio de 3 dimensiones, el hiper-plano es un plano. En dos dimensiones se 

utiliza la línea. 

Los árboles BSP son extremadamente versátiles, porque son muy fáciles de ordenar y clasificar sus estructuras. Una forma 

fácil de pensar en un árbol BSP es limitarse a 2 dimensiones. Para simplificar la situación, al momento de representar los 

ejes X y Y sólo se utilizarán líneas paralelas, y después se dividirá el espacio de forma equitativa para cada nodo. Por 

ejemplo un cuadrado en un plano XY, se selecciona la primera división y esta será la raíz del árbol y se corta el cuadrado 

por la mitad en dirección del eje X. En cada corte se escoge una línea en orientación opuesta a la última, y el segundo 

corte dividirá cada nueva sección en dirección al eje Y. este proceso continuará de forma recursiva hasta alcanzar el punto 

deseado.

Para construir un árbol BSP, dados un conjunto de polígonos en tres dimensiones, si se desea construir un árbol BSP que 

contengan todos los polígonos:

El algoritmo para construir un árbol BSP es el siguiente:

1.              Seleccionar una partición del plano

2.              Particionar el conjunto de polígonos con el plano

3.              Repetir con cada uno de los dos nuevos conjuntos

Para seleccionar la partición del plano influye el uso que se le dará al árbol, el criterio d ordenamiento o eficiencia que se 

le dará para la construcción. Par algunos propósitos, es apropiado escoger la partición del plano de la entrada del conjunto 

de polígonos.

Para particionar un conjunto de polígonos en un plano se clasifica cada miembro del conjunto con respecto al plano. 

El criterio para terminar la construcción del árbol depende de la aplicación que se este desarrollando. Algún criterio sería 

cuando cada polígono estuviera posicionado de forma interna en un nodo, o maximizar la profundidad del árbol.

ÁRBOLES BINARIOS TRIANGULARES

Es una estructura de datos que combina la simplicidad de los árboles binarios con áreas de 2 dimensiones.  Normalmente 

en este tipo de árboles se piensa en el uso de triángulos con la hipotenusa como base y sus dos lados. 

si observamos el triángulo, la raíz del árbol es la A con un hijo derecho llamado B y un hijo izquierdo llamado C, pero C 

tiene a su vez un hijo derecho llamado D y un hijo izquierdo E.

Para saber cual es el hijo derecho y cual es el izquierdo se realiza de la siguiente manera, siempre se deberá de tener a 

la hipotenusa como base ya que si es así la raíz la tendremos justamente en la parte de arriba y de ahí podremos designar 

al hijo derecho e izquierdo.

En general este tipo de árboles es semejante con el árbol binario común, ya que solo cuenta con dos ramificaciones, i. e., 

hijo izquierdo e hijo derecho, también sabemos que al momento de construir un árbol se pueden tomar varios criterios, si 

nos referimos a derivaciones de expresiones regulares, tokens, gramáticas de contexto libre, podemos construirlo de varias

 formas o criterios, puede ser derivación por la izquierda o derivación por la derecha, en este tipo de árboles(BSP) ocurre lo 

mismo ya que dependiendo del tipo de aplicación o problema que se presente se usara la construcción del árbol más 

adecuada.

Una de las diferencias que puede haber es que en los árboles triangulares tenemos que guiarnos por la hipotenusa del 

triángulo para de ahí partir y saber cual es la raíz del árbol y sobre la base de este criterio sabremos cual es el hijo derecho 

o le hijo izquierdo y también si tienen más descendencia y hasta terminar con el triángulo más interno se tiene el final de la 

construcción de este tipo de árboles

Las estructuras de las que se hacen uso en el código en lenguaje C para poder crear árboles de este tipo son arreglos, 

apuntadores, estructuras (struct) para poder manipular los elementos de los árboles y saber como se irá desarrollando la 

construcción del árbol.

Para poder entender este tipo de árboles se tiene que tener nociones de los que son básicamente las estructuras de datos 

que existen y sus usos, en cuanto a la carrera se puede decir que las materias que son indispensables para poder entender 

estos temas son:

v                        DATOS Y ESTRUCTURAS DE ALMACENAMIENTO

v                        TEORÍA DE GRÁFICAS

v                        ESTRUCTURAS DE ALMACENAMIENTO

Una de tantas aplicaciones que en lo personal se me hace interesante es la resolución de problemas de optimización de 

programación entera y más específicamente los problemas binarios, como son los métodos de Gomory, Bifurcación y 

Acotamiento, Ramificación y Acotamiento para problemas binarios, Numeración Implícita, Aditivo de Balas, etc., ahí se 

puede hacer uso o aplicación de los árboles binarios tanto triangulares como los BSP.

BIBLIOGRAFÍA

Bretton Wade ,“BSP Tree Frequently Asked Questions (FAQ)”, , 

Abril 21, 1995

Seumas McNally, “Binary Triangle Trees and Terrain Tessellation”, < http:gamedev.net/reference/articles/article806.asp>, 1999