Desarrollo

El proyecto se encuentra dividido en dos partes:

Obtención de la Triesfera Exterior de Mínimo Volumen.

Obtención de la Triesfera Interior de Máximo Volumen.

El procedimiento seguido en ambas es similar, y está basado en la minimización/maximización de una función multidimensional aplicando un método de optimización para este tipo de funciones: El Método Downhill Simplex. En éste nivel (Nivel Superior) se trabaja con la posición de la triesfera en el espacio, es decir, con las coordenadas de los centros que la definen. La función que se ha de optimizar, constituye el Nivel Inferior del procedimiento. Dicha función está basada en la Transformada de Hough y es la encargada de buscar los radios que generarán el volumen mínimo/máximo de la triesfera para la posición definida por el nivel superior.

Antes de continuar conviene explicar determinados conceptos usados a lo largo del proyecto.

Biesfera. Cuerpo geométrico definido en el espacio por dos centros, C₀ y C₁, y dos radios, r₀ y r₁, en la Figura 1, se puede ver un corte longitudinal de la biesfera.

Figura 1

Figura 1 Corte longitudinal de una biesfera.

Su representación 3D se puede generar por rotación sobre el eje C₀-C₁.

Figura 2.1 Figura 2.2 Figura 2.3

Figura 2 Biesfera. Representación 3D.

Para que una biesfera sea válida, debe cumplir la siguiente restricción: |r₀-r₁| < l₀₁. Donde l₀₁ es la longitud del eje. Esto es así porque, en caso de no cumplirse esta restricción, querría decir que la biesfera ha degenerado en una esfera ya que la de radio mayor estaría envolviendo completamente a la otra.

A la biesfera de centros C₀, C₁ y radios r₀, r₁, se le denota como S₀₁.

Triesfera. La triesfera está compuesta por tres biesferas. Su ubicación en el espacio viene definida por tres centros, C₀, C₁ y C₂, y tres radios, r₀, r₁ y r₂, es decir, las biesferas que la definen son S₀₁ de centros C₀, C₁ y radios r₀, r₁; S₀₂ de centros C₀, C₂ y radios r₀, r₂ y S₁₂ de centros C₁, C₂ y radios r₁, r₂. Dichas biesferas deberán cumplir las restricciones: |r₀-r₁| < l₀₁, |r₀-r₂| < l₀₂ y |r₁-r₂| < l₁₂. Siendo l₀₁, l₀₂ y l₁₂ las longitudes de los ejes C₀-C₁, C₀-C₂ y C₁-C₂ respectivamente. Además, la triesfera la forman 2 planos triangulares, superior e inferior, que son tangentes a la triesfera y actúan a modo de ‘tapas’ de su estructura triangular. Se denota como S₀₁₂.

Figura 3.1 Figura 3.2

Figura 3 Triesfera. Representación 3D.

Recta de Hough. Aplicando la Transformada de Hough a un punto, éste se convierte en una recta de parámetros: l_i y d_i. Dichos parámetros, en el caso de una biesfera, tienen el siguiente significado:

l_ies la posición relativa del punto al eje de la biesfera C₀ - C₁.

d_i es la distancia de dicho punto al eje.

Siguiendo en el caso de una biesfera, según el valor de l_i, tendremos tres grupos de puntos. Aquellos cuyo l_i Î ] 0,1[, son los denominados puntos intermedios (Half-Way Points) y se representan por HWP. Aquellos cuyo l_i£ 0, son los puntos exteriores (Out-Way Points), se representan por OWP^C₀. Por último los que tienen un l_i ³ 1, son también puntos exteriores y se representan por OWP^C₁.

Los OWP^C_i generan a su vez dos nuevos parámetros: d₀^min y d₁^min, definidos así:

d₀^min es igual al mayor d_i de los OWP^C₀.

d₁^min es igual al mayor d_i de los OWP^C₁.

Esto es obvio, si pretendemos envolver a todos los OWP, los radios mínimos que debemos usar son d₀^min y d₁^min.

Como la biesfera es una figura rotacional, aprovecharemos esta característica para basar el siguiente razonamiento. En la figura siguiente se muestra claramente como para envolver al punto p_i Î HWP con la biesfera, dejando al punto en su superficie, podremos jugar con los radios r₀ y r₁ basculando sobre p_i, pero siempre sin rebasar los límites inferiores d_i^min comentados anteriormente. Los radios r₀ y r₁ se relacionan entre sí por medio de la recta de Hough. Dicha recta aparece aplicando la ley de proporcionalidad siguiente:

( 1 )

Figura 4

Figura 4 Valor de l_i según la posición de los p_i. Variación de los radios r₀ y r₁.

Propiedades :

Su pendiente es siempre negativa. De

El corte de la recta de Hough con los ejes r₀=0 y r₁=0 es siempre positivo.

corte con r₀=0

( 2 )

corte con r₁=0

( 3 )

Cada recta de Hough divide el plano r₀r₁ con r₀ ³ d₀^min y r₁ ³ d₁^min, en dos semiplanos, el externo, que representa a biesferas que envuelven sobradamente a p_i, y el interno, representando a biesferas que no envuelven al citado punto.

Figura 5

Figura 5 División del plano r₀-r₁ por la recta de Hough.

El semiplano externo responde a la expresión

( 4 )

Como ya hemos dicho, cualquier punto de éste semiplano representa a una biesfera que envuelve al punto p_i. Dado un valor de r₀, estamos tomando un valor para r₁ mayor que el estrictamente necesario para envolver al punto, luego éste quedará sobradamente envuelto.

El semiplano interno responde a la expresión

( 5 )

Cualquier punto de éste semiplano representa a una biesfera que no envuelve al punto p_i. Dado un valor de r₀, estamos tomando un valor para r₁ menor que el estrictamente necesario para envolver al punto, luego éste no puede ser nunca envuelto.

Características :

Dado que la ecuación de la recta de Hough la podemos escribir así: , siendo: y . Podemos comprobar para los distintos valores que puede tomar l, la posición que toma la recta. Así:

Si y

Si y

Si y

Figura 6

Figura 6 Posición de la recta de Hough en función de l.

Llamaremos Recta ij de Hough a aquella generada por algún p_k proyectado sobre el eje C_i - C_j, es decir, aquella en la que sus variables son r_i y r_j.

Lugar de Mínimo Volumen (M_NVL). Si representamos gráficamente todas las rectas de Hough en función de r₀ y r₁, y teniendo en cuenta las afirmaciones anteriores, la línea de trazo grueso contendrá a la biesfera que envuelva, con el mínimo volumen, a todos los puntos del objeto a modelar. Llamaremos M_NVL ij a aquel en el que intervienen los radios r_i y r_j.

Figura 7

Figura 7 Lugar de Mínimo Volumen o M_NVL.

Las rectas r₀=d₀^min y r₁=d₁^min, constituyen las restricciones impuestas a los radios de la biesfera, es decir, los radios obtenidos deberán ser mayores o iguales a dichos parámetros, por lo tanto el M_NVL acaba en el punto de corte con dichas rectas.

Lugar de Máximo Volumen (M_XVL). Representando gráficamente todas las rectas de Hough en función de r₀ y r₁, y teniendo en cuenta las afirmaciones anteriores, la línea de trazo grueso contendrá a la biesfera con el máximo volumen, que no envuelve a ningún punto del objeto a modelar. Llamaremos M_XVL ij a aquel en el que intervienen los radios r_i y r_j.

Figura 8

Figura 8 Lugar de Máximo Volumen o M_XVL.

Los parámetros d₀^max y d₁^max,en el caso de una biesfera, representan los radios máximos que no envuelven a los OWP, es decir, d₀^max será la menor distancia de los OWP^C₀ al centro C₀, mientras que d₁^max es la menor distancia de los OWP^C₁ al centro C₁. Nótese que los conjuntos OWP^C_i pueden estar vacíos, careciendo de significado el correspondiente d_i^max.

Puesto que constituyen radios máximos, el M_XVL acaba en el punto de corte con las rectas r₀=d₀^max y r₁=d₁^max.