Geometría Computacional

     Quizás te preguntes a qué se refiere la geometría computacional sin darte cuenta que es la base de todos los diseños e interfaces que tenemos, así como para el diseño de muchos objetos los cuales son asistidos por computadora.
     La geometría computacional funciona a través del uso de objetos geométricos creados por conjuntos de segmentos y puntos definidos en un plano cartesiano "imaginario". El plano utilizado contiene dos dimensiones pues así es mas fácil visualizarlo y solucionarlo.
    Para entender mejor esto, lo explicaremos a detalle y comenzaremos definiendo un segmento linea.
    Un segmento linea es la unión de dos puntos diferentes lo cuales podemos llamar P1 y P2, estos puntos tienen un conjunto de coordenadas donde P1 se define por (X1, Y1) y P2 esta definido por (X2, Y2), Estos dos puntos forman el segmento llamado p1p2. Esto puede causar confusión entre un segmento y una linea, pues en una linea s pueden definir los puntos P1 y P2 pero la diferencia es que una linea es una recta infinita en el plano cartesiano y un segmento es una recta acotada, es decir tiene un inicio y un fin los cuales son los puntos P1 Y P2. En un segemento también se puede saber en que dirección va nuestro segmento, esto se define por el orden en que definiremos el segmento, es decir si el segmento lo llamamos p1p2 la dirección será del punto p1 hacia el punto p2 y si lo llamamos p2p1 la dirección será de p2 a p1, al definir su dirección podemos llamar al segmento "vector".

Imagen 1

     Una vez comprendido que es un segmento, debemos pasar a las intersecciones de estos, pues así podremos formar figuras geométricas y para comprobarlo matemáticamente (sin necesidad de un plano cartesiano) realizaremos lo siguiente. Imaginemos dos vectores V1 y V2 partiendo del origen tal y como se muestra en la imagen siguiente.

Imagen 2

     Gráficamente notamos que los vectores solo se unen en el origen, pero en sus puntos terminales no, pero computacionalmente esto sería mas difícil de visualizar así que tenemos que encontrarlo matemáticamente, y para eso debemos realizar determinantes o producto cruzado, los datos que ocuparemos serán los del punto p2 y el punto p3 que se encuentran en la imagen 2.

     

Imagen 2.1. Uso de determinante.

     Al realizar esta operación nos devolverá dos resultados, la multiplicación de (X1)*(Y2)=R1 y (X2)*(Y1)=R2, estos dos resultados se pondrán en la siguiente operación. R1 - R2 = +- Rf. Es importante saber que la operación anterior se realizara de manera algebraica, es decir que R1 y R2 respetaran sus signos obtenidos en la operación de determinantes de tal manera que el signo (-) presente en la operación debe influir con la leyes de signos. 

Imagen 2.2. Paso dos de la determinante.

     En el resultado Rf lo que nos importará es el signo obtenido pues si tenemos un signo (-) se interpreta que los puntos de los extremos de nuestros segmentos se cruzan y si el signo es (+) los puntos extremos de los segmentos no se tocan. El número obtenido es el área total si formáramos una figura con otro punto, pero eso es otro tema.

Imagen 2.3. Resultado final de la determinante.

     Para entender mejor lo anterior, mostraremos un ejemplo con valores numéricos. Tenemos dos segmentos, ambos partiendo del origen, el segmento 1 tiene las coordenadas "(0,0),(5,4)", el segmento 2 tiene las coordenadas (0,0),(3,8). Gráficamente se vería de la siguiente forma.

Imagen 3.1. Gráfica de los segmentos.

     Aplicando la formula de determinantes explicada anteriormente quedaría de la siguiente forma.

Imagen 3.2. Aplicación de determinantes.

     El resultado final de la determinante para la operación algebraica anteriormente explicada queda así.

Imagen 3.2. Paso 2 de la determinante.

     Recuerda que el signo (-) en este caso se obtuvo por la ley de signos al multiplicar el signo de 12 por el signo (-) de la fórmula. El resultado final queda así.

Imagen 3.3. Resultado.

     Así se comprueba matemáticamente que los segmentos no se cruzan en sus extremos por el signo (+).

     Ahora, si tenemos dos segmentos que no empiezan en el origen, pero comparten un punto en común, la comprobación se realizaría de igual forma que el caso anterior, solo que se realiza un paso previo.

Imagen 4. Segundo caso.

    El paso previo es aplicar esta fórmula (p2-p1) x (p4-p3), recordemos que en estos caso el símbolo (x) hace referencia a determinantes o producto cruzado. Si analizamos la imagen, nos daremos cuenta que p1 seria el mismo punto p3 pues comparten este punto quedando la ecuación de la siguiente manera: (p2-p1) x (p4-p1). Realizando las operaciones indicadas los resultados son (3,0) x (1,3). Teniendo estos valores podemos aplicar la determinante explicada en el caso uno (cuando los segmentos parten del origen) y así obtener el resultado.

     En el caso tres nos centraremos más al análisis pues por simple inspección determinaremos si los segmentos se cruzan o no dependiendo del signo que decretemos. Éste caso se ocupa cuando los segmentos no tienen un punto en común. Imaginemos que tenemos estos segmentos en el plano.

Imagen 5. Tercer caso.

     En este caso haremos 4 análisis, el primero es analizar a el segmento AB con respecto al punto C y al punto D, los otros dos análisis serán  del segmento CD con respecto a los puntos A y B. Para determinar los signos se trazan segmentos imaginarios y dependiendo de la inclinación hacia la derecha (-) o izquierda (+) se determinarán los signos.

    Primero analizaremos el segmento AB respecto a C, si trazamos una linea imaginaria del punto A a C encontraremos un segmento con una leve inclinación hacia la izquierda por lo cual determinamos que el signo sera (+), ahora del segmento AB con respecto al punto D trazaremos un segmento imaginario del punto A al B obteniendo una dirección hacia la derecha determinando que el signo sera (-). Para el segmento CD realizaremos lo mismo, primero analizaremos CD con respecto al punto A, trazamos un segmento imaginario de C a A y tenemos una inclinación hacia la derecha determinando que tiene signo (-) y ahora analizaremos el mismo segmento con respecto a B y obtenemos un signo (+).

     Los segmentos se cruzarán siempre y cuando el analisis (1 y 2) y (3 y 4) sean signos diferentes.

Imagen 5.1. Primer análisis.

Imagen 5.2. Segundo análisis.

Imagen 5.4. Tercer análisis.

Imagen 5.5 Cuarto análisis.

      Para este caso tenemos que el análisis 1 y 2 tienen signos diferentes (+) y (-) respectivamente y el análisis 3 y 4 también tienen signos diferentes (-) y (+) por lo tanto los segmentos sí se cruzan.

     El cuarto caso se utiliza para saber si un punto esta sobre un segmento o entre un segmento. Imaginemos el siguiente conjunto de coordenadas.

Imagen 6. Cuarto caso.

     Para este caso solo se verifica si se cumple la siguiente condición: min(XA,XB) <= XC <= Max (XA,XB) &&  min(YA,YB) <= XC <= Max (YA,YB). Donde min (XA, XB)  y  (YA, YB) son los puntos mas pequeños en las cordenadas de X y Y respectivamente para el segmento AB. Max (XA,XB) y  Max (YA,YB) son los puntos de X y Y respectivamente del segmento AB. 

    Estos 4 casos son los principios de la Geometría Computacional. Hasta luego!