Polygon-Konvexitätsprüfung in C: Algorithmus und Implementierung

Konvexpolygon-Check in C: Von der Theorie zur robusten Umsetzung

Die Überprüfung, ob ein Polygon konvex ist, ist eine zentrale Aufgabe der Computergeometrie und unverzichtbar für Spiele-Engines, Navigationssysteme und Computergrafik. Konvexe Formen lassen sich schneller verarbeiten, weshalb dieser Check ein entscheidender Optimierungsschritt ist.

Geometrische Grundlage des Algorithmus

Die Konvexität eines Polygons ergibt sich aus der Richtung der Wendungen beim Durchlaufen der Ecken. Sind alle Wendungen gleichsinnig (links oder rechts), ist es konvex. Eine Richtungsänderung bedeutet, es ist konkav.

Die Wendungsrichtung wird für je drei aufeinanderfolgende Punkte A, B, C über das Vorzeichen des Kreuzprodukts berechnet:

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

• cross > 0 — Linkswendung
• cross < 0 — Rechtswendung
• cross = 0 — Punkte sind kollinear

Diese Formel liefert die signierte Fläche des von den Vektoren AB und AC aufgespannten Parallelogramms. Das Vorzeichen zeigt, ob Punkt C "über" oder "unter" der Richtung von A nach B liegt.

Grundlegende Datenstrukturen

Wir beginnen mit Strukturen für Punkte und Polygone. Die Ecken werden dynamisch alloziert, da die Anzahl zur Laufzeit erst bekannt ist.

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

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

Funktionen für Erstellung und Freigabe verwalten diesen Speicher:

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

Orientierungsfunktion und Überlaufprobleme

Die zentrale Orient-Funktion berechnet das Kreuzprodukt. long long verhindert Überläufe bei Koordinatenmultiplikationen, doch auch 64-Bit-Typen haben Grenzen.

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

Für sicherheitskritische Anwendungen Überlauf-Schutz hinzufügen:

#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)) {
        // Überlaufbehandlung: 0 kollidiert mit Kollinearität
        // Praxis: Fehlerflag setzen oder __int128 nutzen
        printf("ÜBERLAUF\n");
        exit(1);
    }
    return p1 - p2;
}

Wichtig: Bei Überlauf 0 zurückzugeben ist falsch, da es auch Kollinearität bedeutet. In strengem Code Fehlerflag oder breitere Typen verwenden.

Konvexitätsprüfungsalgorithmus

Die Hauptfunktion IsConvex überprüft das Kreuzprodukts-Vorzeichen für alle Ecken-Tripel. sign merkt sich die erste nicht-null Wendungsrichtung.

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; // Kollineare Punkte überspringen
        if (sign == 0) {
            sign = (cross > 0) ? 1 : -1; // Erste Richtung merken
        } else if ((cross > 0 && sign < 0) || (cross < 0 && sign > 0)) {
            return 0; // Richtung geändert — nicht konvex
        }
    }
    return 1; // Alle Wendungen gleichsinnig
}

Wichtige Umsetzungsmerkmale:

• % p->n sorgt für zyklischen Durchlauf.
• Kollineare Punkte (cross == 0) werden übersprungen, was bei Polygonen mit geraden Abschnitten passt.
• O(n)-Zeitkomplexität, konstanter Zusatzspeicher.

Vollständiges Programmbeispiel

Dieser Code zeigt eine komplette Anwendung, die Polygone aus stdin liest und analysiert.

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

// Strukturen und Orientierungsfunktionen (wie oben)
// ...

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("EINGABEFEHLER: Mindestens 3 Ecken erforderlich\n");
        return 1;
    }
    Polygon *p = CreatePolygon(n);
    if (!p) {
        printf("SPEICHERFEHLER\n");
        return 1;
    }
    if (!ReadPolygon(p)) {
        printf("EINGABEFEHLER: Ungültige Koordinaten\n");
        DestroyPolygon(p);
        return 1;
    }
    printf(IsConvex(p) ? "KONVEX\n" : "NICHT KONVEX\n");
    DestroyPolygon(p);
    return 0;
}

Praktische Hinweise und Einschränkungen

Der Algorithmus setzt voraus, dass die Ecken in Reihenfolge (im Uhrzeigersinn oder gegen) angegeben sind und das Polygon einfach ist (keine Selbstüberschneidungen).

Wichtige Punkte:

• Kollinearitätsbehandlung: Überspringen von cross == 0 funktioniert bei konvexen Polygonen mit geraden Kanten, kann aber Eingabefehler kaschieren.
• Überlaufschutz: Produktionscode braucht sichere Multiplikation oder __int128, besonders bei großen Koordinaten.
• Leistung: Basisalgorithmus ist optimal O(n), OrientSafe bremst durch Checks. Je nach Eingabebereich wählen.
• Anwendbarkeit: Nur für 2D-Polygone. 3D erfordert Flächenprüfungen oder Volumenzeichenanalyse.
• Alternativen: Bibliotheken wie CGAL oder Boost.Geometry für Komplexfälle oder GPU-Beschleunigung nutzen.

— Editorial Team