Ejercicio obligatorio 2

Fecha de entrega: Viernes 9 de Octubre

Nota

Nunca es buena idea empezar por un ejercicio integrador antes de tener practicados los temas que el trabajo integra.

Se sugiere antes de desarrollar este trabajo resolver, al menos, los siguientes ejercicios de la guía de Memoria dinámica:

  • Ejercicio 12 (combinar vectores).

  • Ejercicio 14.a (matriz identidad).

  • Ejercicio 16 con el 1.b y 1.c de la guía de estructuras (dirección y persona).

Introducción

Estructuras de datos

A partir de ahora vamos a representar a los vectores en \(\mathbb R^2\) como estructuras

typedef struct {
    float x, y;
} vector_t;

Además queremos modelar un polígono, en principio podríamos hacerlo utilizando la siguiente estructura:

typedef struct {
    vector_t *cs;   // Arreglo dinámico de n coordenadas
    size_t n;       // Cantidad de coordenadas
} poligono_t;

Ahora bien, como nos va a interesar mover el polígono, rotarlo con respecto a su centro de masa y hacer otras operaciones vamos a representarlo de una manera un poco más compleja, pero que nos va a simplificar tremendamente los cálculos. Lo que vamos a hacer es representar el arreglo de coordenadas cs siempre con el cero en su centro de masa y luego vamos a definir la rotación y translación del polígono para transformarlo a la posición en la que realmente lo queremos.

Entonces nuestra segunda iteración será así:

typedef struct {
    vector_t *cs;   // Arreglo dinámico de n coordenadas, con centro de masa en el origen
    size_t n;       // Cantidad de coordenadas

    vector_t cm;    // Translación
    double a;       // Rotación
} poligono_t;

Pero si representáramos el polígono de esta forma cada vez que quisiéramos los puntos en la posición actual, es decir, las coordenadas cs rotadas por a y transladadas según cm tendríamos que hacer la rotación y la translación una y otra y otra vez, cuando más veces vamos a querer consultar los puntos que veces vamos a querer moverlos o rotarlos. Entonces la idea será guardar una versión transformada para cada vez que tengamos que acceder a los puntos que se recalculará en base a las coordenadas solamente cuando se modificaran los parámetros de transformación cm y a.

Con esto tendremos:

typedef struct {
    vector_t *coordenadas;  // Arreglo dinámico de n coordenadas, con centro de masa en el origen
    size_t n;               // Cantidad de coordenadas.

    vector_t cm;            // Translación
    double a;               // Rotación
    vector_t *cs;           // Arreglo dinámico con las n coordenadas rotadas a y transladadas cm

    float radio;            // Radio del polígono
} poligono_t;

¿Qué es eso que se metió por la ventana? Bueno, además nos interesará tener calculado el radio del polígono como la longitud de la coordenada que esté más alejada de su centro de masa.

Notar que en esta estructura las variables coordenadas, n y radio se computan una sola vez al inicio, mientras que las variables cm y a varían todo el tiempo y, en caso de variar, implican recalcular cs.

El esquema de esta estructura será:

../_images/20262_ej2.png

Intersección de polígonos

Vamos a computar la intersección de polígonos, para eso aplicaremos dos métodos distintos, uno aproximado pero muy barato de computar y otro caro pero exacto el cual aplicaremos sólo después de tener un resultado positivo en el método barato.

Intersección según circunferencias

El método barato es sencillo: Envolvemos al polígono en un círculo con el radio calculado y el centro en el centro de masa. Si el círculo de ambos polígonos no se intersecta entonces no hay intersección posible. Si se intersecta no podemos decir nada porque nuestra aproximación es burda.

Entonces, si trazamos una línea entre sus centros de masa, la longitud de esa línea tendrá que ser mayor que la suma de ambos radios para garantizar la inexistencia de intersercción.

../_images/20262_ej2_radios.png

Intersección AABB

El método caro de computar implica proyecciones. Si proyectamos todos los puntos de ambos polígonos sobre una recta observaremos que cada uno de los polígonos se proyectará como un segmento. De ese segmento nos interesa el comienzo y el final, es decir, el mínimo y el máximo de los puntos proyectados.

Llamemos \(a\) al mínimo de los puntos proyectados del polígono A y \(A\) al máximo. Hagamos lo mismo con los puntos de B y llamémoslos \(b\) y \(B\).

Si "mirando" desde la recta de proyección los polígonos no se superponen observaremos que sus segmentos son disjuntos, es decir o bien \(a < A < b < B\) o bien \(b < B < a < A\). Es decir, el máximo de uno es menor que el mínimo que el otro.

Ahora bien, si mirando desde esa recta los segmentos se superponen lo que veremos es que estarán intercalados puntos de A con puntos de B.

../_images/20262_ej2_aabb.png

En la imagen anterior se puede ver las proyecciones de todos los puntos de dos polígonos A y B sobre los dos ejes coordenados \(x\) e \(y\). En el caso de "mirar" según el eje \(x\) los polígonos se superponen, notar que el patrón es \(a < b < A < B\), mientras que "mirando" desde el eje \(y\) los polígonos no se superponen y el patrón es \(a < A < b < B\).

¿Cómo proyectamos?... ¡pero hay que explicarte todo! Las proyecciones se manejan mediante productos internos, siendo \(P\) un punto y \(e\) un eje \(P_e = P \cdot e\) será la proyección de \(P\) en \(e\). Este es un escalar. ¿El eje tiene que estar normalizado? Sólo si me interesa utilizar ese escalar como una distancia, como a nosotros nos interesa saber el orden no es necesario normalizar.

Ahora bien, en nuestro ejemplo anterior utilizando un eje había superposición y utilizano el otro eje no había superposición. Bueno, lo que dice el teorema de los ejes separados es que si encontramos un eje sobre el cual no haya superposición entonces no hay intersección entre dos polígonos. Así que el problema es sencillo: Evaluamos infinitos ejes hasta encontr...

¿Qué ejes probar? Bueno, se puede demostrar que alcanza con probar cada una de las normales a las aristas de mis polígonos. Es decir con cada uno de los segmentos \(\overline{p_i p_{i + 1}}^\perp\) que se generan con los dos polígonos hay que proyectar todos los puntos de uno y otro polígono, encontrar sus mínimos y máximos y verificar si se encuentra un patrón AABB de no intersección. Con que una de las normales que no hay intersección entonces no hay intersección. Si con todas las normales se verifica intersección entonces los polígonos se intersectan.

¡Pero eso es un montón de cuentas! ¿Pero estás leyendo?, dijimos que había un método impreciso pero rápido y otro preciso pero lento. Esto lo vamos a verificar sólo si no podemos determinar la no intersección mirando los radios.

Trabajo

Funciones con vectores

Implementar una función float vector_producto_escalar(vector_t a, vector_t b); que devuelva el producto escalar entre los dos vectores a y b.

Implementar una función float vector_producto_vectorial(vector_t a, vector_t b); que devuelva el producto vectorial entre a y b (según las mismas aclaraciones que en el EJ1).

Implementar una función vector_t vector_restar(vector_t a, vector_t b); que devuelva el vector resta a menos b.

Implementar una función vector_t vector_perpendicular(vector_t a); que devuelva el vector a rotado 90º, es decir para \((x, y)\) será \((-y, x)\).

Implementar una función float vector_norma(vector_t a); que devuelva la norma de a.

Implementar una función void vector_rotar(vector_t v[], size_t n, double a); que rote cada uno de los n vectores de v según el ángulo a.

Implementar una función void vector_trasladar(vector_t v[], size_t n, vector_t t); que translade cada uno de los n vectores de v según la translación t.

Implementar una función vector_t vector_centro_de_masa(const vector_t v[], size_t n); que devuelva el centro de masa del polígono cerrado dado por los n vectores de v. Se debe utilizar la fórmula:

\[A = \sum_{i=0}^{n-1} \frac12 p^i \times p^{i+1},\]
\[C_x = \sum_{i=0}^{n-1} \frac1{6A} \left(p^i_x + p^{i+1}_x\right) \left(p^i \times p^{i+1}\right),\]
\[C_y = \sum_{i=0}^{n-1} \frac1{6A} \left(p^i_y + p^{i+1}_y\right) \left(p^i \times p^{i+1}\right).\]

(Notar que no es exactamente lo pedido en el EJ1, los cálculos de \(A\) y el cálculo parcial de \(C_x\) y \(C_y\) pueden hacerse en una única iteración y \(A\) no es estrictamente el área dado que puede dar negativa. Implementar los tres cálculos en una única iteración y aprovechando donde los términos se repiten.)

Creación y destrucción

Se pide implementar una función poligono_t *poligono_crear(const vector_t coordenadas[], size_t n); que dado un poligono de n coordenadas cree e inicialice toda la memoria necesaria para un poligono_t. Las coordenadas recibidas no necesariamente tendrán centro de masa en el origen, será responsabilidad de la función acomodarlas donde corresponde. En la creación además debe computarse el radio. Los cm y a iniciales serán cero, por lo que inicialmente cs tendrá los mismos vectores que coordenadas.

Se pide implementar la función void poligono_destruir(poligono_t *poligono); que libere la memoria asociada al poligono previamente creado.

Se pide implementar una función poligono_t *poligono_clonar(const poligono_t *poligono); que devuelva una copia del poligono en nueva memoria.

Acceso a los datos

Se pide implementar una función size_t poligono_get_largo(const poligono_t *poligono); que devuelva la cantidad de coordenadas del poligono.

Se pide implementar una función vector_t poligono_get_coordenada(const poligono_t *poligono, size_t i); que devuelva la coordenada i del poligono. (La coordenada transladada y rotada, la única que nos importa.)

Se pide implementar una función vector_t poligono_get_cm(const poligono_t *poligono); que devuelva la translación cm del poligono.

Se pide implementar una función double poligono_get_a(const poligono_t *poligono); que devuelva el ángulo a del poligono.

Se pide implementar una función void poligono_transformacion(const poligono_t *poligono, vector_t *cm, double *a); que devuelva tanto el cm como el a del poligono.

Transformación

Implementar una función void poligono_set_cm(poligono_t *poligono, vector_t cm); que establezca el nuevo cm en el poligono. (¿Qué debe hacerse con las coordenadas cs?)

Implementar una función void poligono_set_a(poligono_t *poligono, double a); que establezca el nuevo a en el poligono.

Implementar una función void poligono_transformar(poligono_t *poligono, vector_t cm, double a); que establezca tanto cm como a en el poligono.

Intersección

Implementar una función bool poligono_hay_interseccion(const poligono_t *a, const poligono_t *b); que indique si hay intersección entre el polígono a y b. La función debe primero hacer la verificación de no intersección utilizando los radios y solo en caso de no poder determinarla debe verificar la intersección por el método AABB proyectando contra cada uno de los segmentos de los dos polígonos.

Programa

Tenemos un formato para ingresar polígonos por stdin que consiste en primero la cantidad \(n\) de puntos del polígono, y luego \(n\) vectores de a uno por vez. Finalizados los puntos se leerá un vector con un centro de masa y luego un ángulo en radianes. Este centro de masa y esa cantidad de radianes se utilizarán para modificar al polígono anterior.

Implementar un programa que lea polígonos y sus respectivas transformaciones hasta agotar la entrada. Luego de leído el primer polígono por cada polígono nuevo que se lea se debe comprobar si el mismo intersecta o no al anterior, la entrada, además contiene un "Si" para los casos donde hay interesección y un "No" para los casos donde no la haya. El programa debe validar que lo que dice la entrada sea consistente con lo que valida. En caso que haya inconsistencias entre lo que dice la entrada y lo que computa el programa el programa debe abortar con un mensaje de error.

Notar que para realizar la operatoria pedida nunca hace falta tener más de dos polígonos en memoria.

Se provee la siguiente entrada: entrada_20262_ej2.txt

Entrega

Deberá entregarse el código fuente del programa desarrollado.

El programa debe:

  1. Compilar correctamente con los flags:

    -Wall -Werror -std=c99 -pedantic -fno-extended-identifiers

  2. y pasar Valgrind correctamente

La entrega se realiza a través del sistema de entregas.

El ejercicio es de entrega individual.