Kontrola konvexnosti mnohoúhelníku v C: algoritmus a implementace

Algoritmus pro kontrolu konvexnosti mnohoúhelníku v C: od teorie k robustní implementaci

Definice konvexnosti mnohoúhelníku je základní úlohou výpočetní geometrie, klíčovou pro herní enginy, navigační systémy a počítačovou grafiku. Konvexní tvary se zpracovávají efektivněji, což z toho činí kontrolu klíčovým krokem optimalizace.

Geometrický základ algoritmu

Konvexnost mnohoúhelníku je určena směrem po sobě jdoucích otočení při procházení jeho vrcholů. Pokud všechna otočení probíhají jedním směrem (doleva nebo doprava), tvar je konvexní. Změna směru indikuje konkávnost.

Směr otočení se vypočítá pro každou trojici sousedních bodů A, B, C pomocí znaménka vektorového součinu:

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

• cross > 0 — otočení doleva
• cross < 0 — otočení doprava
• cross = 0 — body jsou kolineární

Tento výraz představuje orientovanou plochu rovnoběžníku postaveného na vektorech AB a AC. Znaménko určuje, zda se bod C „zvedá“ vzhledem ke směru od A k B.

Implementace základních datových struktur

Práce začíná definicí struktur pro bod a mnohoúhelník. Paměť pro vrcholy je alokována dynamicky, protože jejich počet je znám až za běhu programu.

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

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

Funkce pro vytvoření a odstranění mnohoúhelníku spravují tuto paměť:

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

Funkce pro určení orientace a problém přetečení

Klíčová funkce Orient vypočítává vektorový součin. Použití typu long long je nutné pro prevenci přetečení při násobení souřadnic, ale i 64bitový typ má omezení.

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

Pro kritické aplikace je vyžadována ochrana proti přetečení. Implementace s kontrolou:

#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)) {
        // Zpracování přetečení: vrácení 0 by bylo v rozporu s kolinearitou
        // V praxi by se měl nastavit příznak chyby nebo použít __int128
        printf("PŘETECENÍ\n");
        exit(1);
    }
    return p1 - p2;
}

Důležité: vrácení 0 při přetečení není správné, protože tato hodnota také označuje kolinearitu. V přísné implementaci by se měl použít samostatný příznak chyby nebo rozšířený datový typ.

Algoritmus kontroly konvexnosti

Hlavní funkce IsConvex postupně kontroluje znaménko vektorového součinu pro všechny trojice vrcholů. Proměnná sign si pamatuje směr prvního nenulového otočení.

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; // Ignorujeme kolineární body
        if (sign == 0) {
            sign = (cross > 0) ? 1 : -1; // Fixujeme první směr
        } else if ((cross > 0 && sign < 0) || (cross < 0 && sign > 0)) {
            return 0; // Směr se změnil — mnohoúhelník není konvexní
        }
    }
    return 1; // Všechna otočení jedním směrem
}

Klíčové vlastnosti implementace:

• Použití % p->n zajišťuje cyklické procházení vrcholů.
• Kolineární body (cross == 0) jsou přeskočeny, což je správné pro mnohoúhelníky s rovnými úseky.
• Algoritmus má lineární složitost O(n) a vyžaduje konstantní paměť.

Úplný příklad programu

Následující kód demonstruje hotovou aplikaci pro analýzu mnohoúhelníků načtených ze standardního vstupu.

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

// Struktury a funkce pro určení orientace (jak výše)
// ...

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("VSTUPNÍ CHYBA: je vyžadováno alespoň 3 vrcholy\n");
        return 1;
    }
    Polygon *p = CreatePolygon(n);
    if (!p) {
        printf("PAMĚŤOVÁ CHYBA\n");
        return 1;
    }
    if (!ReadPolygon(p)) {
        printf("VSTUPNÍ CHYBA: nekorektní souřadnice\n");
        DestroyPolygon(p);
        return 1;
    }
    printf(IsConvex(p) ? "KONVEXNÍ\n" : "NEKONVEXNÍ\n");
    DestroyPolygon(p);
    return 0;
}

Praktické aspekty a omezení

Algoritmus předpokládá, že vrcholy jsou zadány v pořadí procházení (po nebo proti směru hodinových ručiček) a že mnohoúhelník je jednoduchý (bez sebeprotínání).

Co je důležité:

• Správnost při kolinearitě: Přeskočení bodů s cross == 0 je správné pro konvexní mnohoúhelníky s rovnými segmenty, ale může maskovat chyby ve vstupu.
• Zpracování přetečení: V produkčním kódu je nutné používat chráněné násobení nebo rozšířené typy (__int128), zvláště při velkých souřadnicích.
• Výkon: Algoritmus je optimální časově (O(n)), ale OrientSafe s kontrolami zpomaluje výpočty. Volba implementace závisí na rozsahu vstupních dat.
• Použitelnost: Metoda je vhodná pro 2D mnohoúhelníky. V 3D je potřeba kontrola konvexnosti každého ohraničujícího mnohoúhelníku nebo analýza znamének objemů.
• Alternativní přístupy: Pro některé úlohy je efektivnější používat hotové knihovny (CGAL, Boost.Geometry) nebo hardwarové zrychlení.

— Editorial Team