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

En la segunda parte del proyecto se pretende encontrar la triesfera que teniendo volumen máximo, no envuelva a ningún punto del objeto modelado.

El proceso es similar al seguido anteriormente para el cálculo de la triesfera de mínimo volumen exterior, por lo que se tratarán aquí los aspectos diferentes con el anterior y se hará referencia a los ya expuestos cuando sea necesario.

El punto de partida es el mismo que en el otro caso, es decir, el conjunto de puntos 3D que definen el objeto.

A continuación se calcula la posición de la triesfera inicial P₀ y 9 posiciones más como se explicó anteriormente.

El Downhill Simplex, en este caso, maximizará la función que tiene que evaluar. Dicha función es, también, una llamada al nivel inferior que computará los radios que hagan máximo el volumen engendrado por la triesfera.

El nivel inferior lo podemos considerar dividido en 2 partes. La primera dedicada a la transformación de los p_i en los l_i1, l_i2, y d_i. Y la segunda que, con esa información, obtiene los radios.

La primera parte es casi idéntica a la vista anteriormente, sus únicas diferencias son:

Las restricciones impuestas ahora por los OWP serán radios máximos que no envuelven a los citados OWP. Dichos radios máximos se nombran con d₀^max, d₁^max y d₂^max y corresponden a las siguiente expresiones

Nótese que algún conjunto OWP puede estar vacío y, por lo tanto, carecer de significado su correspondiente d_i^max.

Los puntos de corte que se consideran ahora para la ordenación de las rectas son aquellos en los que cortan las rectas al eje r₀=0 (véase la Figura 8). Dichos puntos son exactamente la b_i de la ecuación de la recta de Hough correspondiente.

La segunda parte es radicalmente diferente en su tratamiento, que no en su concepto. Aquí se descarta la utilización del Golden-Ratio basándonos en la siguiente observación:

Dado que la función volumen de la triesfera presenta sus máximos locales en los puntos de corte de las rectas de Hough que pertenecen al M_XVL, es decir, en los cambios de recta que se producen al recorrer el lugar. Es allí donde deberemos buscar el máximo global. No siendo necesario, por tanto, recorrer todo el lugar. Consideraremos, entonces, únicamente los citados puntos de corte.

Figura 21 Evaluación de la función volumen en un M_XVL.

La determinación del intervalo de búsqueda, puntos A y B, inicio y final del intervalo respectivamente, vendrá determinada por la existencia o no de las restricciones d₀^max, d₁^max y d₂^max. El procedimiento a seguir es el que a continuación se indica:

Determinación de A=(A.r₀,A.r₁,A.r₂).

Si el conjunto implica que existe d₁^max, entonces, si existen rectas 01 de Hough, se calcularán A.r₀ y A.r₁ como sigue

( 6 )

Dado que las rectas están ordenadas de menor a mayor b_i, será la primera recta de esta lista la que tenga el b_i mínimo. El valor de A.r₀ dependerá del valor que haya tomado A.r₁, así

Si A.r₁=min{b_i}, entonces A.r₀=0

Si A.r₁=d₁^max, A.r₀ se obtiene a partir de la recta que menor punto de corte dé con el eje r₁=d₁^max.

( 7 )

El A.r₀ obtenido debe cumplir que si . Si esto no se cumple, el M_XVL 01 consistiría en un sólo punto (d₀^max,d₁^max) y podríamos eliminar todas las rectas 01 de Hough, fijando el r₁ a d₁^max. Por el contrario, si se cumple lo anterior, podemos eliminar de la lista las rectas que tengan un b_i menor que el de la recta que satisfizo ( 7 ), ya que dichas rectas no aparecerán en el M_XVL.

Si no existieran rectas 01, las únicas restricciones las impondrían d₀^max y d₁^max, en el caso de que ellos también existan.

Si , entonces directamente y si existen rectas 01

en caso de no existir rectas 01, estaríamos, como en el caso anterior, con las únicas restricciones impuestas por d₀^max y d₁^max. De ahora en adelante, siempre que no existan rectas 01 y/o 02 de Hough, se fijarán los radios r₁ a d₁^max y/o r₂ a d₂^max respectivamente, por lo que no se comentará más este detalle.

Ahora se procede de forma análoga en el M_XVL 02, es decir, la forma de obtener A’.r₀ y A.r₂ es idéntica en la forma, si más que cambiar los r₁ por r₂ y el d₁^max por d₂^max, además, las rectas 01 de entonces serán ahora las rectas 02.

Tenemos dos puntos A (A.r₀ y A’.r₀), nos quedamos con el mayor r₀. Y si el mayor lo dio el M_XVL 01 calculo A.r₂, pero si el mayor lo dio el M_XVL 02 calcularemos A.r₁ y con ello queda completamente definido el punto A.

Determinación de B=(B.r₀,B.r₁,B.r₂).

Buscamos B en el M_XVL 01 de la siguiente forma:

Si implica la existencia de d₀^max, entonces si hay rectas 01

donde es el punto de corte de las rectas con el eje r₁ = 0. B.r₁ dependerá del valor que haya tomado B.r₀. Así

Si B.r₀=d₀^max, B.r₁ se obtendrá de la recta con menor punto de corte para r₀=d₀^max.

( 8 )

el r₁ obtenido deberá cumplir que si . Si no se cumple, el lugar queda reducido a un único punto (d₀^max,d₁^max) y, por tanto, se pueden eliminar todas las rectas 01 fijando el r₁ a d₁^max. Por el contrario, si se cumple lo anterior, podremos eliminar del conjunto de rectas, aquellas cuya b_i sea superior a la b_i de la recta que satisfizo ( 8 ).

, entonces B.r₁ = 0. Además, se pueden eliminar del conjunto de rectas, aquellas cuya b_i sea superior a la b_i de la recta que dio el mínimo.

Si , directamente y si existen rectas 01

y se eliminan las rectas cuya b_i sea mayor que la b_i de la recta que dio el mínimo.

Igual que en la búsqueda de A, ahora se procede a buscar el punto B en el M_XVL 02, con los cambios que vimos anteriormente. De los dos B encontrados nos quedaremos con el menor. Si éste fue el perteneciente al M_XVL 01, calcularemos B.r₂, si lo fue el del M_XVL 02, calcularemos B.r₁ y dispondremos ya del punto B completamente definido.

Figura 22 Determinación del intervalo [A,B] en función de la existencia o no de d₀^max y d₁^max.

Falta una última consideración. Es posible que los intervalos [A,B] calculados para los dos lugares, no se solapen, es decir, que el punto B.r₀ de uno de ellos sea inferior al punto A.r₀ del otro. Si este fuera el caso, nos quedaríamos con el intervalo que recorre los menores r₀ y fijaríamos el otro radio (r₁ ó r₂ según el caso) a d_i^max convenientemente. En la Figura 23 se ha representado esta situación superponiendo el M_XVL 01 y 02 para poder apreciar el NO-SOLAPAMIENTO de los intervalos.

Figura 23 NO-SOLAPAMIENTO de los intervalos [A,B] del M_XVL 01 y 02.

Ahora que tenemos plenamente identificado el intervalo de búsqueda [A,B], debemos comprobar los radios r₂ de ambos puntos en el M_XVL 12, quedándonos con el que sea menor, en ambos casos.

En este momento estamos en condiciones de iniciar la búsqueda. Si A=B, calculamos el área de la triesfera en ese punto y acabamos devolviendo estos valores al nivel superior. Si A es distinto de B, lo primero que hacemos es calcular el área en A y luego en B y guardamos el que haya obtenido la mayor. Se entra ahora en un bucle que consiste en buscar en el M_XVL que corresponda (01 y/ó 02) el siguiente cruce de la 1ª recta de la lista con las pertenecientes al lugar. Dicho cruce debe cumplir que su r₀ sea mayor que el r₀ del cruce anterior y menor que B.r₀. Pues bien, en todo momento tendremos dos cruces a considerar, cada uno correspondiente a uno de los lugares de búsqueda, consideramos el menor y guardamos el otro (con lo que no habrá que buscar en ése lugar en la próxima iteración). Si el menor lo dio el M_XVL 01, calcularemos el r₂ correspondiente y evaluaremos el área en ese punto, quedándonos con la mayor hasta el momento. Si el menor lo dio el M_XVL 02, calcularemos el r₁ que nos falta y procederemos a calcular el área en ese punto guardando la mayor. Hay que tener en cuenta que, antes de calcular el área, se debe comprobar el r₂ en el M_XVL 12 y rectificarlo si es necesario, quedándonos con el menor.

El algoritmo seguirá iterando hasta que se alcance el punto B en los dos lugares, es decir, si en uno de los lugares llegamos a B y no en el otro, el bucle continúa buscando cruces en ése lugar hasta alcanzar B. También hay que decir que al bucle se entra si existen, al menos, rectas de algún tipo (01 ó 02).

Manteniendo la coherencia en el tratamiento de las biesferas NO válidas que se producen, la función que calcula su área devolverá esta vez, en esos casos, la mitad del área de la circunferencia de radio menor, para obligar así al Downhill Simplex a rectificar la posición.

He dejado para el final una última consideración a tener muy en cuenta, dada su importancia. Comenté antes que el máximo volumen se encontraba únicamente en los cambios de recta del M_XVL. Esto no es del todo cierto. Como hemos visto, los radios r₂ pueden verse rectificados al comprobarlos en el M_XVL 12. Analizando este asunto, se comprueba que como empezamos con valores para r₀ pequeños, ello implica que se obtengan r₁ y r₂ grandes. Al trasladar esto al lugar 12, un r₁ grande implica un r₂ pequeño y, por tanto, como nos quedamos con el menor, el r₂ será rectificado. Esto es así hasta que llegado a un punto el r₂ se deja de rectificar.

Pues bien, es en ése punto, donde se puede encontrar el máximo de la función volumen, luego habrá que determinar su posición. Para ello se anota el valor del r₀ donde se rectificó por última vez y que llamaremos r₀^{último cambio} y el del r₀ en donde ya no se rectifica que llamaremos r₀^{no rectifica}. Es evidente que el r₀ buscado estará en el intervalo ]r₀^{último cambio}, r₀^{no rectifica}[. Para su obtención sabemos que en dicho punto se cumple que

despejando r₂ en la última ecuación y r₁ en la primera. Sustituyendo estos valores en la segunda y operando se llega a

que es, precisamente, el punto buscado.

Hay que destacar dos casos particulares que se pueden presentar. Son los casos en los que alguna de las listas de rectas 01 ó 02 está vacía. En estos casos se procede así:

Rectas 01 vacía.

r₁ = d₁^max

r₂ = mínimo punto de corte de las rectas 12 con el eje r₁= d₁^max

r₀ = El correspondiente en el M_XVL 02 al r₂ calculado.

Rectas 02 vacía.

r₁ = mínimo punto de corte de las rectas 12 con el eje r₂=d₂^max

r₂ = d₂^max

r₀ = El correspondiente en el M_XVL 01 al r₁ calculado.

Dichos radios serían el punto en donde se deja de rectificar en esos casos.