Vérification de la Convexité de Polygone en C : Algorithme et Implémentation

Vérification de polygone convexe en C : de la théorie à l'implémentation robuste

Vérifier si un polygone est convexe est une tâche fondamentale en géométrie computationnelle, indispensable pour les moteurs de jeux, les systèmes de navigation et l'infographie. Les formes convexes se traitent plus rapidement, rendant cette vérification une étape d'optimisation clé.

Fondements géométriques de l'algorithme

La convexité d'un polygone se détermine par la direction des virages en parcourant ses sommets. Si tous les virages vont dans le même sens (à gauche ou à droite), il est convexe. Un changement de direction indique qu'il est concave.

La direction du virage se calcule pour chaque triplet consécutif de points A, B, C à l'aide du signe du produit vectoriel :

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

• cross > 0 — virage à gauche
• cross < 0 — virage à droite
• cross = 0 — points alignés

Cette formule donne l'aire signée du parallélogramme formé par les vecteurs AB et AC. Le signe indique si le point C est « au-dessus » ou « en-dessous » de la direction de A vers B.

Structures de données de base

On commence par des structures pour les points et les polygones. Les sommets sont alloués dynamiquement car leur nombre n'est connu qu'à l'exécution.

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

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

Les fonctions de création et de destruction gèrent cette mémoire :

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);
}

Fonction d'orientation et problèmes de débordement

La fonction clé Orient calcule le produit vectoriel. L'utilisation de long long évite les débordements lors des multiplications de coordonnées, mais même les types 64 bits ont des limites.

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);
}

Pour les applications critiques, ajoutez une protection contre les débordements :

#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)) {
        // Gestion du débordement : retourner 0 entre en conflit avec l'alignement
        // En pratique, définir un drapeau d'erreur ou utiliser __int128
        printf("DÉBORDEMENT\n");
        exit(1);
    }
    return p1 - p2;
}

Important : Retourner 0 en cas de débordement est incorrect car cela signifie aussi alignement. Utilisez un drapeau d'erreur ou des types plus larges dans du code strict.

Algorithme de vérification de convexité

La fonction principale IsConvex vérifie le signe du produit vectoriel pour tous les triplets de sommets. sign suit la première direction de virage non nulle.

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; // Ignorer les points alignés
        if (sign == 0) {
            sign = (cross > 0) ? 1 : -1; // Verrouiller la première direction
        } else if ((cross > 0 && sign < 0) || (cross < 0 && sign > 0)) {
            return 0; // Changement de direction — non convexe
        }
    }
    return 1; // Tous les virages dans la même direction
}

Points clés de l'implémentation :

• % p->n permet le parcours cyclique.
• Les points alignés (cross == 0) sont ignorés, ce qui convient aux polygones avec des segments droits.
• Complexité temporelle O(n), espace constant supplémentaire.

Exemple de programme complet

Ce code présente une application complète qui lit des polygones depuis l'entrée standard et les analyse.

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

// Structures et fonctions d'orientation (comme ci-dessus)
// ...

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("ERREUR Saisie : au moins 3 sommets requis\n");
        return 1;
    }
    Polygon *p = CreatePolygon(n);
    if (!p) {
        printf("ERREUR MÉMOIRE\n");
        return 1;
    }
    if (!ReadPolygon(p)) {
        printf("ERREUR Saisie : coordonnées invalides\n");
        DestroyPolygon(p);
        return 1;
    }
    printf(IsConvex(p) ? "CONVEXE\n" : "NON CONVEXE\n");
    DestroyPolygon(p);
    return 0;
}

Considérations pratiques et limites

L'algorithme suppose que les sommets sont dans l'ordre de parcours (sens horaire ou antihoraire) et que le polygone est simple (sans auto-intersections).

Points clés :

• Gestion de l'alignement : Ignorer cross == 0 fonctionne pour les polygones convexes avec des arêtes droites mais peut masquer des erreurs de saisie.
• Protection contre débordement : Le code de production nécessite une multiplication sécurisée ou __int128, surtout pour de grandes coordonnées.
• Performance : L'algorithme de base est optimal en O(n), mais OrientSafe ajoute des vérifications qui le ralentissent. Choisissez selon la plage d'entrée.
• Applicabilité : Uniquement pour les polygones 2D. En 3D, il faut vérifier les faces ou analyser le signe du volume.
• Alternatives : Utilisez des bibliothèques comme CGAL ou Boost.Geometry pour les cas complexes, ou l'accélération GPU.

— Editorial Team