CP-UPV Bootcamp - Capítulo 11

Capítulo 11: Geometría

Introducción

En este capítulo nos adentraremos en el fascinante mundo de la geometría computacional. Aquí aprenderemos a manejar puntos y vectores, calcular áreas, distancias y resolver problemas como la envolvente convexa (convex hull).

Índice de contenidos

• Representación de puntos y vectores
  • Puntos y vectores como pares ordenados
  • Representación en código
  • Operaciones básicas
• Distancias y ángulos
• Áreas y orientación
  • Teorema del cordel
  • Teorema de Pick
• Envolvente convexa (Convex Hull)

Representación de puntos y vectores

Puntos y vectores como pares ordenados

Un punto en el plano se representa con dos coordenadas (\(x, y\)), donde x e y pueden ser enteros o números reales (con decimales). Por ejemplo:

• P = (3, 5)
• Q = (0.5, -2)

Representación en código

Para facilitar las cosas, podemos representar puntos o vectores mediante estructuras o clases que contengan las coordenadas, por ejemplo:

struct Point {
    double x, y;
    Point(double x, double y) : x(x), y(y) {}
};

int main() {
    // Cómo utilizar la estructura

    Point p(3, 5);
    Point q(0.5, -2);

    p.x = 4;

    cout << p.x << " " << p.y << endl;

    return 0;
}

Operaciones básicas

Podemos utilizar la sobrecarga de operadores de C++ para definir algunas operaciones básicas en nuestra plantilla:

Vector de desplazamiento y distancia entre dos puntos

Podemos definir la resta para dos puntos, simplemente restando sus componentes, lo que nos resultará en otro punto, que podemos considerar un vector de posición

Point operator-(const Point &p) const {
    return Point(x - p.x, y - p.y);
}

Si calculamos el módulo o longitud del vector de posición hallaremos la distancia entre los puntos:

double length(const Point &v) {
    return sqrt(v.x * v.x + v.y * v.y);
}

int main() {
    Point p(3, 5);
    Point q(0.5, -2);

    Point v = p - q;

    cout << "Distancia de P a Q: " << length(v) << endl;
    return 0;
}

Producto escalar

El producto escalar (dot product) de dos vectores es una operación fundamental en la geometría computacional que nos permite calcular el ángulo entre ellos y proyectar un vector sobre el otro. Dados dos vectores $\vec u$ y $\vec v$, su producto escalar se define como: $\vec u * \vec v = \vec u_x * \vec v_x + \vec u_y * \vec v_y$. El resultado es un número real. Si el producto escalar es positivo, el ángulo entre los vectores es agudo, si es cero son perpendiculares, y si es negativo es obtuso. Esta operación es muy útil para comprobar ortogonalidad y para calcular proyecciones y longitudes proyectadas.

double dot(const Point &p) const {
    return x * p.x + y * p.y;
}

Producto cruzado

El producto cruzado (cross product) nos da una medida del área del paralelogramo formado por dos vectores y nos indica su orientación relativa. Dados dos vectores $\vec u$ y $\vec v$, su producto cruzado se define como: $\vec u$ x $\vec v = \vec u_x * \vec v_y + \vec u_y * \vec v_x$. El valor del producto cruzado es positivo si $\vec v$ está a la izquierda de $\vec u$ (en sentido antihorario), negativo si está a la derecha (en sentido horario) y cero si los vectores son colineales. Esta operación es esencial para determinar la orientación de tres puntos y para calcular áreas.

double cross(const Point &p) const {
    return x * p.y - y * p.x;
}

Plantilla completa

struct Point {
    double x, y;
    Point(double x, double y) : x(x), y(y) {}
    Point operator-(const Point &p) const {
        return Point(x - p.x, y - p.y);
    }
    double cross(const Point &p) const {
        return x * p.y - y * p.x;
    }
    double dot(const Point &p) const {
        return x * p.x + y * p.y;
    }
};

// Producto cruzado de AB x AC
double cross(const Point &a, const Point &b, const Point &c) {
    return (b - a).cross(c - a);
}

Distancias y ángulos

Una de las aplicaciones más comunes en geometría computacional es calcular la distancia entre dos puntos o el ángulo entre dos vectores. La distancia entre dos puntos \( P = (x_1, y_1) \) y \( Q = (x_2, y_2) \) se obtiene aplicando el teorema de Pitágoras: \[ \text{distancia}(P, Q) = \sqrt{(P_x - Q_x)^2 + (P_y - Q_y)^2} \] Esto se puede calcular fácilmente con la función length aplicada al vector de desplazamiento entre ambos puntos.

El ángulo \( \theta \) entre dos vectores \( \vec{u} \) y \( \vec{v} \) puede obtenerse mediante el producto escalar: \[ \cos \theta = \frac{\vec{u} \cdot \vec{v}}{|\vec{u}| |\vec{v}|} \] Esto nos permite determinar el ángulo y, por tanto, la relación geométrica entre los vectores.

// Calcula la distancia entre dos puntos
double distance(const Point &a, const Point &b) {
    return sqrt((a - b).dot(a - b));
}

// Calcula el ángulo entre dos vectores
double angle(const Point &u, const Point &v) {
    return acos(u.dot(v) / (sqrt(u.dot(u)) * sqrt(v.dot(v))));
}

Áreas y orientación

A continuación veremos cómo calcular el área de un polígono y determinar su orientación. La orientación de un polígono o de tres puntos se puede determinar con el producto cruzado: \[ \text{orientación}(A, B, C) = (B - A) \times (C - A) \] Como hemos mencionado en un apartado anterior, si el resultado es positivo los puntos forman un giro antihorario, si es negativo horario, y si es cero, son colineales.

Teorema del cordel

Para hallar el área de un polígono de forma eficiente podemos usar el teorema del cordel (Shoelace theorem). Si el polígono tiene vértices \( P_0, P_1, \dots, P_{n-1} \), su área es: \[ \text{Área} = \frac{1}{2} \left| \sum_{i=0}^{n-1} (x_i * y_{i+1} - y_i * x_{i+1}) \right| \] donde se considera que \( P_n = P_0 \). Este método es muy rápido y evita tener que dividir el polígono en triángulos.

// Calcula el área de un polígono con el teorema del cordel
double poly_area(const vector<Point> &poly) {
    double area = 0;
    int n = poly.size();
    for (int i = 0; i < n; ++i) {
        area += poly[i].cross(poly[(i + 1) % n]);
    }
    return abs(area) / 2.0;
}

Teorema de Pick

Si el polígono tiene todos sus vértices en puntos de una cuadrícula (coordenadas enteras), podemos aplicar el Teorema de Pick: \[ \text{Área} = I + \frac{B}{2} - 1 \] donde \( I \) es el número de puntos interiores y \( B \) el número de puntos en el borde. Este teorema es muy útil en problemas de geometría en el plano entero.

Envolvente convexa (Convex hull)

La envolvente convexa (convex hull) de un conjunto de puntos es el menor polígono convexo que los contiene a todos. Es como si envolviésemos los puntos con una goma elástica que se ajusta lo máximo posible.

Uno de los algoritmos más conocidos para calcular la envolvente convexa es el Graham Scan. Su idea principal es:

1. Elegir el punto más bajo (y el más a la izquierda si hay empate) como punto base.
2. Ordenar los demás puntos por el ángulo polar que forman con el punto base.
3. Recorrer los puntos y mantener una pila con los puntos de la envolvente, eliminando los que causan un giro horario.

El Graham Scan tiene un coste de \( O(n \log n) \) debido a la ordenación de los puntos.

bool cmp(const Point &a, const Point &b, const Point &pivot) {
    double c = (a - pivot).cross(b - pivot);
    if (c == 0) return (a - pivot).dot(a - pivot) < (b - pivot).dot(b - pivot);
    return c > 0;
}

vector<Point> convex_hull(vector<Point> pts) {
    int n = pts.size();
    // Encontrar el punto más bajo (y más a la izquierda si hay empate)
    int pivot_idx = 0;
    for (int i = 1; i < n; ++i) {
        if (pts[i].y < pts[pivot_idx].y || 
            (pts[i].y == pts[pivot_idx].y && pts[i].x < pts[pivot_idx].x)) {
            pivot_idx = i;
        }
    }
    swap(pts[0], pts[pivot_idx]);
    Point pivot = pts[0];

    // Ordenar por ángulo polar respecto al pivot (el punto base)
    sort(pts.begin() + 1, pts.end(), [&](const Point &a, const Point &b) {
        return cmp(a, b, pivot);
    });

    // Construir la envolvente
    vector<Point> hull;
    for (const Point &p : pts) {
        while (hull.size() >= 2 && (hull[hull.size()-1] - hull[hull.size()-2]).cross(p - hull[hull.size()-2]) <= 0) {
            hull.pop_back();
        }
        hull.push_back(p);
    }

    return hull;
}

El resultado es un vector con los puntos de la envolvente en orden antihorario. Este método es estable y funciona bien siempre que los puntos sean distintos.