Comprobación de Convexidad de Polígono en C: Algoritmo e Implementación

# Verificación de Polígono Convexo en C: De la Teoría a una Implementación Robusta

Verificar si un polígono es convexo es una tarea fundamental en geometría computacional, esencial para motores de juegos, sistemas de navegación y gráficos por computadora. Las formas convexas se procesan más rápido, lo que hace de esta verificación un paso clave de optimización.

Fundamentos Geométricos del Algoritmo

La convexidad de un polígono se determina por la dirección de los giros al recorrer sus vértices. Si todos los giros van en la misma dirección (izquierda o derecha), es convexo. Un cambio de dirección indica que es cóncavo.

La dirección del giro se calcula para cada tres puntos consecutivos A, B, C mediante el signo del producto vectorial:

cross = (B.x - A.x)(C.y - A.y) - (B.y - A.y)(C.x - A.x)

• cross > 0 — giro a la izquierda
• cross < 0 — giro a la derecha
• cross = 0 — puntos colineales

Esta fórmula da el área firmada del paralelogramo formado por los vectores AB y AC. El signo indica si el punto C está "por encima" o "por debajo" de la dirección de A a B.

Estructuras de Datos Básicas

Empezamos con estructuras para puntos y polígonos. Los vértices se asignan dinámicamente ya que el número solo se conoce en tiempo de ejecución.

typedef struct {
    int x;
    int y;
} Point;

typedef struct {
    Point *vertices;
    int n;
} Polygon;

Las funciones de creación y destrucción gestionan esta memoria:

Polygon* CreatePolygon(int n) {
    Polygon *p = malloc(sizeof(Polygon));
    if (!p) return NULL;
    p->n = n;
    p->vertices = malloc(n * sizeof(Point));
    if (!p->vertices) {
        free(p);
        return NULL;
    }
    return p;
}

void DestroyPolygon(Polygon *p) {
    if (!p) return;
    free(p->vertices);
    free(p);
}

Función de Orientación y Problemas de Desbordamiento

La función clave Orient calcula el producto vectorial. Usar long long evita desbordamientos en multiplicaciones de coordenadas, pero incluso los tipos de 64 bits tienen límites.

long long Orient(Point a, Point b, Point c) {
    return (long long)(b.x - a.x) * (c.y - a.y) -
           (long long)(b.y - a.y) * (c.x - a.x);
}

Para aplicaciones críticas, añade protección contra desbordamiento:

#include <limits.h>

int SafeMul(long long a, long long b, long long *res) {
    if (a > 0 && b > 0 && a > LLONG_MAX / b) return 0;
    if (a > 0 && b < 0 && b < LLONG_MIN / a) return 0;
    if (a < 0 && b > 0 && a < LLONG_MIN / b) return 0;
    if (a < 0 && b < 0 && a < LLONG_MAX / b) return 0;
    *res = a * b;
    return 1;
}

long long OrientSafe(Point a, Point b, Point c) {
    long long p1, p2;
    if (!SafeMul((long long)b.x - a.x, (long long)c.y - a.y, &p1) ||
        !SafeMul((long long)b.y - a.y, (long long)c.x - a.x, &p2)) {
        // Manejo de desbordamiento: devolver 0 choca con colinealidad
        // En la práctica, usa una bandera de error o __int128
        printf("DESBORDAMIENTO\n");
        exit(1);
    }
    return p1 - p2;
}

Importante: Devolver 0 en desbordamiento es erróneo ya que también significa colineal. Usa una bandera de error o tipos más amplios en código estricto.

Algoritmo de Verificación de Convexidad

La función principal IsConvex verifica el signo del producto vectorial para todos los tripletes de vértices. sign rastrea la primera dirección de giro no cero.

int IsConvex(const Polygon *p) {
    int sign = 0;
    for (int i = 0; i < p->n; i++) {
        Point a = p->vertices[i];
        Point b = p->vertices[(i + 1) % p->n];
        Point c = p->vertices[(i + 2) % p->n];
        long long cross = Orient(a, b, c);
        if (cross == 0) continue; // Saltar puntos colineales
        if (sign == 0) {
            sign = (cross > 0) ? 1 : -1; // Fijar primera dirección
        } else if ((cross > 0 && sign < 0) || (cross < 0 && sign > 0)) {
            return 0; // Cambio de dirección — no convexo
        }
    }
    return 1; // Todos los giros en misma dirección
}

Características clave de la implementación:

• % p->n permite el recorrido cíclico.
• Puntos colineales (cross == 0) se saltan, válido para polígonos con tramos rectos.
• Complejidad temporal O(n), espacio extra constante.

Ejemplo de Programa Completo

Este código muestra una aplicación completa que lee polígonos desde stdin y los analiza.

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

// Estructuras y funciones de orientación (como arriba)
// ...

int ReadPolygon(Polygon *p) {
    for (int i = 0; i < p->n; i++) {
        if (scanf("%d %d", &p->vertices[i].x, &p->vertices[i].y) != 2) return 0;
    }
    return 1;
}

int main() {
    int n;
    if (scanf("%d", &n) != 1 || n < 3) {
        printf("ERROR DE ENTRADA: se necesitan al menos 3 vértices\n");
        return 1;
    }
    Polygon *p = CreatePolygon(n);
    if (!p) {
        printf("ERROR DE MEMORIA\n");
        return 1;
    }
    if (!ReadPolygon(p)) {
        printf("ERROR DE ENTRADA: coordenadas inválidas\n");
        DestroyPolygon(p);
        return 1;
    }
    printf(IsConvex(p) ? "CONVEXO\n" : "NO CONVEXO\n");
    DestroyPolygon(p);
    return 0;
}

Consideraciones Prácticas y Limitaciones

El algoritmo asume que los vértices están en orden de recorrido (sentido horario o antihorario) y que el polígono es simple (sin autointersecciones).

Puntos clave:

• Manejo de colinealidad: Saltar cross == 0 funciona para polígonos convexos con aristas rectas, pero podría ocultar errores de entrada.
• Protección contra desbordamiento: El código de producción necesita multiplicación segura o __int128, sobre todo con coordenadas grandes.
• Rendimiento: El algoritmo base es O(n) óptimo, pero OrientSafe añade verificaciones que lo ralentizan. Elige según el rango de entrada.
• Aplicabilidad: Solo para polígonos 2D. En 3D se necesitan verificaciones de caras o análisis de signo de volumen.
• Alternativas: Usa librerías como CGAL o Boost.Geometry para casos complejos, o aceleración GPU.

— Editorial Team