LA CURVA BÉZIER

Un  intento de deducir la fórmula de esta famosa curva

 

Rafael Nieto Yosten

 

Introducción:

Como podrás ver, justo aquí arriba se encuentra una curva con un par de líneas rectas, tal vez se te haga muy familiar, a simple vista, no es mas que una simple curva.  Sin embargo esta curva a resultado ser de gran utilidad y ha tenido muchas aplicaciones, como en el diseño de automóviles, de aviones, o cualquier dibujo hecho por computadora.

 

Las computadoras siempre se han caracterizado por ser demasiado “cuadradas” en sus dibujos, y es por eso que se empezaron a hacer las curvas, ya que las computadoras adquirieron más poder de procesamiento… hubo muchos diferentes tipos de curvas, pero, de alguna manera u otra, la curva Bézier llegó a ser la más popular y la más usada en el dibujo por computadora.

 

Una de las ventajas de esta curva es que las variables que definen la curva tienen mucho que ver con su aspecto, además de que la curva se ve bonita.  El final de cada una de las 2 líneas rectas que salen desde los puntos donde la curva está “anclada”, son los puntos control, estos actúan como un imán que jala la curva hacia ellos.  Así, moviendo los puntos control se puede darle a la curva casi cualquier forma deseada.

 

A esta curva también se le conoce como un B-Spline, y para definirla solo se necesitan cuatro puntos: el punto de inicio (P₀), el punto control 1 (P₁), el punto control 2 (P₂) y el punto final (P₃).  Hay que aclarar que el B-Spline es un tipo de curva Bézier, pues la curva original Bézier en realidad puede tomar cualquier número de puntos control, y cada uno atrae a la curva un poco para darle forma.  El B-Spline, en cambio, sólo toma 2 puntos control, sin embargo, se pueden crear curvas muy grandes y complejas uniendo muchas pequeñas curvas B-Spline.

 

 

 

Lo que se pretende deducir y explicar en este texto

 

Primero que nada, este texto esta escrito por un estudiante de primer semestre de carrera (yo), y no cuento con los suficientes conocimientos para explicar todo acerca de las ecuaciones de esta curva.

 

La fórmula original de la curva Bézier, está basada en un polinomio especial que inventó el matemático Bernstein, y este polinomio, como dicen, “está en chino”, y claro, esta formula funciona para cualquier número de puntos control.

 

Esta fórmula original no la voy a tratar de explicar aquí, sino trataré de explicar la fórmula de un B-Spline, eso es, la curva con un punto de inicio, un punto final y sus 2 puntos control, aunque la fórmula para esta curva obviamente deriva de la fórmula original, yo me fui por mi propio camino para llegar al mismo lugar (pero más fácilmente).

 

Una explicación del B-Spline

 

 

Aquí podemos ver la curva B-Spline un poco más detallada, una cosa muy importante para poder deducir fórmulas es observar atentamente las características del problema a resolver, en este caso, tenemos que observar bien las características de esta curva.  No vamos a irnos a propiedades matemáticamente muy rigurosas y difíciles de entender, sino a características simples que yo creo que son fáciles de captar a simple vista..

 

Primero que nada, aquí vemos que la curva empieza en un punto (P₀) y termina en otro (P₃), eso es una característica.  Pero, lo que es más importante de todo es que la recta que va de P₀ a P₁ es tangente a la curva en el punto P₀, y la recta que va de P₂ a P₃ es tangente a la curva en el punto P_3.  Yo prolongué las rectas con una línea gris para que esto se viera más claramente.  Hasta aquí ya tenemos suficientes propiedades como para tratar de hacer una curva parecida a esta.

 

Pendientes cambiantes

Nosotros sabemos que podemos obtener la pendiente de la recta tangente a una función, utilizando la derivada.  Así que vamos a empezar a intentar de sacar nuestra primera curva con una ecuación de tipo:

Donde calculamos un valor y en función de un valor x, espero que ya sepas graficar pues aquí no es el lugar para aprender a hacerlo.

Vamos a suponer que yo quiero una curva que en una posición inicial x₁ tenga una pendiente inicial de m₁, y que en una posición final x₁, tenga una pendiente final de m₂.  Ahora sí, prepárense para lo bueno, porque vamos que tener que usar algo de matemáticas.

 

Diferencia entre las curvas y las rectas

Antes de empezar a poner un montón de ecuaciones, quiero explicar un poco por que metí esto de pendientes y rectas tangentes, hasta mencioné derivadas… Hay que entender la naturaleza de las curvas.  La gran diferencia entre una curva y una recta es su pendiente.  Una recta tiene la misma pendiente en todos sus puntos, y una curva, en cambio, tiene una pendiente diferente en cada uno de sus puntos.

 

El robot que dibuja líneas y curvas

Imaginemos que tenemos un robot que está hecho de manera que al ir caminando, va dejando tinta por donde pasa.  Si quisiéramos dibujar una línea recta, simplemente lo colocamos en una dirección y dejamos que avance.  En cambio, si queremos que dibuje una curva, el robot tendría que ir cambiando de dirección para dejar la forma de una curva.  Esa dirección que lleva el robot en determinada parte de la curva, es la pendiente de la curva.

 

 

	Aquí podemos ver una recta muy simple cuya ecuación es: Aquí marqué varios puntos tratando de dibujar la recta tangente de esta recta en cada punto, pero no se puede notar nada pues la misma recta es su recta tangente en todos sus puntos.  Si derivamos esta función obtenemos que:  o sea, una constante.  La pendiente siempre será 1 /2 para esta función.
	Aquí tenemos ya un caso muy diferente, una curva cuya ecuación es: Se puede observar muy claramente que la pendiente cambia conforme avanza la curva.  Si derivamos la función obtenemos lo siguiente: Al ver esta derivada nos damos cuenta que la pendiente ( y’ ) cambia en función de x, y por lo tanto, no es constante.

 

El hecho de que “la pendiente cambia” es la base que vamos a utilizar para tratar de encontrar ecuaciones de las curvas que queremos.  Retomemos la idea de hacer una curva que en un punto tenga una determinada pendiente, y en otro punto tenga otra pendiente. 

 

Pongámoslo así:

 

 

 

Disculpa un poco por mis dibujos, pues están hechos solo con unos pequeños programitas que hice y algo de ayuda de Paint, así que no están 100% exactos pero solo son para que se puede entender mejor la explicación.

 

Aquí vemos como la curva (cuya ecuación no conocemos), tiene una pendiente M₁ en X₁, y una pendiente M₂, en X₂, ahora, nosotros sabemos que de alguna manera, la pendiente m tiene que  ir de M₁ a M₂ cuando x cambie de X₁ a X₂.  Tenemos que crear una función  en donde m sea  igual a M₁ cuando x sea igual a X₁, y m sea igual a M₂ cuando x sea igual a X₂.  Esto es como si tuviéramos 2 puntos (X₁, M₁) y (X₂, M₂).  Lo más lógico sería ir cambiando m de M₁ a M₂ proporcionalmente conforme x cambie de X₁ a X₂; para esto podemos usar la ecuación de la recta para crear la función, basándonos en los 2 puntos que tenemos.

 

No te vayas a espantar con lo que acabo de decir, la ecuación de la recta la estamos aprovechando para crear una relación proporcional entre m y x, y no precisamente para crear una recta.  Si te pones a  analizar la ecuación de la recta obtenida a partir de 2 puntos, te darás cuenta que lo que estamos haciendo sí tiene sentido.  Si tenemos dos puntos (x1, y1) y (x2, y2); y utilizamos la fórmula de la recta a partir de 2 puntos, encontraremos una ecuación que, cuando x = x1, entonces y = y2, y cuando x = x2, entonces y = y2.  Lo mismo estamos haciendo nosotros, pero en vez de usar una coordenada Y como variable dependiente, estamos yéndonos a un nivel más “profundo”, y usamos la pendiente M como variable dependiente.

 

Ahora sí, encontremos nuestra ecuación .

Aquí tenemos la fórmula para la ecuación de la recta a partir de 2 puntos:

 

Pero en lugar de usar las Y, vamos a usar la M, y entonces nos quedaría así:

Despejamos:

 

Ahora algo muy importante que notar aquí, f(x) es una función que nos va a dar la pendiente de la curva, en x.  Nosotros bien sabemos que la derivada de una función, nos da otra función que es la que nos da la pendiente.  Pero aquí  f(x) es una función que nos da la pendiente, así que para poder encontrar la ecuación de la curva cuya pendiente es f(x), simplemente hacemos el proceso inverso, o sea que integramos la función f(x)!.

 

Entonces, vamos a decir que nuestra función de la curva va a ser de la forma

Así que para obtenerla, vamos a integrar:

Como verás, la fórmula no está tan bonita que digamos, pero debe funcionar, así que vayamos a intentar.  Hay algo que tenemos que hacer notar, esa C que está al final de nuestra ecuación integrada, según nuestras fórmulas de integración, siempre hay una C al final de la fórmula integrada.  Te preguntarás, ¿y que significa esa C?.

 

Hay dos maneras de entender que es esa C.  Al derivar una función que tiene una parte constante, esa parte desaparece en la función integrada.  Ejemplo:

¿Y que pasó con el 6 que estaba en la fórmula inicial?, pues desaparece pues es una constante, y la derivada de una constante es 0.  Sin embargo, cuando integramos, como no sabemos que número constante es el que estaba en la fórmula antes de ser derivada, simplemente se pone una C indicando que es esa constante que desapareció.

 

La otra manera, es entender gráficamente que representa la C.  La C es el punto de inicio de nuestra función:

 

La C es cuanto vale y cuando la curva intersecta con el eje Y, es decir, cuando la x vale 0.  Así que con la C podemos establecer la y inicial, cuando x valga 0.

 

Ahora que ya sabemos que significa, todo, hay que probar nuestras fórmulas para hacer una curva.  Digamos que queremos una curva que pase por el punto (0, 2), y que cuando x valga 3, tenga una pendiente de 7/4, y que cuando x valga 10, tenga una pendiente de –6/7.  Nuestras constantes quedarían así:

Como el punto por donde debe pasar es (0, 2), o sea, que ya y valga 2 cuando la x valga 0, entonces podemos asignar eso a la C:

El resto de las constantes es fácil de asignarlas:

Nuestra fórmula dice:

 

 

Sustituimos:

 

Veamos como quedó nuestra curva:

Si graficas la ecuación obtenida, te debió haber quedado una curva parecida a esta.

Con la fórmula que usamos, podemos establecer un punto (0, C) por donde pase la curva, y establecer las pendientes m₁ y m₂ en x₁ y x₂ respectivamente.  Aunque puede ser útil, esta manera de crear curvas es limitada.

Primero que nada, sólo podemos establecer un punto por donde queremos que pase la curva, y de ese punto sólo podemos establecer la coordenada Y, pues la coordenada X ya está establecida como 0.  Lo que nosotros queremos es poder establecer dos puntos, un punto inicial (x0, y0), y otro punto final (x3, y3) por donde pase la curva.

 

Las ecuaciones paramétricas

Otra desventaja de nuestra curva es que está dada como una función .  Una función es una relación en donde para cada valor x existe un único valor y.  Con una función podemos hacer curvas la que acabamos de hacer, o como estas:

Pues para cada valor x, hay un único valor y.

Ahora veamos estas curvas:

Estas curvas ya no son funciones, pues llega a existir más de un valor y para cada valor x.  Y si te fijas en la figura de la primera página, verás que un B-Spline llega a tener más de un valor y por cada valor x.  Aquí es donde las ecuaciones paramétricas nos son de gran utilidad.  Antes que nada.. ¿qué es una ecuación paramétrica?.  Las ecuaciones paramétricas se dan en pares, una para calcular la coordenada x y otra para calcular la coordenada y.  Las dos ecuaciones toman un solo parámetro t.  Aquí hay un ejemplo de un par de ecuaciones paramétricas:

Con estas ecuaciones se dibuja un círculo cuyo centro está en el origen y que tiene un radio de r.

Una de las ventajas de usar ecuaciones paramétricas es que se pueden trazar cualquier forma, y las dos ecuaciones siguen siendo funciones válidas.

Te estarás preguntando, ¿porqué usar ecuaciones paramétricas, si aún así se puede expresar una curva como la del círculo de la manera ?  Por ejemplo, podríamos usar esto en vez de las 2 ecuaciones paramétricas que acabamos de mostrar:

 

Hay 2 principales razones para no usar esto en vez de ecuaciones paramétricas.  Primero, como para cada x puede hacer mas de una y, sería difícil programar la computadora para que determine cuántas y hay, y que tenga que averiguar como calcular cada una de esas y.

La otra es, por la manera en que las ecuaciones paramétricas determinan una pendiente.

 

Rectas tangentes en ecuaciones paramétricas

Para conocer la pendiente de la línea o curva que definen un par de ecuaciones paramétricas, tenemos que usar algo de matemáticas.

Vamos a suponer que tenemos dos ecuaciones paramétricas: las cuales representan la misma curva que .

La función g(t) nos da una coordenada y al igual k(x).  Y k(x) requiere una x, la cual podemos obtener con f(t).

Entonces podemos establecer que:

Para encontrar la tangente, tenemos que derivar, y para derivar esto, aplicamos la regla de la cadena:

Despejamos k’(x) y obtenemos que:

 siempre que

 

El problema de la dirección de una recta tangente

Si observamos cuidadosamente la curva B-Spline, notaremos que las rectas formadas entre sus puntos de inicio y final con los puntos control no son simplemente tangentes a la curva en su punto de inicio y en su punto final.  Veamos de nuevo la curva:

 

En el punto P0, la curva tiene como tangente a la recta que va de P0 a P1, pero la curva tiene una dirección, podríamos decir que la curva “sale hacia P1”.  Al igual sucede en P3, la curva tiene como tangente a la recta que va de P2 a P3, y lleva una dirección “hacia P3”.

Esto de la dirección es muy importante.  La pendiente por sí sola sólo nos dice cual es el grado de inclinación, pero no nos dice su dirección.

Por ejemplo, aquí hay una recta cuya pendiente es 2:

Nosotros sabemos que la pendiente se calcula dividiendo la y entre la x, para poder así encontrar una relación, esta relación es la pendiente m:

Si nosotros conocemos la parte y y la parte x con la cual se obtiene la pendiente, entonces podemos saber cual es la dirección de la recta que tiene esa pendiente, si por ejemplo:

 

 

 

Entonces la recta tendría esta dirección:

Pero si:

Entonces la recta sería así:

La inclinación es la misma, pues , pero la dirección cambia.

Magnitud

Otra dato importante que podemos conocer si tenemos por separado la x y la y que con que se obtiene la pendiente, es la magnitud de la recta, al tener magnitud y dirección, entonces ya estamos hablando de un vector.

Por ejemplo, si:

, tendríamos un vector así:

Pero si  entonces tendríamos un vector así:

La pendiente es la misma, lo que cambia es la magnitud y la dirección, los cuales son datos muy importantes para nuestra curva B-Spline.

Veamos nuevamente la forma de calcular la tangente usando ecuaciones paramétricas:

Aquí vemos que g’(t) viene siendo nuestra componente y, y f’(t) es nuestra componente x.  Así que con ecuaciones paramétricas podemos determinar no sólo la pendiente (grado de inclinación) de la recta tangente, sino también su magnitud y dirección!

 

La curva B-Spline de un solo punto control.

Antes de intentar hacer ya directamente la fórmula de la curva B-Spline con sus 2 puntos control, vamos a hacer una curva parecida utilizando sólo un punto control.

 

Aquí está la curva que vamos a intentar hacer:

Como vemos aquí, vamos a encontrar una ecuación que nos dé una curva que empiece en el punto P0 y que en ese mismo punto tenga una pendiente de , y que termine en el punto P3.

 

El rango de t

Te habrás dado cuenta que las ecuaciones paramétricas toman un parámetro t, o sea que t es nuestra única variable independiente.  Teniendo un valor t podemos obtener la x y la y correspondientes, usando las 2 ecuaciones paramétricas.  La pregunta es, ¿qué valor le asignamos a t? ¿qué rango de valores puede tomar t?

El significado de t depende mucho de cómo estén formadas las ecuaciones paramétricas, por ejemplo, en la forma paramétrica del círculo, la t es un ángulo.

A veces t puede ser cualquier valor; como apenas vamos a definir un par de ecuaciones paramétricas, podemos simplemente establecer el rango que queramos.  Así que vamos a establecer que el rango de t es de 0 a 1, matemáticamente hablando:

Con esto queremos decir que cuando t = 0, las ecuaciones paramétricas nos van a dar el punto (x₀, y₀), y que cuando t = 1, entonces las ecuaciones paramétricas nos darán el punto (x₃, y₃).  En otras palabras, la curva se dibuja cuando los valores de t van del 0 al 1.

No voy a tratar de explicar por que utilizamos el rango [0, 1] como dominio de nuestras 2 funciones paramétricas, pudimos haber utilizado cualquier otro rango, pero a mi simplemente se me hacen el 0 y el 1 valores muy fáciles de manejar al estar simplificando las fórmulas.  ¿Para qué nos complicamos la vida definiendo un rango de [4.63, 32.567]?, sería una lata andar haciendo operaciones con esos valores.

 

Deduciendo la ecuación de la curva que tiene un punto control

Vamos a deducir un par de ecuaciones  que definan la curva que acabamos de poner al principio de esta página.

Empecemos por listar concretamente las características que debe cumplir esta curva:

La pendiente inicial será de e irá cambiando de tal manera que la curva llegue a pasar por el punto (x₃, y₃).

 

La pendiente de la pendiente

La pendiente de nuestra curva va a ir cambiando, es decir, va a tener una razón de cambio, esa razón de cambio es la pendiente de la pendiente.  La pendiente de la pendiente es lo que obtiene con la segunda derivada, obviamente.

 

Vamos a definir:

        siendo m la “pendiente” de la curva

       siendo p la “razón de cambio” de m.

 

Nosotros sabemos que cuando t = 0, entonces m = x₁ – x₀.

Aquí podemos definir un punto: (0, x₁ – x₀).  Considerando que p es una pendiente, entonces podemos definir una ecuación para m, utilizando la formula de la línea recta que se obtiene con un punto y una pendiente.  La ecuación de la línea recta usando un punto-pendiente es la siguiente:

En nuestro caso, la variable dependiente y viene siendo m,  p es la pendiente (m en la fórmula original), x es la variable independiente, o sea t, x₁ y y₁ definen el punto que conocemos, en este caso: (t = 0, m = x₁ – x₀).

Al sustituir los valores que queremos utilizar quedaría así:

Si quisiéramos conocer f(t) solo tenemos que integrar:

Como el valor inicial de f es x0, o sea, f(0) = x₀, entonces C = x₀ y la fórmula queda finalmente así:

Pero, ¿cuándo vale p?, pues a eso vamos precisamente, a despejar p:

Ahora es el momento de usar otra característica de nuestra curva:

Si sustituimos nos queda:

Ahora sí, por fin sabemos cuanto vale p.

Tomemos en cuenta que si:

Entonces:

Pero mejor hay que hacerlo por pasos:

Así que primero hay que obtener m:

Como dijimos, C es cuanto vale m cuando t = 0:

Ahora tenemos que sacar f(t):

En este caso, C es cuanto vale f(0), y eso, según las características que listamos al principio:

 

Por lo tanto:

Las características para la función g(t) son exactamente iguales a la función f(t), lo único que cambia es que g(t) es para la coordenada Y.  Por lo tanto función g(t) quedaría así:

 

Ahora sí, cuando usemos estas funciones para t con valores del 0 al 1, obtendremos la curva B-Spline de un solo punto control que se presentó anteriormente.  Recuerda que la función f(t) calcula la coordenada X, y la función g(t) calcula la coordenada Y.

 

Primer intento de deducir la fórmula del B-Spline de 2 puntos control

 

Veamos nuevamente el B-Spline del cual queremos encontrar la fórmula:

 

A diferencia del Spline del cual obtuvimos la fórmula anteriormente, aquí tenemos un segundo punto control.  Eso significa que nosotros estamos especificando en donde queremos que empiece la curva, en donde queremos que termine la curva, y cual será la pendiente en cada uno de esos 2 puntos, no sólo en uno de ellos.

 

Vamos a utilizar nuevamente un rango para t de 0 a 1.  Tomando esto en cuenta, trataremos de listar aquellas características o condiciones que deben cumplir las ecuaciones paramétricas de esta curva:

 

 

Las características de g(t) son las mismas que f(t), sólo cambia la coordenada a la que se refieren.  Así que solo tenemos que encontrar la fórmula de una de las funciones y la utilizamos para la otra función (sustituyendo la coordenada correspondiente).

 

Concavidad hacia arriba, concavidad hacia abajo y puntos de inflexión

Al deducir la fórmula del Spline de un solo punto control, estábamos considerando a p una constante.  De hecho, si p no hubiera sido una constante, no hubiéramos podido integrarla y obtener la fórmula final.  Nosotros dijimos que p = f’’(t), eso significa que p es la segunda derivada de la función paramétrica.  Ahora, hay algo importante que notar cuando decimos que la segunda derivada de nuestra función es una constante.

 

Examinemos la siguientes curvas:

Las líneas verdes son las rectas tangentes de la curva en diferentes puntos, conforme la curva avanza, estas tangentes aumentan de valor, en otra palabra podría decirse, que “van girando hacia la izquierda”, aunque el aumento de la pendiente tiene sus limitaciones, por ejemplo, en las 2 curvas que se muestran arriba, la tangente seguirá aumentando, pero por más que aumente, nunca llegará ni pasará de los 90°, de hecho, la tangente de 90° es infinito.  Cuando la tangente va en aumento, se dice que la función tiene concavidad hacia arriba.  Si decimos que hay concavidad hacia arriba cuando la pendiente va en aumento, entonces, la razón de cambio de la pendiente debe ser positiva, matemáticamente hablando:

Si la función de estas curvas es f y la posición x donde la curva debe ser cóncava hacia arriba es c, entonces:

 

Ahora examinemos las siguientes curvas:

 

Aquí cambió la cosa, ahora la recta tangente está “girando hacia la derecha”, eso significa que la pendiente va disminuyendo.  Entonces decimos que estas curvas son “cóncavas hacia abajo”.  Por lo tanto, si la pendiente va disminuyendo, entonces la razón de cambio de la pendiente debe ser negativa:

En cualquiera de los dos casos anteriores, el de concavidad hacia arriba y del de concavidad hacia abajo, la segunda derivada de f puede ser un valor constante.  Pero ahora examinemos la siguiente curva:

Es la misma curva B-Spline que ya llevo como 4 veces que la repito, pero aquí marqué un punto especial, un punto de inflexión.  El punto de inflexión es donde la pendiente cambia de dirección.  En el caso de arriba, la pendiente deja de disminuir y empieza a aumentar.

Aunque no todas la curvas B-Spline tengan un punto de inflexión, es importante tomar en cuenta las consecuencias de que pueda existir este punto de inflexión.

 

En el punto de inflexión de esta curva B-Spline, la pendiente va a dejar de disminuir para empezar aumentar, eso significa que la razón de cambio de la pendiente, o sea, la segunda derivada de la función de esta curva, va a cambiar de signo, de negativo, a positivo, por lo tanto la razón de cambio de la pendiente (a la cual hemos estado llamando p), no puede ser una constante.

 

La pendiente de la pendiente de la pendiente

Cuando algo no es constante, es porque tiene una razón de cambio, o una pendiente.  Si acabamos de confirmar que la f’’(t) y g’’(t) no son constantes, pues en cierto momento pasan de un valor positivo a un valor negativo, por lo tanto deben tener alguna razón de cambio que los haga cambiar, valga la redundancia, eso vendría siendo la pendiente de la pendiente de la pendiente, para simplificarnos la cosa, vamos a llamarle s.

 

 

Ahora sí, podemos empezar a deducir las ecuaciones paramétricas del B-Spline.  Agárrense por que aquí viene lo bueno.  Aquí van de nuevo las condiciones que deben reunir nuestras ecuaciones paramétricas:

Nosotros no tenemos idea de cuanto vale s, entonces tenemos que encontrar su valor.  Primero, empecemos por definir p:

Ahora tenemos a p en términos de s, pero ahora tenemos una C que nos está dando lata, y tampoco sabemos cuanto vale.  Aún así, podemos integrar de nuevo para encontrar m:

Cuidado con la C, esa C es la que obtuvimos originalmente al integrar p, también hay que notar que agregué directamente el x₁ + x₀ (pues f’(0) = x₁ + x₀ )  en lugar de poner otra C, para que no se confundiera con la C que ya estaba ahí.

Ahora hay que integrar m para obtener f(t), aquí voy a agregar el x₀ (pues f(0) = x₀ ) directamente en lugar de poner otra C.

Ahora tomemos la siguiente característica para formular una ecuación:

Como m = f’(t), entonces podemos tomamos la fórmula de m para establecer que:

Tomemos también en cuenta la siguiente característica:

Si sustituimos en la fórmula obtenida para f(t), entonces tenemos que:

Las últimas 2 ecuaciones que acabamos de hacer, forman un sistema de ecuaciones, si las resolvemos, podremos conocer el valor de s y el valor de C.  Aquí esta nuestro sistema de ecuaciones:

1. 
2. 

 

Empecemos por despejar C en la 1:

Ahora sustituimos en la 2:

multiplicamos todo por 12:

Ahora hay que obtener C:

Ahora que tenemos a s y a C en términos de los puntos que definen la curva, podemos integrar hasta obtener f(t).

Primero tenemos que obtener p:

Esa C es precisamente la que acabamos de despejar, así que sustituimos la C y nos queda:

Ahora hay que obtener m (la pendiente, o sea f’(t)), ya sabemos que al integrar, le agregamos al final la pendiente inicial que es:

Ahora sí, a integrar para obtener m:

Finalmente integramos m para obtener f(t):

Podemos simplificar:

Igualmente definimos a g(t):

 

 

 

 

El problema de la fuerza de atracción de los puntos control

 

Veamos las fórmulas obtenidas para nuestra curva B-Spline:

 

Ahora veamos las condiciones que definimos que debían tener estas fórmulas:

 

Si nos ponemos a comprobarlas nos daremos cuenta de que efectivamente las ecuaciones que obtuvimos cumplen con estas condiciones.  Pero, sucede que al utilizar estas fórmulas para crear una curva B-Spline, la curva se ve así:

 

Esta curva es efectivamente un B-Spline del tipo que queríamos obtener, pero si la comparamos con el B-Spline que aparece en la primera página, nos daremos cuenta de que algo anda mal.  Sucede que a los puntos control, les falta algo de fuerza de atracción, la curva debería verse más “atraída” hacia los puntos control.

 

Para solucionar esto, tenemos que analizar que es lo que hace que la curva se vea atraída hacia los puntos control.  Hay dos características que establecimos que debían tener cada una de las ecuaciones paramétricas de nuestra curva:

          

 

Al estar nosotros especificando la derivada de f y la derivada de g, estamos estableciendo no sólo una pendiente, sino una dirección y una magnitud.  Esto de la magnitud es muy importante, pues es la que determina que tanto se va a ser atraía la curva.

 

Si nosotros no estuviéramos utilizando ecuaciones paramétricas, daría igual si establecemos que en un punto debe haber una pendiente de  a que estableciéramos una de , pero como estamos utilizando ecuaciones paramétricas, cada elemento de la fracción es la derivada de una de las ecuaciones; el numerador es la derivada de la función g(t) y el denominador es la derivada de f(t), esto nos permite establecer una magnitud.

 

Ahora bien, esto significa que si queremos que los puntos control atraigan mas a la curva, debemos aumentar los valores que establecimos para f’(0), f’(1), g’(0) y g’(1).  A mí se me ocurrió triplicar el valor original, de manera que:

           

 

En este momento te has de estar preguntando ¿y a este tipo que le pasa? ¿qué es eso de “se me ocurrió”? ¿y por que lo multiplica por 3, por que no por 2 o por 4?

Lo que sucede aquí es que el 3 es el número que nos da la curva B-Spline como debe ser, básicamente, aquí solo es cosa de “atinarle”, pudimos haber usado un 2, o un 4, etc.  Pero la curva no nos hubiera quedado como debe ser.  La única explicación que puedo dar aquí es que necesitamos de alguna manera aumentar el valor de las derivadas para lograr una mayor atracción de la curva por parte de los puntos control.  Más adelante daré una pequeña explicación más matemática de porqué se utilizó el 3 (aunque no lo demostraré con fórmulas).

 

Ya que redefinimos las nuevas derivadas, hay que volver a sacar las 2 ecuaciones paramétricas.  Retomemos las fórmulas con que empezamos a deducir la fórmula del B-Spline anterior:

El (x₁, x₀) tienen que ser reemplazados por la nueva derivada, las fórmulas quedaría así:

Ahora tomando en cuenta la siguiente condición de nuestra curva:

Podemos formular la siguiente ecuación:

Y utilizando esta condición:

Podemos formular esta otra ecuación:

Así tenemos un sistema de ecuaciones:

1. 
2. 

 

Despejamos C en 1:

Sustituimos C en 2:

Multiplicamos todo por 6:

Pasamos las s a la izquierda:

Multiplicamos todo por 2

Ahora hay que sacar la C:

Ahora sí, ya que tenemos s, podemos ir integrando hasta obtener f(t)

Para poder resolver esto más fácilmente, nos vamos por pasos, primero a sacar p:

Sustituimos la C:

Ahora hay que obtener m:

Lo que agregué en el paréntesis es la pendiente inicial, según la condición

Simplificamos:

Ahora hay que sacar f(t):

El x₀ que agregué es la coordenada del punto inicial.

Seguimos simplificando:

Y esta misma fórmula la pasamos a g(t):

Violá!, ya tenemos nuestras 2 fórmulas paramétricas de la curva B-Spline.  Estas son las que producen curvas como la que se muestra en la primera página.  Créeme, si quieres compruébalo tú mismo y verás.

 

La fórmula original de Bézier:

Ok ok, yo sé que me vi muy mal al simplemente multiplicar por 3 las pendientes iniciales y finales sin dar ninguna explicación “matemáticamente rigurosa”, pero en fin, funcionó, y la razón que di fue suficientemente lógica.  Sin embargo, para aquellos que no estén conformes con esto, y que sean unos genios de las matemáticas, aquí les va la fórmula original para una curva Bézier:

      para valores de t del 0 al 1.

La P_i es el punto.  P₀ es el punto inicial, y P_n es el punto final, todos los demás puntos entre el 1 y el n-1 son los puntos control.

Ah verdad?, a ver si le entiendes…

Bueno bueno, esa  se refiere al polinomio de Bernstein, y pues sí, aquí va:

Donde  es el coeficiente binomial:

La “!” indica factorial, ya si no sabes que es el factorial, estás muy perdido, ve y búscalo en un libro de matemáticas.

 

Para deducir esta fórmula se utilizaron todos las condiciones que nosotros establecimos para deducir nuestra propia fórmula, sólo que Bézier y Bernstein, utilizaron otra condición que nosotros no especificamos.  Ellos pusieron como condición, que la curva siempre iba a quedar dentro de un convex hull.  El convex hull es un polígono de 4 lados que se forma al unir los puntos control y los puntos inicial y final; la curva siempre quedará dentro de este polígono.

 

Otra característica que se estableció es que ninguna línea puede tener más intersecciones con una curva Bézier que con la curva obtenida al juntar puntos consecutivos con líneas rectas.  Esta característica de la curva indica que la variación de la curva no es mucha.

 

La más importante característica es que se encuentra dentro de un convex hull.  El problema es que los cálculos que se tienen que hacer para definir un convex hull son súper complejos, y muy probablemente hubiéramos tardado más en hacer los cálculos del convex hull que en atinarle al 3 por el cual teníamos que multiplicar las pendientes.  Si hubiéramos usado un número mayor que el 3, no pasa de que la curva se salga de su convex hull.

 

Bueno, de una manera u otra, la fórmula obtenida es la misma.  Para terminar, voy a poner las ecuaciones finales que definen a una curva Bézier de 2 puntos control (un B-Spline):

 

 

¿Cómo hacer las torres de Hanoi

en Visual Basic?

 

Rafael Nieto Yosten

 

Debido a la gran demanda de programas que hagan las torres de Hanoi, decidí hacer esta pequeña guía(para tumbaburros), para hacer un programa que permita manejar, resolver y desplegar las torres de Hanoi en Visual Basic.

 

Primero que nada, las torres de Hanoi consisten en tres “torres” donde se supone que colocamos aros, cada aro tiene diferente tamaño.  El juego empieza teniendo todos los aros en la primer torre.  El aro mas grande esta hasta mero abajo, y el mas pequeño está hasta mero arriba.  El objetivo del juego es pasar todos los aros desde la torre que esté mas a la izquierda, hasta la torres que esté mas a la derecha.  Pero hay ciertas reglas:

 

• Solo se puede mover un aro a la vez
• Nunca, pero nunca, se puede colocar un aro mas grande sobre otro mas pequeño.

 

Ciertamente, para nuestras cabezas es difícil pensar si no tememos una imagen gráfica de que es lo que estamos hablando.  Así que lo pondré así: la manera en que nos estamos imaginando a las torres de Hanoi en Visual Basic sería mas o menos así:

 

 

Las torres las simulamos con 3 objetos line verticales.  Y los aros vienen siendo objetos shape.  La linea de abajo no es tan importante, sólo es un line horizontal para simular la base de las torres.

 

Los numeros que están dentro de cada shape no aparecen realmente en Visual Basic, se los puse yo para poder identificar a cada aro.  El aro mas pequeño le dí el numero 1, y el aro mas grande le di en numero 5.  Con esto quiero, indicar que esos cinco aros, son una matriz de controles, y el índice para el aro mas pequeño es el 1 y el índice del aro mas grande es el 5.

Así como la llevamos, debemos tener los siguientes objetos en nuestro formulario:

 

Tipo	Nombre	Descripción
Line	LineaVer(1)	La línea vertical de la primera torre
Line	LineaVer(2)	La línea vertical de la segunda torre
Line	LineaVer(3)	La línea vertical de la tercera torre
Line	LineaBase	La línea que sirve de base para las 3 torres
Shape	ShpAro(1)	El aro mas chiquito (el blanco)
Shape	ShpAro(2)	El aro que sigue en chiquito (el rojo)
Shape	ShpAro(3)	El aro verde
Shape	ShpAro(4)	El aro azul
Shape	ShpAro(5)	El aro mas grande (el amarillo)

 

 

En el formulario tenemos 5 aros representados con objetos shape.  Que información útil tenemos de cada shape?.. pues tenemos las coordenadas de la esquina superior izquierda de cada shape: las propiedades left y top nos dan estas coordenadas., pero que diablos hago con estas coordenadas?, que tal si yo quiero mover un aro de la torre 1 a la torre 2?, como sé que aro mover, y a qué coordenadas moverlo..? mas aún, cómo se si es válido hacer tal movimiento? (recuerda: las reglas del juego…).  Ok, ok, se que tienes ganas de llorar, pero no lo hagas todavía.. espera, todavía hay esperanza.

 

Mira, el chiste es este: si tratas de pensar como vas a jugar con las coordenadas de estos objetos gráficos, estas completamente perdido, pues estas lidiando directamente con el aspecto gráfico del programa, y todos sabemos que manejar una interfaz gráfica es un dolor en el trasero!.. así que para que complicarse?, la clave esta en que no tienes que concentrarte tanto en el aspecto grafico; sino que tienes que manejar el asunto de manera abstracta, y utilizar una estructura de datos que te permita fácilmente lidiar con estas torres y sus mentados aros.

 

Así que olvida completamente el formulario, y esos shapes y todo el rollo aquél.  Piensa ahora abstractamente.  Tienes 5 aros…, pero aro es demasiado concreto para una computadora.. recuerda, la computadora solo puede pensar en 0s y 1s, y tu le pides que piense en aros?.. a la compu no le vas a decir: muéveme este aro de aquí para acá: Tú eres el que tiene que sufrir!.  Entonces pues, en lugar de pensar que tienes cinco aros, tienes que pensar en los aros, como si fueran números.  El numero 1 corresponde a tu aro mas chiquito, y el numero 5 corresponde a tu aro mas grande.  Y como vas a acomodar estos cinco números en las torres?.. pues que mejor que una matriz!.. digamos, una matriz bidimensional que mida 3 x 5.  (3 torres x 5 espacios).

 

La tentación de todo mundo sería declarar la matriz de esta forma:

 

Dim torres(1 to 3, 4) as aro

 

Pero no!, recuerda, no estamos manejando aros.. sino números, asi que la manera correcta de declarar la matriz sería así:

 

Dim torres(1 to 3, 4) as integer

 

Una matriz de 2 dimensiones, es simplemente una tabla:

 

        

torres
	1	2	3
0	5	0	0
1	4	0	0
2	3	0	0
3	2	0	0
4	1	0	0

 

Los números en negrita son los índices.  Por ejemplo torres(1,0) es igual a 5, por que si vemos la columna 1, en la fila 0, hay un 5.

 

La correspondiente representación grafica de esta matriz sería así:

 

 

Esos numeritos: 0, 1, 2, 3 y 4 al nivel de cada aro son los índices para cada “posición”.

Y los números 1, 2 y 3 arriba de cada torre, son los índices de cada torre.

 

1. En la torre 1, en la posición 0, está el aro 5.
2. En la torre 1, en la posición 3, está el aro 2.
3. En la torre 2, en la posición 0, no hay aro!
4. En la torre 3, en la posición 4, tampoco hay aro!.
5. En la torre 1, en la posición 4, está el aro 1.

 

Bueno, pues esto es lo que almacenamos en la matriz torres.  Expresando los 5 enunciados anteriores ya en términos mas específicos de código diríamos:

 

1. torres(1, 0) = 5
2. torres(1, 3) = 2
3. torres(2, 0) = 0
4. torres(3, 4) = 0
5. torres(1, 4) = 1

 

Ahora, pues, nuestro código tiene que estar enfocado a manejar los números dentro de esta matriz, pero antes de empezar, sucede que necesitamos un dato mas: cuantos aros hay en cada torre. ¿por qué?, pues simple, en programación, llevar la cuenta de objetos siempre es una técnica muy recurrida pues puede servir muchas cosas, y sobre todo para la validación.  He aquí lo que podemos hacer si tenemos el dato de cuantos aros hay en cada torre:

 

• Podemos saber cuando una torre está vacía (no tiene aros).  Esto significa que, en caso de querer mover un aro a esta torre, no hay que hacer ninguna validación adicional, pues la torre no tiene ningún aro aún, por lo tanto, podemos meter ahí cualquier aro sin importar su tamaño.  También significa que, en caso de querer sacar un aro de esa torre, no podemos, pues no hay ningún aro en esa torre, y podemos informarle eso al usuario.
• Podemos saber cuál es el aro que esta a mero arriba en una torre (si es que la torre no esta vacía)
• Podemos saber cuál es el siguiente espacio disponible para colocar un aro en una torre.

 

Como no necesitamos saber cuantos aros hay en un solo una torre, sino, en cada una de las 3 torres.  Vamos a crear un pequeño arreglo que almacene la cuenta de aros para cada torre, la declaración sería así:

 

Dim nAros(1 to 3) as integer

 

Asi pues, nAros(1) me dice cuantos aros tengo en la torre 1, nAros(2) me dice cuantos aros tengo en la torre 2.. etc.  Veamos como quedarían las matrices torres y nAros, inicialmente:

 

torres
	1	2	3
0	5	0	0
1	4	0	0
2	3	0	0
3	2	0	0
4	1	0	0

 

nAros
1	2	3
5	0	0

 

En la torre 1 tenemos 5 aros, en la torre 2, 0 aros, y en la torre 3, 0 aros también.

Ok, yo dije que teniendo esta información, yo podía saber cual es el aro mas arriba en una torre y cual es el siguiente espacio disponible para colocar un aro en una torre, veamos como: supongamos que tenemos nuestros aros así:

 

 

Las información correspondiente en las matrices sería así:

 

torres
	1	2	3
0	3	4	5
1	1	0	2
2	0	0	0
3	0	0	0
4	0	0	0

 

nAros
1	2	3
2	1	2

 

Para saber cuál, aro esta a mero arriba, necesitamos saber la posición del aro mas arriba, y esta posición corresponde al numero de aros que hay en esa torre – 1.  Mas especifico:

Posición del aro mas arriba en la torre n = nAros(n) – 1

Numero del aro mas arriba de la torre n = torres(n, nAros(n) – 1)

 

Por ejemplo, el numero de aros de la torre 1 es = nAros(1) = 2, la posición del aro mas alto es la posición 1, o sea nAros(1) – 1 = 2 – 1 = 1.

 

Ahora, para saber la posición del siguiente espacio libre en una torre (el espacio que está justamente arriba del espacio ocupado por el aro mas arriba de una torre), simplemente utilizamos el numero de aros de esa torre como posición:

 

Posición del siguiente espacio disponible en la torre n = nAros(n)

Siguiente espacio disponible en la torre n = torres(n, nAros(n))

Y sí, ciertamente la siguiente posición disponible en la torre 1, es la posición 2; en la torre 2, es la posición 1, y en la torre 3, es la posición 2.

 

Ahora pues, empecemos a hacer nuestra primera operación con las matrices torres y nAros: Inicializarlas.

Necesitamos una función que nos deje a estas matrices tal y como están en la pagina 4.  Aquí esta esa función:

 

Sub InicializarTorres()

      Dim i as integer

      Erase torres

      For i = 0 to 4

            torres(0, i) = 5 – i

      Next i

      nAros(0) = 5

      nAros(1) = 0

      nAros(2) = 0

End Sub

 

Ahora, necesitamos una función que mueva un aro de una torre a otra torre.  Esta función va a tomar el aro que está mas arriba en la torre origen y lo va a colocar en la siguiente posición disponible en la torre destino.

 

Sub MoverAro(ByVal origen as Integer, ByVal destino as Integer)

torres(destino, nAros(destino)) = torres(origen, nAros(origen) – 1)

      torres(origen, nAros(origen) – 1) = 0

      nAros(origen) = nAros(origen) – 1

      nAros(destino) = nAros(destino) + 1

End Sub

 

En la primera línea, tomo el aro que esta mas arriba en la torre origen, y lo asigno a la siguiente posición disponible en la torre destino.

En la segunda línea, borro el aro que acabo de copiar de la torre origen. (si no la borro, voy a tener 2 aros repetidos, y eso no es lo que quiero).  Para borrarla, solo le asigno un 0, como no hay ningún aro que tenga el número 0, entonces ya sé que cuando vea un 0, significa que no hay ningún aro ahí.

 

En las 2 últimas líneas, actualizo mis contadores.  Al la cuenta de aros en el origen le resto 1, y a la cuenta de aros en el destino le sumo 1.  Si en la torre origen tenía 4 aros y en la torre destino tengo 1 aro, entonces después de mover el aro, en la torre origen voy a tener 3 aros y en la destino 2 aros.

 

Ahora, a esta función le falta algo: validación!. Oh Si!..  Resulta que no siempre puedo mover un aro de una torre a otra torre.  Si la torre origen no tiene aros, entonces no puedo mover nada.  Y si la torre destino tiene en su aro mas alto, un aro mas pequeño que el aro que quiero ponerle, tampoco puedo hacer el movimiento.  Así que la función ya con validación quedaría así:

 

Sub MoverAro(ByVal origen as Integer, ByVal destino as Integer)

      If nAros(origen) = 0 then Exit Sub

      If nAros(destino) <> 0 then

            If torres(destino, nAros(destino) – 1) < _

               torres(origen, nAros(origen) – 1) then

                  Exit Sub

            End If

      End If

torres(destino, nAros(destino) = torres(origen, nAros(origen) – 1)

      torres(origen, nAros(origen) – 1) = 0

      nAros(origen) = nAros(origen) – 1

      nAros(destino) = nAros(destino) + 1

End Sub

 

Bueno, ahora estarás diciendo, bueno, que bonito que se mueven los numeritos dentro de las matrices, pero ahora quiero que se vea!.. ok ok, a eso iba.  Lo que tu necesitas es una función que te permita hacer realidad tus sueños.  Bueno, mas bien, una función que acomode tus shapes (que simulan aros), en las coordenadas apropiadas de acuerdo a la información que tienes en tus matrices de torres y nAros.

 

Las coordenadas se pueden calcular fácilmente si tu conoces en que torre, en que posición, y que aro quieres colocar.

Lo que haces al calcular las coordenadas es centrar el aro en la torre.  El centro está dado por la propiedad X1 o X2 de el objeto lineaVer.. recuerdas?.

Vamos a darle un vistazo a la declaración de la función que calcula las coordenadas:

 

Private Function CalcCoord(nTorre as Integer, pos as Integer, nAro as integer) as TPoint

 

Que es ese TPoint?.. es un type que almacena las coordenadas de un punto. Aquí está la el código para la declaración del TPoint:

 

Private Type TPoint

         X as Integer

         Y as Integer

End Type

 

Esta declaración la pones arriba en el general.

Ahora si, el código para calcular la coordenada sería así:

 

Private Function CalcCoord(ByVal nTorre as Integer, ByVal pos as Integer, ByVal nAro as integer) as TPoint

 

      CalcCoord.X = lineaVer(nTorre).X1 – (shpAro(nAro).Width / 2)

      CalcCoord.Y = lineaVer(nTorre).Y2 – (pos + 1) * shpAro(1).Height

End Function

 

Para que este código funcione, tuviste que haber dibujado las líneas verticales de arriba hacia abajo.. así como lo oyes.. de arriba hacia abajo.  Así, propiedad Y1 es la coordenada superior, y la propiedad Y2 es la coordenada inferior.

 

Teniendo esta función de CalcCoord, ya podemos hacer la función que acomode nuestros aros de acuerdo a la info en las matrices.  Iteramos por la matriz, y cuando hallamos un aro, calculamos sus coordenadas, y lo movemos a esas coordenadas.  Para ya no hacer mas bla bla bla.. aquí está el código:

Sub AcomodarAros()

      Dim i, j as Integer

      Dim p as TPoint

      For i = 1 to 3

            For j = 0 to 4

                  If torres(i, j) <> 0 then

                        p = CalcCoord(i, j, torres(i, j))

                        shpAro(torres(i, j)).Move p.X, p.Y

                  End If

            Next j

      Next i

End Sub

 

Estos 2 ciclos for anidados sirven para ir iterando por toda la matriz de torres, lo que hacemos en cada iteración es buscar los aros.  Cuando encontramos un aro (o sea que torres(i, j) <> 0), entonces calculamos las coordenadas para ese aro (el numero del aro está dado por torres(i, j)) en la torre i en la posición j.  Las coordenadas quedan almacenadas en la variable p (que es un TPoint).  Lo que hacemos después es mover el shape correspondiente a las coordenadas almacenadas en p (p.X y p.Y).  El shpAro que vamos a mover está dado por torres(i, j), es por eso que utilizamos esta expresión como índice de shpAro.

 

Arrastrando los Aros con el mouse

 

Y hora que?.. los puedo escuchar como lloran. Waa waa.. , quiero que pueda arrastrar los aros de una torre a la otra torre!!!.  Bueno, ustedes lo pidieron, van a tener que escribir otro buen pedazote de código! Eh!.

 

El proceso de arrastrar un aro de una torre a otra torre consiste en los siguientes pasos:

 

1. El usuario da clic con el mouse a un aro, el programa detecta el clic y detecta en cual aro se dio clic, además, valida si se puede “agarrar” ese aro.
2. El usuario (con el botón del mouse aún aplanado), mueve el mouse.  El programa va moviendo el aro conforme el usuario mueve el mouse.
3. El usuario “suelta” el botón del mouse, el programa recibe un evento “MouseUp”, y detecta si las coordenadas donde soltó el mouse, corresponden al “bounding rectangle” de una torre.  Si así es, entonces checa si es válido soltar el aro en esa torre.  Si así es, entonces realiza el movimiento internamente en las matrices.
4. Al final, el programa refleja los cambios hechos internamente en la matriz llamando al procedimiento AcomodarAros

 

Primero, hay que definir algunas estructuras de datos que representan objetos básicos en geometría.. recuerdas el día en que te dijeron que todo eso que te metían en la escuela de geometría analítica te iba a servir para algo?, bueno si tuviste fe, pronto serás salvado., pero si no, ya puedes empezar a llorar de nuevo.

 

Bueno, primero que nada, el sistema de coordenadas de una PC está asi:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Las Y incrementan hacia abajo y disminuyen hacia arriba.  Las X funcionan igual: aumentan hacia la derecha y disminuyen hacia a la izquierda

 

Ahora, necesitamos una estructura que nos defina un rectángulo:

 

Type TRect

(left, top)

         left as Integer

         top as Integer

         right as Integer

         bottom as Integer

End Type

 

 

 

 

 

 

 

 

Las coordenadas (left, top) nos dan el punto que está en la esquina superior izquierda del rectángulo.  Las coordenadas (right, bottom) nos dan el punto que está en la esquina inferior derecha del rectángulo.

 

Por convención, se dice que un rectángulo no incluye a sus lados right y bottom.  Esto se utiliza para saber como determinar si un punto se encuentra dentro de un rectángulo.  Un punto que esté en el lado left o el lado top, o dentro de cualquiera de los 4 lados, se dice que está dentro del rectángulo.  Un punto que se encuentre sobre el lado right, o el lado bottom, se le considera fuera del rectángulo.

 

Asi que ya estamos listos para hacer una función que nos diga si un punto está dentro de un rectángulo:

Private Function IsPointInRect(ByVal p as TPoint, ByVal r as TRect) as Boolean

 

      If (p.X >= r.left and p.X < r.right and _

          p.Y >= r.top and p.Y < r.bottom) then

            IsPointInRect = True

      Else

            IsPointInRect = False

      End If

End Function

 

Esta función toma como parámetros un punto (p) y un rectángulo (r).  Y devuelve True si p está dentro de r, y False en caso de que no.

 

Antes de empezar a escribir algo de código en el MouseDown, necesitamos una función que nos diga si un aro está a mero arriba de una torre.  Por ejemplo.. el usuario hace clic al aro 3.. entonces yo quiero saber si el aro 3 está a mero arriba en una de las torres.  Tengo 3 torres, y cada torre (si no está vacía), tiene un aro a mero arriba, lo único que tengo que checar, es si esa torre es la torre que estoy buscando.

 

Aquí esta la función:

 

Private Function EstaArriba(ByVal n as Integer) as Integer

      Dim i as Integer

      For i = 1 to 3

            If nAros(i) <> 0 then

                  If torres(i, nAros(i)) = n then

                        EstaArriba = True

                        Exit Function

                  End If

            End If

      Next i

End Function

 

Esta función nos sirve porque el usuario solo debe de poder agarrar el aro que esté mas arriba en una torre, y debemos checar si el aro que se está intentando agarrar es efectivamente un aro de los que están arriba.

 

Ahora si, ya podemos empezar a escribir código para el evento MouseDown, y detectar, si el punto donde se hizo clic, está dentro del rectángulo que define a uno de nuestros shapes.

 

Necesitamos además una variable donde almacenar que aro es el que el usuario está “arrastrando”, si es que el usuario hizo clic a uno de los shapes.

Asi que declara esta variable en el general:

 

Dim aroAgarrado as Integer

 

También hay que inicializarlo a –1, por eso, agrega esta línea al Form_Load:

 

AroAgarrado = -1

 

También declara las siguientes variables en el general:

Dim offx, offy as Integer

 

 

Mas adelante explico que onda con el offx y el offy.

Ahora escribe algo de código para el MouseDown:

 

Private Sub Form_MouseDown(Button As Integer, Shift As Integer, X As Single, Y As Single)

 

      Dim i as Integer

Dim p as TPoint

Dim r as TRect

      p.X = X

      p.Y = Y

      For i = 1 to 5

            r.left = shpAro(i).left

            r.top = shpAro(i).top

            r.right = shpAro(i).left + shpAro(i).Width

            r.bottom = shpAro(i).top + shpAro(i).Height

            If EstaArriba(i) and IsPointInRect(p, r) then

                  aroAgarrado = i

                  offx = p.X – r.left

                  offy = p.Y – r.top

                  Exit Sub

            End If

      Next i

End Sub

 

En las primeras líneas, declaro un iterador (i), un punto (p), y un rectángulo (r), también lleno mi variable p con las coordenadas donde dio clic el usuario.

Luego empiezo un ciclo for, en este ciclo voy a checar si el usuario dio clic a uno de mis 5 shapes que simulan aros.  El for va checar aro por aro, desde el primer aro hasta el quinto aro, a ver si el punto p (el punto donde se dio clic) está dentro del rectángulo que encierra a esos aros.  Las primeras líneas dentro del ciclo for llenan los datos para el rectángulo que encierra al shape del aro (r).  Notarás que la sentencia If tiene 2 condiciones.  Una condición checa si el punto p esta dentro del rectángulo r., y la otra checa si el aro numero i es uno de los aros mas arriba en una torre.  Esto se logra llamando a las funciones que previamente escribimos: EstaArriba, y IsPointInRect.

 

Offx y offy vienen a ser mi “offset”, o sea la distancia que hay desde la esquina superior izquierda del shape, hasta el punto donde yo di clic.  Gráficamente:

 

 

 

 

 

 

 

 

 

 

 

 

Imagina que el rectángulo ese es el rectángulo de un shape de uno de los aros, también imagina que esa flechita es el mouse que está dando clic en ese punto.

Y para que necesito estos offx y offy?., pues sucede que el evento MouseMove, me da las coordenadas del mouse, pero si estoy arrastrando el shape de un aro, necesito conocer las coordenadas de la esquina superior izquierda de ese shape, y para calcularlas, simplemente le resto el offx y el offy al punto que me da el evento MouseMove.  Aquí esta el código que lo hace:

 

Private Sub Form_MouseMove(Button As Integer, Shift As Integer, X As Single, Y As Single)

 

      If aroAgarrado > 0 then

            ShpAro(aroAgarrado).Move X – offx, Y – offy

      End If

End Sub

 

Si te acuerdas, al cargar el formulario aroAgarrado vale –1, eso significa que no hay ningún aro agarrado.  Así, cuando se generen los eventos de MouseMove, éste evento no va a mover ningún aro.

Cuando el usuario “agarra” un aro, entonces aroAgarrado va a tener el numero del aro que esta arrastrando, y ciertamente, el evento MouseMove se va a encargar de ir cambiando las coordenadas del shape correspondiente.

 

Ahora, nos falta la parte mas bonita de todas… cuando suelta el aro.  ¡Ahora si!,  se que estas llorando, pero… no te preocupes, esto va paso por paso, pronto saldrá.

 

Cuando el usuario “suelta” el clic del mouse, se genera el evento MouseUp.  Es en este evento en que tienes que meter mano para ver en que torre se soltó el aro agarrado (si es que el usuario tiene agarrado un aro).

 

A la hora de soltar el aro, tenemos que checar si el usuario soltó el aro en uno de los siguientes rectángulos:

 

 

El procedimiento del MouseUp se resume en los siguientes pasos:

 

1. Primero, checar si se esta agarrando un aro, sino, salir.
2. Luego, generar una variable tipo TRect para cada uno de los rectángulos que encapsulan a cada torre.
3. Checar si las coordenadas del punto donde se “soltó” el puntero, están dentro de uno de los rectángulos.
4. Hacer el movimiento llamando a MoverAro

 

Aquí está el código mas o menos:

 

Private Sub Form_MouseUp(Button As Integer, Shift As Integer, X As Single, Y As Single)

 

Dim i as Integer

Dim p as TPoint

Dim r as TRect

     

      p.X = X

      p.Y = Y

      r.top = lineaVer(0).Y1

      r.bottom = lineaVer(0).Y2

      For i = 1 to 3

            r.left = lineaVer.X1 + (lineaVer(1).X1 – lineaVer(0).X1) * _

   (i + 0.5)

            r.right = r.left + lineaVer(1).X1 – lineaVer(0).X1

            If IsPointInRect(p, r) then

                  Call MoverAro(BuscarAro(aroAgarrado), i)

            End If

      Next i

      aroAgarrado = -1

      Call AcomodarAros

End Sub

 

En las primeras líneas declaramos un iterador (i).  Un punto (p) y un rectángulo (r).  Justo después, asignamos la X y la Y que recibimos del evento y los almacenamos en p.  Asignamos el top y el bottom, de r pues siempre tienen el mismo valor.

Luego en cada iteración de i, calculamos el left y el right de r, pues son los que cambian, dependiendo de la torre.  Para que las formulas funcionen, cada torre tiene que tener la misma distancia entre si.  Trata de echarle coco para entender las fórmulas, ya verás por qué.

 

Al final, hago que aroAgarrado sea –1, para que “suelte” el aro, y así el MouseMove no me siga arrastrando el aro.

Además, llamo la función AcomodarAros, para reflejar el cambio de la matriz interna, gráficamente.

 

AutoResolución de las torres de Hanoi

 

Okay, esto de la auto resolución si tiene su chiste, pero por favor ya deja de llorar.., la verdad esto es la parte mas fácil de todo el programa (uh, casi).

La auto resolución, es fácilmente implementada con una técnica llamada recursividad.  Aja.. si y eso con que se come?.. , bueno mas o menos significa que una función se implemente en términos de si misma…, (lee la oración anterior varias veces antes de continuar).

 

Primero que nada, vamos a ver la situación mas fácil para auto-resolver las torres de Hanoi:

 

 

Recuerda que tenemos una función que se llama MoverAro.

Si quisiéramos, resolver estas torres de Hanoi, haríamos lo siguiente (en español):

 

1.      Mover el aro blanco (el de arriba), a la segunda torre

2.      Mover el aro rojo (el de abajo), a la tercera torre

3.      Mover el aro blanco (que está en la segunda torre) a la tercera torre.

 

Ahora, expresado en código:

 

1.    Call MoverAro(1, 2)

2.    Call MoverAro(1, 3)

3.      Call MoverAro(2, 3)

 

Ahora, pasa algo, que cada llamada a MoverAro tiene números específicos, tenemos que escribir esto en términos genéricos.  Que tal si estos 2 aros estuvieran en la torre 2, y las quisiéramos mover a la torre 3?.  Es mas digamos, que origen es el numero de la torre donde están estos 2 aros, y que destino es el numero de la torre a donde queremos mover estos 2 aros.  Como expresaríamos la solución en términos de origen y destino?

 

Primero, necesitamos encontrar el numero de la torre que no sea origen, ni destino, y lo vamos a almacenar en la variable temp. Aquí el código:

 

 

temp = 1

If temp = origen or temp = destino then temp = temp + 1

If temp = origen or temp = destino then temp = temp + 1

 

Con este código, hacemos que temp sea la otra torre que no es ni origen ni destino.

 

Ahora si, ya podemos expresar la solución en términos de temp, origen y destino.

 

1.    Call MoverAro(origen, temp)

2.    Call MoverAro(origen, destino)

3.      Call MoverAro(temp, destino)

 

Entonces, ya podemos hacer un procedimiento que mueva 2 aros de una torre a otra torre:

 

Sub Mover2Aros(ByVal origen as integer, ByVal destino as integer)

 

      Dim temp as Integer

temp = 1

If temp = origen or temp = destino then temp = temp + 1

If temp = origen or temp = destino then temp = temp + 1

Call MoverAro(origen, temp)

Call MoverAro(origen, destino)

Call MoverAro(temp, destino)

End Sub

 

 

Bueno, ya tenemos código para resolver las torres de Hanoi cuando sólo hay 2 aros.

Si los dos aros estuvieran en la primera torre, llamaríamos la función de la siguiente manera:

Call Mover2Aros(1, 3)

 

Pero esto no sirve!-  vas a decir!., si yo quiero resolver las torres cuando tenga 3, 4, 5. etc. N torres!.

Por ejemplo, si tenemos la siguiente situación:

 

 

¿Cómo lo resolvemos?.. pues fácil!.  Tenemos una función que mueve 2 aros de una torre a otra torre, con esa podemos mover el aro blanco y el rojo a la torre 2, luego movemos el verde a la torre 3, y luego movemos el blanco y el rojo a la torre 3.

 

Ya expresado en código la solución quedaría así:

 

Call Mover2Aros(1, 2)

Call MoverAro(1, 3)

Call Mover2Aros(2, 3)

 

La primera línea, mueve el aro blanco y rojo, a la segunda torre; la segunda línea simplemente mueve el aro verde a la tercera torre, y la tercera línea mueve el aro blanco y rojo (que están en la segunda torre) a la tercera torre.  Y ya quedaron todos acomodados!, y siguiendo las reglas de Hanoi!.

 

Si te fijas, podrías hacer un procedimiento que mueva tres aros de una torre a otra torre:

 

Sub Mover3Aros(ByVal origen as integer, ByVal destino as integer)

Dim temp as Integer

temp = 1

If temp = origen or temp = destino then temp = temp + 1

If temp = origen or temp = destino then temp = temp + 1

Call Mover2Aros(origen, temp)

Call MoverAro(origen, destino)

Call Mover2Aros(temp, destino)

End Sub

 

Ahora, que tal si tenemos la siguiente situación:

 

 

Igualmente, podemos resolver estas torres fácilmente: Movemos los 3 aros de arriba (el blanco, el rojo y el verde) a la torre 2.  Luego agarramos el aro azul y lo movemos al tercer aro.  Luego Movemos los 3 aros que pusimos en la torre 2 (el blanco, el rojo y el verde), a la torre 3.

 

En código:

Call Mover3Aros(1, 2)

Call MoverAro(1, 3)

Call Mover3Aros(2, 3)

 

Podríamos hacer un procedimiento que mueva 4 aros de un lugar a otro:

 

Sub Mover4Aros(ByVal origen as integer, ByVal destino as integer)

      Dim temp as Integer

temp = 1

If temp = origen or temp = destino then temp = temp + 1

If temp = origen or temp = destino then temp = temp + 1

Call Mover3Aros(origen, temp)

Call MoverAro(origen, destino)

Call Mover3Aros(temp, destino)

End Sub

 

Ya para no hacer larga la historia, también podríamos hacer una función que mueva 5 aros de un lugar a otro, etc.  Si analizas un rato estas funciones, verás que Mover4Aros está implementado en términos de Mover3Aros, y Mover3Aros está implementado en términos de Mover2Aros.  Y si te fijas, el código en cada función es exactamente el mismo, sólo cambia el numero de aros que mueve la función.  Así pues, podríamos hacer una función genérica que mueva n aros.

 

La función estaría mas o menos así:

 

Sub MoverNAros(ByVal origen as integer, ByVal destino as integer, n as Integer)

      Dim temp as Integer

temp = 1

If temp = origen or temp = destino then temp = temp + 1

If temp = origen or temp = destino then temp = temp + 1

Call MoverNAros(origen, temp, n – 1)

Call MoverAro(origen, destino)

Call MoverNAros(temp, destino, n – 1)

End Sub

 

El último parámetro de esta función es n, n viene siendo el número de aros que quiero mover de un lugar a otro.  Ahora, la función MoverNAros está casi bien, sólo falta checar una condición, pues si llamamos esta función así como está, se va a seguir llamando a si misma para siempre (o bueno, hasta que se acabe la memoria del stack).  Sucede que si n = 1, entonces sólo tenemos que mover un aro!.

 

La función final está en la siguiente página.

 

Sub MoverNAros(ByVal origen as integer, ByVal destino as integer, n as Integer)

If n > 1 then

         Dim temp as Integer

temp = 1

If temp = origen or temp = destino then temp = temp + 1

If temp = origen or temp = destino then temp = temp + 1

Call MoverNAros(origen, temp, n – 1)

Call MoverAro(origen, destino)

Call MoverNAros(temp, destino, n – 1)

Else        ‘osea n = 1

      Call MoverAro(origen, destino)

End If     

End Sub

 

Ahora si, ese “If n > 1” hace que cuando n sea mayor que 1, entonces se haga la solución recursiva.  Y cuando n = 1, entonces se realiza un solo movimiento.

 

Otra cosa más, si quieres que se visualice el movimiento, y quieres contar el numero de movimientos, tienes que hacer unas modificaciones al código del procedimiento MoverAro:

 

Sub MoverAro(ByVal origen as Integer, ByVal destino as Integer)

      If nAros(origen) = 0 then Exit Sub

      If nAros(destino) <> 0 then

            If torres(destino, nAros(destino) – 1) < _

               torres(origen, nAros(origen) – 1) then

                  Exit Sub

            End If

      End If

torres(destino, nAros(destino) = torres(origen, nAros(origen) – 1)

      torres(origen, nAros(origen) – 1) = 0

      nAros(origen) = nAros(origen) – 1

      nAros(destino) = nAros(destino) + 1

      cuentaMov = cuentaMov + 1

      Call AcomodarAros

End Sub

 

cuentaMov es una variable que declaras en el general, y ahí llevas la cuenta de los movimientos.

La llamada a AcomodarAros sirve para desplegar el movimiento gráficamente (como se cambia la matriz internamente, entonces AcomodarAros lo refleja visualmente).

Es probable que la auto-solución se vea medio rápida, para hacer que se vea mas lenta, sólo agrega un “delay”.. osea un ciclo For que cuente del 1 al 1000000 o más, para tener a la maquina trabajando un rato.  Este ciclo For lo pondrías también dentro de la función MoverAro.

 

Oooo (¡_!) ooo0

 

Bueno, al parecer eso es todo por esta vez! Que te diviertas mucho! bugs y comentarios a Rafa:

 

Correo Electrónico:

rafanieto@hotmail.com

Hasta la próxima!.