OIA-Wiki

Antes de mencionar estructuras, voy a dar un consejo general para geometría computacional: usar estructuras, es decir structs. Hay muchos problemas que no son tan complicados como parecen, pero que la gracia es poder desglosar todo todo todo en structs y funciones que estén bien declaradas y realicen pocas cosas, y que al juntarlo quede algo como un algoritmo en palabras que nos vaya contando lo que vamos haciendo, tipo “obtenerPoligono(); buscarPuntoCentralAPoligono(); calcularSumaDeDistancias();” Y que por ejemplo en sumaDeDistancias se use la función “obtenerDistancia()”. Esta pavada de declarar bien explicativamente todo puede salvar un problema.

Ahora sí: Cuando pensamos en geometría y en representar objetos geométricos las primeras estructuras que se nos vienen a la cabeza son:

Punto: En 2 ó 3 dimensiones, tiene coordenadas x, y (, z). Podríamos usar un pair<int,int> para puntos en 2D, pero es poco declarativo:

struct Punto{
    int x, y; // o double si por ejemplo vamos a usar puntos medios de segmentos que podrían caer en racionales
    // int z para 3D
};

A partir de esta estructura podemos definir las funciones suma, resta, distancia. Podemos hacerlo adentro del struct o fuera como funciones que reciben dos puntos y devuelven otro.

Notación: Cuando hablamos de un vector (geométricamente, no de $vector<int>$), hablamos de una flecha en el plano. En general se lo nota por ejemplo como el vector $(x_v, y_v)$, que representa la flecha desde el $(0, 0)$ hasta el punto $(x_v, y_v)$ con la punta de la flecha apuntando hacia este último punto.

Producto escalar: El producto escalar entre dos vectores $u$, $v$ es un número (medida escalar, justamente) que se define como $u*v$ = $x_u*x_v + y_u*y_v$ ($+z_u*z_v$ si corresponde), que también es igual a $|u|*|v|*cos(\theta)$ con $\theta$ el ángulo entre los vector. Notar que el producto es nulo si y sólo si $\theta=90°$, si y sólo si son perpendiculares.

Producto vectorial: Es un vector perpendicular al plano generado por los vectores. Básicamente para dos vector en 2 dimensiones dibujados por ejemplo en una hoja de papel, el producto vectorial entre ellos será un vector saliendo (o entrando) de la hoja. El producto vectorial (también llamado producto cruz) se nota con una $x$. Si $u=(x_u, y_u)$, $v=(x_v, y_v)$, entonces $u$ x $v = (0, 0, x_u*y_v - x_v*y_u)$. Se puede demostrar que el área del paralelogramo denotado por los vector es $|u$ x $v| = |x_u*y_v - x_v*y_u|$. Si el valor da positivo, significa que “girando” $u$ hasta ubicarlo en la recta de $v$, el ángulo es convexo ($< 180°$); si es negativo es cóncavo ($> 180°$), y si es $0$ significa que están ubicados sobre la misma recta (notar que $x_u*y_v - x_v*y_u = 0 \Rightarrow x_u*y_v = x_v*y_u \Rightarrow x_u/y_u = x_v/y_v$ si las coordenadas $y$ son no nulas, lo que da la idea de que tienen la misma pendiente.

Recta: Una recta podemos representarla de dos maneras:

1. Una es como función lineal, la típica $R(x) = mx+b$. El único problema es cuando “la pendiente es infinito”, es decir que es una recta vertical. Estos casos tendríamos que contemplarlos con un if.
2. La otra manera, que es la que vamos a usar, es $R(t) = p + t*v$, donde p es un punto por el que pasa la recta, y v un vector de orientación. Si la recta es vertical, el vector es $(0, 1)$, y si la pendiente es por ej. $2$, el vector es el $(1, 2)$. Básicamente, si el vector es $(x_v, y_v)$, significa que la pendiente es $y_v/x_v$, que si $x_v$ es no tiene sentido.

struct Recta{
    Punto p;
    Punto v; // Podríamos definir la estructura vector, que básicamente sería un punto
};

Así, entonces, podemos definir la función “estaPuntoEnRecta” de la siguiente manera:

bool estaPuntoEnRecta(Punto p, Recta r){
    p = resta(p, r.p); // le resto a cada coordenada el valor de las coords del punto p de la recta
    // Ahora, p está en la recta si lo puedo escribir como t*v para algún t
    // Es decir, queremos saber si existe t tal que t*v.x=p.x y t*v.y=p.y
    // Si v.x es 0, entonces p.x debe ser 0, y a t lo podemos setear como nos convenga para acomodar la segunda ecuacion.
    // Analogo si v.y es 0
    return (r.v.x==0 and p.x==0) or (r.v.y==0 and p.y==0) or (p.x*v.y==p.y*v.x);
    // Notar que lo que queríamos para el último paréntesis es que los cocientes entras las coordenadas x e y sean iguales, para que exista t. Pero por la precision, en vez de comparar cocientes, multiplicamos cruzado.
}

De esta manera, expresar el segmento entre dos puntos a y b es simplemente armar una recta donde el punto $p$ sea a, el vector $v$ sea (b-a) y el parámetro $t$ vaya de $0$ a $1$. Se ve que cuando $t=0$, $a+t*(b-a) = a$, y cuando $t=1$, $a+(b-a)=b$. El punto medio del segmento por ejemplo es hacer $t=0.5$.

Área de un polígono

Pensemos primer cómo calcular el área de un triángulo. Esto es fácil pensando que el área de un paralelogramo es el módulo del producto vectorial entre los dos vectores. El área del triángulo conformado por los dos vector en cuestión como lados, y la diagonal correspondiente como tercer lado, es simplemente $|u$ x $v|/2$.

Entonces, para hallar el área de un polígono, triangulamos! Supongamos que el polígono está formado por los puntos, en orden horario, $x_1, x_2, \ldots, x_n$. Luego, tomamos por ejemplo el punto $x_1$ como punto para la triangulación, y dividimos al polígono en los triángulos $(x_1, x_2, x_3), (x_1, x_3, x_4), \ldots, (x_1, x_{n-1}, x_n)$, y sumamos las áreas de estos polígonos. Si un polígono tiene ángulos cóncavos (lo que hace que estos triángulos abarquen área fuera del polígono, por el tema de los signos esto se arregla.

El código queda:

double areaPoli(vector<Punto> v){
    int area=0;
    int n=v.size();
    for(int i=1; i<n-1; i++){
        int x1=v[i].x-v[0].x;
        int y1=v[i].y-v[0].y;
        int x2=v[i+1].x-v[0].x;
        int y2=v[i+1].y-v[0].y;
        area+=(x1*y2-x2*y1;
    }
    return abs((double)area/2.0); // notar que area es entero, entonces la parte decimal del area es .0 ó .5
}

Punto en Polígono

Algo interesante también, es saber si un punto dado está en un polígono o no.

Una manera (que cuando me la contaron me pareció súper copada y bastante fácil de comprender) es agarrar un punto fuera del polígono (podemos usar los límites de los valores de $x$ e $y$ y agarrar uno bien lejos) y tirar un rayo recto hasta el punto en cuestión. Pensemos entonces que a medida que se viene el rayo, que inicialmente está afuera, si corta un segmente del polígono, entró. Si vuelve a cortar otro segmento, salió.

Entonces básicamente vemos la cantidad de segmentos del polígono que corta el rayo, y el punto estará adentro si y sólo si la cantidad es impar. Podemos tener una variable de tipo boolean que empieza siendo false ya que el rayo empieza afuera, y va cambiando de valor al cruzar un segmento. Lo único que hay que tener en cuenta acá es que si el rayo pasa justo por un punto del polígono, si el ángulo de ese punto es convexo el rayo cruza, y si es cóncavo no.

Para saber por donde el rayo corta a los segmentos, hay que pensar en cómo averiguar el punto de intersección de dos rectas.

Para esto, pensemos que queremos un punto que pertenezca a ambas rectas. Si las rectas están dadas por las fórmulas $p_1 + t*v_1$ y $p_2 + k*v_2$, entonces queremos valores de $t$ y $k$ que cumplan que $p_1 + t*v_1 = p_2 + k*v_2$

Para sacarnos de encima una variable, podemos por ejemplo multiplicar con el producto vectorial por $v_2$ a ambos lados:

$(p_1 + t*v_1)$ x $v_2 = (p_2 + k*v_2) $ x $v_2$.

$p_1$ x $v_2 + t*v_1$ x $v_2 = p_2$ x $v_2$, ya que $v_2$ x $v_2 = 0$.

$t*v_1$ x $v_2 = (p_2-p_1)$ x $v_2$, de donde despejamos $t$ sabiendo los productos vectoriales (como el producto de $t$ con el producto cruz es un número por un vector, entonces cada coordenada del vector del lado izquierdo debe coincidir con la coordenada correspondiente del lado derecho. En particular, si estamos en 2 dimensiones, debe coincidir el tercer valor de ambos vectores, por lo que $t$ será la división entre la tercera coordenada del vector derecho y la tercera coordenada de $v_1$ x $v_2$.

CODIGO QUE SEA LA POSTA!