Sprawdzanie wypukłości wielokąta w C: algorytm i implementacja

Algorytm sprawdzania wypukłości wielokąta w C: od teorii do stabilnej implementacji

Określenie wypukłości wielokąta to fundamentalne zadanie geometrii obliczeniowej, kluczowe dla silników gier, systemów nawigacji i grafiki komputerowej. Figury wypukłe są przetwarzane wydajniej, co sprawia, że sprawdzanie jest kluczowym etapem optymalizacji.

Geometryczne podstawy algorytmu

Wypukłość wielokąta jest określana przez kierunek kolejnych obrotów podczas omijania jego wierzchołków. Jeśli wszystkie obroty odbywają się w jedną stronę (w lewo lub w prawo), figura jest wypukła. Zmiana kierunku wskazuje na wklęsłość.

Kierunek obrotu jest obliczany dla każdej trójki sąsiednich punktów A, B, C przez znak iloczynu wektorowego:

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

• cross > 0 — obrót w lewo
• cross < 0 — obrót w prawo
• cross = 0 — punkty są współliniowe

To wyrażenie reprezentuje zorientowane pole równoległoboku zbudowanego na wektorach AB i AC. Znak określa, czy punkt C 'wznosi się' względem kierunku od A do B.

Implementacja podstawowych struktur danych

Praca zaczyna się od definicji struktur dla punktu i wielokąta. Pamięć dla wierzchołków jest alokowana dynamicznie, ponieważ ich liczba jest znana tylko podczas wykonywania.

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

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

Funkcje tworzenia i usuwania wielokąta zarządzają tą pamięcią:

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

Funkcja określania orientacji i problem przepełnienia

Kluczowa funkcja Orient oblicza iloczyn wektorowy. Użycie typu long long jest konieczne do zapobiegania przepełnieniu przy mnożeniu współrzędnych, ale nawet 64-bitowy typ ma ograniczenia.

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

Dla krytycznych aplikacji wymagana jest ochrona przed przepełnieniem. Implementacja z sprawdzaniem:

#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)) {
        // Obsługa przepełnienia: zwrot 0 konfliktuje z współliniowością
        // W praktyce należy ustawić flagę błędu lub użyć __int128
        printf("PRZEŁNIENIE\n");
        exit(1);
    }
    return p1 - p2;
}

Ważne: zwrot 0 przy przepełnieniu jest niepoprawny, ponieważ ta wartość również oznacza współliniowość. W ścisłej implementacji należy użyć oddzielnej flagi błędu lub rozszerzonego typu danych.

Algorytm sprawdzania wypukłości

Główna funkcja IsConvex kolejno sprawdza znak iloczynu wektorowego dla wszystkich trójek wierzchołków. Zmienna sign zapamiętuje kierunek pierwszego niezerowego obrotu.

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; // Ignorujemy punkty współliniowe
        if (sign == 0) {
            sign = (cross > 0) ? 1 : -1; // Fiksujemy pierwszy kierunek
        } else if ((cross > 0 && sign < 0) || (cross < 0 && sign > 0)) {
            return 0; // Kierunek się zmienił — wielokąt nie jest wypukły
        }
    }
    return 1; // Wszystkie obroty w jedną stronę
}

Kluczowe cechy implementacji:

• Użycie % p->n zapewnia cykliczne omijanie wierzchołków.
• Punkty współliniowe (cross == 0) są pomijane, co jest poprawne dla wielokątów z prostymi odcinkami.
• Algorytm ma liniową złożoność O(n) i wymaga stałej pamięci.

Pełny przykład programu

Następujący kod demonstruje kompletne aplikacje do analizy wielokątów odczytanych ze standardowego wejścia.

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

// Struktury i funkcje określania orientacji (jak powyżej)
// ...

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("BŁĄD WEJŚCIA: wymagane minimum 3 wierzchołki\n");
        return 1;
    }
    Polygon *p = CreatePolygon(n);
    if (!p) {
        printf("BŁĄD PAMIĘCI\n");
        return 1;
    }
    if (!ReadPolygon(p)) {
        printf("BŁĄD WEJŚCIA: niepoprawne współrzędne\n");
        DestroyPolygon(p);
        return 1;
    }
    printf(IsConvex(p) ? "WYPUKŁY\n" : "NIE WYPUKŁY\n");
    DestroyPolygon(p);
    return 0;
}

Praktyczne aspekty i ograniczenia

Algorytm zakłada, że wierzchołki są podane w kolejności omijania (zgodnie lub przeciwnie do ruchu wskazówek zegara) i że wielokąt jest prosty (bez samoprzecięć).

Co jest ważne:

• Poprawność przy współliniowości: Pomijanie punktów z cross == 0 jest poprawne dla wypukłych wielokątów z prostymi odcinkami, ale może maskować błędy wejścia.
• Obsługa przepełnienia: W kodzie produkcyjnym konieczne jest użycie ochronnego mnożenia lub rozszerzonych typów (__int128), szczególnie przy dużych współrzędnych.
• Wydajność: Algorytm jest optymalny czasowo (O(n)), ale OrientSafe z sprawdzaniami spowalnia obliczenia. Wybór implementacji zależy od zakresu danych wejściowych.
• Zastosowalność: Metoda jest odpowiednia dla 2D-wielokątów. W 3D wymagane jest sprawdzenie wypukłości każdego wielokąta granicznego lub analiza znaku objętości.
• Alternatywne podejścia: Dla niektórych zadań bardziej efektywne jest użycie gotowych bibliotek (CGAL, Boost.Geometry) lub przyspieszenia sprzętowego.

— Editorial Team