📐 Geometría Computacional

🔺 4.1 Primitivas Geométricas

Cross Product (Producto Cruz 2D)

Visualización: Giro y Producto Cruz

Implementación

double cross(Point O, Point A, Point B) {
    return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);
}

// Orientación: >0 CCW, <0 CW, =0 colineal
int orient(Point a, Point b, Point c) {
    double v = cross(a, b, c);
    if (v > 0) return 1;   // CCW
    if (v < 0) return -1;  // CW
    return 0;              // colineal
}

// Test si segmentos AB y CD se intersectan
bool segmentsIntersect(Point A, Point B, Point C, Point D) {
    int o1 = orient(A, B, C), o2 = orient(A, B, D);
    int o3 = orient(C, D, A), o4 = orient(C, D, B);
    if (o1 * o2 < 0 && o3 * o4 < 0) return true;
    // Casos colineales...
    return false;
}

def cross(o, a, b):
    return (a[0] - o[0]) * (b[1] - o[1]) - (a[1] - o[1]) * (b[0] - o[0])

def orient(a, b, c):
    v = cross(a, b, c)
    if v > 0: return 1   # CCW
    if v < 0: return -1  # CW
    return 0             # colineal

def segments_intersect(a, b, c, d):
    o1, o2 = orient(a, b, c), orient(a, b, d)
    o3, o4 = orient(c, d, a), orient(c, d, b)
    if o1 * o2 < 0 and o3 * o4 < 0:
        return True
    # Casos colineales...
    return False

📍 4.2 Closest Pair Problem

Divide & Conquer Approach

1. Ordenar por coordenada x en O(n log n)
2. Dividir P en mitades izquierda/derecha en la mediana xm
3. Conquistar: Recursivamente encontrar δL, δR; sea δ = min(δL, δR)
4. Combinar: Considerar la franja vertical |x - xm| < δ
   • Ordenar puntos en la franja por y (merge de dos listas ordenadas)
   • Cada punto revisa máximo 7 sucesores

Visualización: Closest Pair

Implementación

double closestPair(vector<Point>& Px, vector<Point>& Py) {
    int n = Px.size();
    if (n <= 3) return bruteForce(Px);
    
    int mid = n / 2;
    Point midPoint = Px[mid];
    
    vector<Point> Lx(Px.begin(), Px.begin() + mid);
    vector<Point> Rx(Px.begin() + mid, Px.end());
    vector<Point> Ly, Ry;
    for (auto& p : Py) {
        if (p.x <= midPoint.x) Ly.push_back(p);
        else Ry.push_back(p);
    }
    
    double dL = closestPair(Lx, Ly);
    double dR = closestPair(Rx, Ry);
    double d = min(dL, dR);
    
    // Franja
    vector<Point> strip;
    for (auto& p : Py)
        if (abs(p.x - midPoint.x) < d) strip.push_back(p);
    
    for (int i = 0; i < strip.size(); i++)
        for (int j = i + 1; j < strip.size() && strip[j].y - strip[i].y < d; j++)
            d = min(d, dist(strip[i], strip[j]));
    
    return d;
}

🧹 4.3 Line Sweep Algorithm

Estructuras Clave

• Sweep Line: Línea vertical que se mueve de izquierda a derecha
• Event Queue: Endpoints de segmentos + intersecciones descubiertas (priority queue por x)
• Status Structure: BST balanceado de segmentos activos ordenados por y en la sweep line

Procesamiento de Eventos

Visualización: Sweep Line

🔷 4.4 Convex Hull

Algoritmos Principales

Visualización: Convex Hull

Graham Scan

vector<Point> grahamScan(vector<Point> pts) {
    int n = pts.size();
    if (n < 3) return pts;
    
    // Encontrar punto más bajo
    int pivot = 0;
    for (int i = 1; i < n; i++)
        if (pts[i].y < pts[pivot].y || 
           (pts[i].y == pts[pivot].y && pts[i].x < pts[pivot].x))
            pivot = i;
    swap(pts[0], pts[pivot]);
    Point p0 = pts[0];
    
    // Ordenar por ángulo polar
    sort(pts.begin() + 1, pts.end(), [&](Point a, Point b) {
        double v = cross(p0, a, b);
        if (v == 0) return dist(p0, a) < dist(p0, b);
        return v > 0;
    });
    
    // Construir hull
    vector<Point> hull;
    for (auto& p : pts) {
        while (hull.size() >= 2 && 
               cross(hull[hull.size()-2], hull[hull.size()-1], p) <= 0)
            hull.pop_back();
        hull.push_back(p);
    }
    return hull;
}

def graham_scan(pts):
    if len(pts) < 3:
        return pts
    
    # Encontrar punto más bajo
    p0 = min(pts, key=lambda p: (p[1], p[0]))
    pts = sorted(pts, key=lambda p: (
        math.atan2(p[1] - p0[1], p[0] - p0[0]),
        (p[0] - p0[0])**2 + (p[1] - p0[1])**2
    ))
    
    # Construir hull
    hull = []
    for p in pts:
        while len(hull) >= 2 and cross(hull[-2], hull[-1], p) <= 0:
            hull.pop()
        hull.append(p)
    return hull

🎯 4.5 Voronoi Diagrams & Delaunay

Propiedades

• Celdas son convexas (intersección de half-planes)
• Aristas están en bisectores perpendiculares
• Complejidad O(n) vértices y aristas
• Grafo dual es la triangulación de Delaunay

Fortune's Algorithm

• Beach line: Lower envelope de parábolas
• Site events: Nueva parábola
• Circle events: Arco desaparece

Aplicaciones

• Nearest neighbor queries
• Mesh generation (FEM)
• Facility location
• Motion planning

Visualización: Voronoi (Crecimiento de Regiones)

🔍 4.6 Geometric Search Structures

Point Location (Kirkpatrick)

Preprocessing: O(n), Space: O(n), Query: O(log n)

Range Searching

kd-Tree

1. Elegir eje de división alternando x, y
2. Encontrar mediana por esa coordenada O(n)
3. Recursión en dos mitades → árbol balanceado O(n log n)

Visualización: Particiones de un kd-Tree

struct KDNode {
    Point pt;
    KDNode *left, *right;
};

KDNode* build(vector<Point>& pts, int depth = 0) {
    if (pts.empty()) return nullptr;
    int axis = depth % 2;
    sort(pts.begin(), pts.end(), [axis](auto& a, auto& b) {
        return axis == 0 ? a.x < b.x : a.y < b.y;
    });
    int mid = pts.size() / 2;
    KDNode* node = new KDNode{pts[mid], nullptr, nullptr};
    vector<Point> left(pts.begin(), pts.begin() + mid);
    vector<Point> right(pts.begin() + mid + 1, pts.end());
    node->left = build(left, depth + 1);
    node->right = build(right, depth + 1);
    return node;
}

🎲 4.7 Algoritmos Randomizados

Seidel's Randomized 2D LP

Tiempo esperado: O(n)

Enfoque

1. Permutar constraints aleatoriamente
2. Agregar constraints incrementalmente
3. Si nueva constraint viola solución actual → resolver LP 1D en la línea boundary

Cada constraint causa violación con probabilidad ≤ 2/i

RANSAC (Computer Vision)

• Robust fitting bajo outliers
• Repetir N trials: sample minimal set, fit model, count inliers
• Iterations: N ≥ log(1-p) / log(1-w^s)

Monte Carlo π Estimation