Zadania z geometrii analitycznej, które świetnie nadają się do kodowania

Czym są zadania z geometrii analitycznej idealne do kodowania?

Geometria analityczna jako poligon doświadczalny dla programisty

Geometria analityczna to część matematyki, która opisuje obiekty geometryczne za pomocą równań, współrzędnych i wektorów. Dla programisty to złote połączenie: świat wizualny (punkty, proste, odcinki, okręgi) da się opisać prostymi strukturami danych i kilkoma wzorami. Z tych wzorów bardzo naturalnie powstają algorytmy, które można zaimplementować w dowolnym języku programowania.

Zadania z geometrii analitycznej świetnie nadają się do kodowania z kilku powodów. Po pierwsze, są bardzo konkretne: masz dane wejściowe (np. współrzędne punktów), operujesz na nich kilkoma dobrze znanymi algorytmami (np. sprawdzenie położenia punktu względem prostej) i otrzymujesz odpowiedź, którą łatwo zweryfikować. Po drugie, wiele z tych zadań ma bezpośrednie zastosowania w grafice komputerowej, grach, robotyce czy analizie danych przestrzennych. Po trzecie, te same schematy obliczeniowe powtarzają się w bardzo wielu problemach, więc raz napisane funkcje można używać wielokrotnie.

Z punktu widzenia nauki algorytmiki zadania z geometrii analitycznej uczą myślenia o błędach numerycznych (liczby zmiennoprzecinkowe), projektowania struktur danych (punkt, wektor, odcinek) oraz dekompozycji problemu: najpierw rozwiązuje się małe podzadania (np. iloczyn skalarny), a dopiero z nich składa się większe funkcje (np. sprawdzenie przecięcia odcinków). Kod jest stosunkowo krótki, a mimo to wymaga precyzji, dzięki czemu dobrze ćwiczy rzemiosło programistyczne.

Jakie cechy mają zadania „przyjazne” kodowaniu?

Nie każde zadanie geometryczne jest wygodne do kodowania na początku nauki. Dobre zadania z geometrii analitycznej do implementacji w kodzie mają kilka wspólnych cech:

• Jasne dane wejściowe – zazwyczaj współrzędne w postaci liczb rzeczywistych lub całkowitych.
• Proste struktury danych – wystarczy punkt, odcinek, wektor, czasem prosta lub okrąg.
• Jednoznaczne warunki logiczne – decyzje typu: „punkt leży na prostej / poza prostą”, „odcinki się przecinają / nie przecinają”, „trójkąt istnieje / jest prostokątny / równoramienny”.
• Możliwość wizualizacji – rezultat można łatwo narysować lub zwizualizować w prostym programie.
• Rozsądna złożoność obliczeniowa – klasyczne zadania punktowe i odcinkowe da się rozwiązać w czasie liniowym lub kwadratowym.

Jeśli warunki zadania są niejednoznaczne, opis zbyt słowny lub wymaga zbyt skomplikowanego modelu (np. geometria sferyczna bez dobrego przygotowania), implementacja szybko zmienia się w walkę z założeniami. Dlatego dobrym punktem startu są klasyczne zadania: odległości, iloczyny skalarne, położenie punktu, przecięcia odcinków, własności trójkątów czy wielokąty wypukłe.

Podstawowe typy zadań z geometrii analitycznej

Najbardziej „kodowalne” zadania z geometrii analitycznej można pogrupować według obiektów, którymi się zajmują. Taki podział ułatwia też projektowanie struktury kodu i modułów w projekcie.

• Zadania punktowe – obliczanie odległości, transformacje punktów, położenie względem prostej czy odcinka.
• Zadania odcinkowe i proste – sprawdzanie przecięcia, kąty między prostymi, rzutowanie punktu na prostą, znajdowanie odległości punkt–prosta i odcinek–odcinek.
• Zadania z wielokątami – sprawdzenie, czy punkt leży w wielokącie, obliczanie pola, obwodu, konstrukcja otoczki wypukłej.
• Zadania z okręgami – odległości punkt–okrąg, położenie odcinka względem okręgu, wspólne punkty dwóch okręgów.
• Transformacje geometryczne – rotacje, przesunięcia, skalowania, odbicia, które świetnie mapują się na macierze i wektory.

Każda z tych grup zawiera zadania o rosnącej trudności. Można zacząć od prostych funkcji typu „oblicz długość odcinka”, a dojść do projektów na poziomie konkursów programistycznych: wykrywanie przecięć wielu odcinków, triangulacja wielokąta czy algorytmy diagramów Voronoi.

Reprezentacja obiektów geometrycznych w kodzie

Punkty i wektory jako podstawowe struktury danych

Serce zadań z geometrii analitycznej to punkt. W prawie każdym języku programowania pojawi się struktura (lub klasa) reprezentująca punkt na płaszczyźnie:

// przykład w stylu C++/Java
struct Point {
    double x;
    double y;
};

W praktyce ten sam typ danych używa się często zarówno jako punkt, jak i wektor. Dwa pola (x, y) wystarczają, aby reprezentować:

• pozycję punktu w układzie współrzędnych,
• wektor przesunięcia między dwoma punktami,
• normalę do prostej (jako wektor prostopadły).

Najwygodniej jest od razu przygotować zestaw podstawowych operacji wektorowych jako funkcje, które będą wykorzystywane w kolejnych zadaniach.

Operacje na wektorach w praktyce kodowania

Najczęściej używane operacje wektorowe w zadaniach z geometrii analitycznej, które świetnie nadają się do kodowania, to:

• dodawanie i odejmowanie wektorów (punktów),
• mnożenie przez skalar,
• iloczyn skalarny,
• iloczyn wektorowy w 2D (pseudowektorowy),
• długość wektora i normalizacja.

Przykładowy zestaw funkcji:

Point add(Point a, Point b) {
    return {a.x + b.x, a.y + b.y};
}

Point sub(Point a, Point b) {
    return {a.x - b.x, a.y - b.y};
}

Point mul(Point a, double k) {
    return {a.x * k, a.y * k};
}

double dot(Point a, Point b) { // iloczyn skalarny
    return a.x * b.x + a.y * b.y;
}

double cross(Point a, Point b) { // iloczyn wektorowy 2D
    return a.x * b.y - a.y * b.x;
}

double length(Point a) {
    return sqrt(dot(a, a));
}

Dzięki takim pomocniczym funkcjom kod zadań z geometrii analitycznej staje się krótszy i czytelniejszy. Zamiast rozwijać za każdym razem wzór, pisze się po prostu dot(u, v) czy cross(AB, AC). To sprzyja zarówno mniejszej liczbie błędów, jak i łatwiejszemu przenoszeniu kodu między językami.

Proste, odcinki, okręgi – jak je zaprojektować w strukturach?

Oprócz punktów i wektorów w kodzie często pojawiają się także:

• prosta,
• odcinek,
• okrąg,
• czasem również wielokąt.

Najwygodniejsza reprezentacja tych obiektów zależy od typu zadań. Przykładowe, praktyczne modele danych mogą wyglądać tak:

struct Segment {
    Point a;
    Point b;
};

struct Line { // prosta w postaci ogólnej: Ax + By + C = 0
    double A, B, C;
};

struct Circle {
    Point center;
    double r;
};

struct Polygon {
    std::vector<Point> v;
};

Prostą można reprezentować na kilka sposobów: równanie ogólne Ax + By + C = 0, punkt + wektor kierunkowy, dwie różne postaci parametryczne. W zadaniach programistycznych często wygodnie jest trzymać prostą jako punkt + wektor normalny lub po prostu dwa punkty (jak odcinek), bo wtedy łatwo odpowiadać na pytania typu: „czy punkt leży na prostej?”, „jaki jest kierunek prostej?”. Dla równań przecięcia prostych z kolei równanie ogólne bywa praktyczne. Warto przetestować różne modele w małych projektach.

Najprostsze zadania: punkty, odległości, wektory

Odległość między punktami jako funkcja bazowa

Najprostszy i jednocześnie bardzo często wykorzystywany typ zadania: oblicz odległość między dwoma punktami w układzie współrzędnych. Wzór jest klasyczny:

d(P, Q) = √((x₂ – x₁)² + (y₂ – y₁)²)

W kodzie najczęściej implementuje się pomocniczą funkcję:

double dist(Point a, Point b) {
    return length(sub(a, b));
    // lub bezpośrednio:
    // double dx = a.x - b.x;
    // double dy = a.y - b.y;
    // return sqrt(dx*dx + dy*dy);
}

Na tej jednej funkcji da się zbudować dziesiątki prostych, ale bardzo użytecznych zadań: znalezienie najbliższego punktu z listy, obliczenie obwodu trójkąta, suma długości odcinków łamanej czy sprawdzenie, czy punkt leży w zadanym promieniu od innego punktu (wyszukiwanie w promieniu w grach lub aplikacjach mapowych).

Iloczyn skalarny i kąt między wektorami

Iloczyn skalarny wektorów w geometrii analitycznej daje prosty sposób na obliczanie kąta między odcinkami. Jeśli mamy wektory u i v, to:

u · v = |u| · |v| · cos(α)

Stąd:

cos(α) = (u · v) / (|u| · |v|)

W praktyce w kodzie rzadko oblicza się sam kąt (czyli acos), bo jest to względnie kosztowne obliczeniowo i wprowadza dodatkowe błędy numeryczne. Dużo lepsze są porównania bezpośrednio na iloczynie skalarnym, np.:

• wektory są prostopadłe ⇔ dot(u, v) == 0 (z tolerancją na błąd),
• wektory tworzą kąt ostry ⇔ dot(u, v) > 0,
• wektory tworzą kąt rozwarty ⇔ dot(u, v) < 0.

Dzięki temu można rozwiązywać zadania typu:

• sprawdzenie, czy trójkąt jest prostokątny (test prostopadłości boków),
• wykrywanie „skrętu w lewo/prawo” w zadaniach z wielokątami (w połączeniu z iloczynem wektorowym),
• sprawdzanie, czy dany punkt na odcinku jest „pomiędzy” innymi punktami wzdłuż tej samej linii.

Iloczyn wektorowy w 2D jako narzędzie decyzyjne

Choć w przestrzeni 2D „pełny” iloczyn wektorowy nie istnieje, w geometrii analitycznej stosuje się tzw. pseudowektorowy iloczyn wektorowy:

cross(u, v) = u_x · v_y – u_y · v_x

Wynik to liczba skalarna. Interpretacja jest bardzo użyteczna:

• cross(u, v) > 0 – skręt z u do v w lewo (przeciwnie do ruchu wskazówek zegara),
• cross(u, v) < 0 – skręt w prawo,
• cross(u, v) = 0 – wektory współliniowe.

Dzięki temu w zadaniach z geometrii analitycznej można bardzo elegancko decydować o:

• położeniu punktu względem prostej (po lewej / po prawej / na prostej),
• kolejności wierzchołków wielokąta (w lewo lub w prawo),
• sprawdzaniu przecięcia odcinków (znak kolejnych iloczynów wektorowych).

W zadaniach programistycznych iloczyn wektorowy 2D pojawia się tak często, że przeważnie ma osobną krótką funkcję, jak pokazano w poprzedniej sekcji. Większość algorytmów operujących na wielokątach, otoczkach wypukłych i przecięciach segmentów opiera się właśnie na porównywaniu znaków cross.

Położenie punktu względem prostej, odcinka i wielokąta

Test położenia punktu względem prostej z użyciem iloczynu wektorowego

Zadanie: dany jest punkt P i prosta przechodząca przez punkty A i B. Określ, czy P leży po lewej, po prawej stronie prostej, czy na niej. To klasyczny kandydat na zadanie, które świetnie nadaje się do kodowania.

Wektorowo można to zapisać:

• wektor AB = B – A,
• wektor AP = P – A,

Implementacja testu strony i współliniowości w kodzie

Konkretna implementacja testu położenia punktu względem prostej opiera się bezpośrednio na iloczynie wektorowym. Skoro mamy już funkcję cross, wystarczy zbudować wektory AB i AP:

int orientation(Point A, Point B, Point P) {
    // zwraca:
    //  0  - gdy punkty są współliniowe
    // >0 - gdy P leży po lewej stronie wektora AB
    // <0 - gdy P leży po prawej stronie wektora AB
    double val = cross(sub(B, A), sub(P, A));
    const double EPS = 1e-9;
    if (fabs(val) < EPS) return 0;
    return (val > 0 ? 1 : -1);
}

Taka funkcja staje się szybko jednym z najczęściej wywoływanych fragmentów kodu w zadaniach z geometrii. Na niej można oprzeć nie tylko test strony, ale także sprawdzanie „skrętów” w algorytmach na wielokątach i otoczkach wypukłych.

Położenie punktu na odcinku – łączenie iloczynu skalarnego i wektorowego

Częsty wariant zadania: czy punkt P leży na odcinku AB? Tutaj sama współliniowość (iloczyn wektorowy równy zero) nie wystarcza, bo punkt może leżeć na przedłużeniu odcinka. Potrzebna jest także kontrola, czy P leży między A i B.

Praktyczna implementacja:

bool onSegment(Point A, Point B, Point P) {
    const double EPS = 1e-9;
    // 1. Współliniowość (P na prostej AB)
    if (fabs(cross(sub(B, A), sub(P, A))) > EPS)
        return false;
    // 2. Sprawdzenie, czy P leży w przedziale <A, B>
    //    użycie iloczynu skalarnego: (P-A) · (P-B) <= 0
    if (dot(sub(P, A), sub(P, B)) > EPS)
        return false;
    return true;
}

Ten prosty test pojawia się w bardzo wielu zadaniach: od wyznaczania przecięć odcinków, przez analizę łamanych, po obliczanie długości części wspólnej dwóch segmentów. Warto go mieć gotowego i dobrze przetestowanego.

Przecięcie dwóch odcinków jako pierwsze „większe” zadanie

Zadanie: sprawdź, czy dwa odcinki AB i CD mają punkt wspólny, a jeśli tak – wyznacz ten punkt. To klasyka zadań konkursowych i jednocześnie świetny pretekst do połączenia kilku pojęć: orientacji, współliniowości i rozwiązywania układu równań.

Sprawdzenie, czy odcinki się przecinają (przynajmniej w jednym punkcie), można zrealizować w dwóch krokach:

• test ogólny: odcinki „przecinają się jako proste” (orientacje mają różne znaki),
• testy brzegowe: przypadki współliniowe, gdy jeden koniec leży na drugim odcinku.

bool segmentsIntersect(Point A, Point B, Point C, Point D) {
    int o1 = orientation(A, B, C);
    int o2 = orientation(A, B, D);
    int o3 = orientation(C, D, A);
    int o4 = orientation(C, D, B);
    const double EPS = 1e-9;

    // Przypadek ogólny
    if (o1 != o2 && o3 != o4)
        return true;

    // Przypadki współliniowe (C, D leżą na prostej AB lub odwrotnie)
    if (o1 == 0 && onSegment(A, B, C)) return true;
    if (o2 == 0 && onSegment(A, B, D)) return true;
    if (o3 == 0 && onSegment(C, D, A)) return true;
    if (o4 == 0 && onSegment(C, D, B)) return true;

    return false;
}

Jeśli odcinki się przecinają i nie są współliniowe, punkt przecięcia można wyznaczyć rozwiązując układ równań prostych przechodzących przez AB i CD. Dobrze działa podejście parametryczne:

// Zakładamy, że odcinki nie są równoległe i nie są współliniowe.
Point intersectionPoint(Point A, Point B, Point C, Point D) {
    Point r = sub(B, A);
    Point s = sub(D, C);
    double rxs = cross(r, s);
    double t = cross(sub(C, A), s) / rxs;
    // Punkt: A + t * r
    return add(A, mul(r, t));
}

Już na takim przykładzie widać, jak wielokrotne użycie tych samych prostych funkcji wektorowych porządkuje kod i ułatwia późniejsze modyfikacje (np. dodanie tolerancji numerycznej).

Test punktu wewnątrz trójkąta – kilkanaście linii kodu

Naturalna kontynuacja: czy punkt P leży wewnątrz trójkąta ABC? Rozwiązań jest kilka. Jedno z najbardziej eleganckich opiera się na znakach iloczynów wektorowych.

Załóżmy, że wierzchołki trójkąta są w kolejności przeciwnie do ruchu wskazówek zegara. Punkt P leży wewnątrz, jeśli dla każdej z krawędzi skręt z krawędzi do wektora „wierzchołek → P” jest nieujemny (lub nie dodatni – w zależności od konwencji).

bool pointInTriangle(Point A, Point B, Point C, Point P) {
    const double EPS = 1e-9;
    double c1 = cross(sub(B, A), sub(P, A));
    double c2 = cross(sub(C, B), sub(P, B));
    double c3 = cross(sub(A, C), sub(P, C));

    bool hasNeg = (c1 < -EPS) || (c2 < -EPS) || (c3 < -EPS);
    bool hasPos = (c1 >  EPS) || (c2 >  EPS) || (c3 >  EPS);

    // Wewnętrznie lub na krawędzi, jeśli wszystkie mają ten sam znak lub 0
    return !(hasNeg && hasPos);
}

Ten sam pomysł można rozszerzyć na wielokąty wypukłe, a przy odpowiednich modyfikacjach – wykorzystać w dynamicznych strukturach danych (np. wyszukiwanie sektora w meshach czy szukanie trójkąta w triangulacji).

Wielokąty w praktyce programisty

Reprezentacja i podstawowe operacje na wielokątach

Wielokąt w kodzie to zwykle po prostu tablica lub wektor punktów. Z takiej struktury można w prosty sposób wyprowadzić podstawowe operacje: obliczanie obwodu, pola, sprawdzanie wypukłości.

Obwód:

double perimeter(const Polygon& poly) {
    double res = 0.0;
    int n = (int)poly.v.size();
    for (int i = 0; i < n; ++i) {
        Point a = poly.v[i];
        Point b = poly.v[(i + 1) % n];
        res += dist(a, b);
    }
    return res;
}

Pole wielokąta według wzoru „shoelace” (suma iloczynów krzyżowych kolejnych wierzchołków):

double area(const Polygon& poly) {
    int n = (int)poly.v.size();
    double s = 0.0;
    for (int i = 0; i < n; ++i) {
        Point a = poly.v[i];
        Point b = poly.v[(i + 1) % n];
        s += cross(a, b);
    }
    return fabs(s) / 2.0;
}

W wielu zastosowaniach (np. w grafice wektorowej czy mapach) stosuje się dodatni znak pola do odróżniania, czy wielokąt jest zadany zgodnie czy przeciwnie do ruchu wskazówek zegara.

Sprawdzanie wypukłości wielokąta

Kolejne zadanie „z półki”: sprawdź, czy zadany wielokąt prosty jest wypukły. Nietrudno je zamienić na kod, gdy w ręku są już iloczyny wektorowe. Wypukły wielokąt ma wszystkie skręty w tę samą stronę (przy założeniu, że wierzchołki są w spójnej kolejności).

bool isConvex(const Polygon& poly) {
    int n = (int)poly.v.size();
    if (n < 3) return false;
    const double EPS = 1e-9;

    int sign = 0; // 0 - nieustalony, 1 - dodatni, -1 - ujemny
    for (int i = 0; i < n; ++i) {
        Point A = poly.v[i];
        Point B = poly.v[(i + 1) % n];
        Point C = poly.v[(i + 2) % n];
        double val = cross(sub(B, A), sub(C, B));
        if (fabs(val) < EPS) continue; // współliniowe wierzchołki
        int cur = (val > 0 ? 1 : -1);
        if (sign == 0) sign = cur;
        else if (sign != cur) return false;
    }
    return true;
}

To zadanie dobrze sprawdza się jako ćwiczenie na testy brzegowe: wierzchołki współliniowe, wielokąty samoprzecinające się, różne kolejności punktów.

Punkt wewnątrz wielokąta – algorytm „ray casting”

Jedno z najpopularniejszych zadań: czy punkt P leży wewnątrz wielokąta (niekoniecznie wypukłego)? Klasyczne rozwiązanie to algorytm „przecinania promienia” (ray casting). Rzucamy z punktu P promień w jednym kierunku i liczymy, ile razy przecina krawędzie wielokąta.

• liczba przecięć nieparzysta → punkt wewnątrz,
• liczba przecięć parzysta → punkt na zewnątrz.

bool pointInPolygon(const Polygon& poly, Point P) {
    bool inside = false;
    int n = (int)poly.v.size();
    for (int i = 0, j = n - 1; i < n; j = i++) {
        Point A = poly.v[j];
        Point B = poly.v[i];

        // Sprawdzenie, czy punkt leży dokładnie na krawędzi
        if (onSegment(A, B, P))
            return true;

        bool intersect = ((A.y > P.y) != (B.y > P.y)) &&
                         (P.x < (B.x - A.x) * (P.y - A.y) / (B.y - A.y) + A.x);
        if (intersect)
            inside = !inside;
    }
    return inside;
}

To rozwiązanie można rozwijać: dodawać obsługę wielokątów z dziurami, optymalizacje przez struktury przestrzenne czy specjalne przypadki numeryczne. Na potrzeby większości konkursów i typowych zadań wystarczy jednak staranne zaimplementowanie powyższej wersji.



Otoczka wypukła – klasyczny projekt z geometrii i algorytmiki

Problem otoczki wypukłej i jego zastosowania

Otoczka wypukła zbioru punktów to najmniejszy wypukły wielokąt, który zawiera wszystkie te punkty. W praktyce przypomina „gumkę” naciągniętą na punkty. Z perspektywy kodowania to jedno z najwdzięczniejszych zadań:

• algorytm jest stosunkowo prosty do zaimplementowania,
• łatwo wizualizować wynik (np. prostym rysunkiem),
• występuje w wielu zastosowaniach: grafika, analiza kształtów, GIS, fizyka gier.

Popularny i wygodny do implementacji jest algorytm otoczki wypukłej Andrew (tzw. monotonic chain).

Algorytm Andrew krok po kroku

Schemat jest prosty:

1. Posortuj punkty rosnąco po x, a przy remisie po y.
2. Zbuduj dolną część otoczki, przechodząc po punktach od lewej do prawej.
3. Zbuduj górną część otoczki, przechodząc po punktach od prawej do lewej.
4. Połącz obie części (usuwając duplikaty końcowe).

Implementację dobrze jest opierać na funkcji cross, używając jej do sprawdzania skrętów:

std::vector<Point> convexHull(std::vector<Point> pts) {
    int n = (int)pts.size();
    if (n <= 1) return pts;

    std::sort(pts.begin(), pts.end(), [](const Point& a, const Point& b) {
        if (a.x != b.x) return a.x < b.x;
        return a.y < b.y;
    });

    std::vector<Point> hull;
    // Dolna otoczka
    for (int i = 0; i < n; ++i) {
        while (hull.size() >= 2) {
            Point A = hull[hull.size() - 2];
            Point B = hull[hull.size() - 1];
            if (cross(sub(B, A), sub(pts[i], B)) <= 0) hull.pop_back();
            else break;
        }
        hull.push_back(pts[i]);
    }

    // Górna otoczka
    size_t lowerSize = hull.size();
    for (int i = n - 2; i >= 0; --i) {
        while (hull.size() > lowerSize) {
            Point A = hull[hull.size() - 2];
            Point B = hull[hull.size() - 1];
            if (cross(sub(B, A), sub(pts[i], B)) <= 0) hull.pop_back();
            else break;
        }
        hull.push_back(pts[i]);
        if (i == 0) break; // zabezpieczenie przed i-- poniżej 0
    }

    // Usunięcie duplikatu pierwszego i ostatniego punktu
    if (!hull.empty()) hull.pop_back();
    return hull;
}

Kilka linijek i mamy w ręku narzędzie, które można wykorzystać w dziesiątkach zadań: od szacowania „rozmiaru” chmury punktów po filtr wstępny przed bardziej zaawansowaną analizą geometrii.

Typowe rozszerzenia zadań na otoczce wypukłej

Na bazie otoczki wypukłej łatwo zbudować kolejne zadania:

Średnica zbioru punktów – rotating calipers w akcji

Mając otoczkę wypukłą, często kolejnym krokiem jest policzenie średnicy zbioru punktów, czyli maksymalnej odległości między dowolnymi dwoma punktami. Naivny algorytm O(n²) łatwo „zabić” w warunkach konkursowych, ale na otoczce wypukłej wystarczy technika rotating calipers o złożoności O(n).

Przepis jest prosty: bierzemy kolejne krawędzie otoczki i szukamy dla każdej z nich punktu „antypodalnego” – takiego, dla którego odległość do aktualnego wierzchołka jest maksymalna. Dzięki monotoniczności na otoczce indeks antypodalny tylko rośnie, nigdy się nie cofa.

double diameter(const std::vector<Point>& hull) {
    int n = (int)hull.size();
    if (n < 2) return 0.0;
    if (n == 2) return dist(hull[0], hull[1]);

    double best = 0.0;
    int j = 1;

    for (int i = 0; i < n; ++i) {
        int ni = (i + 1) % n;
        // przesuwamy j tak długo, aż pole równoległoboku przestanie rosnąć
        while (true) {
            int nj = (j + 1) % n;
            double cur = fabs(cross(sub(hull[ni], hull[i]), sub(hull[j], hull[i])));
            double nxt = fabs(cross(sub(hull[ni], hull[i]), sub(hull[nj], hull[i])));
            if (nxt > cur) j = nj;
            else break;
        }
        best = std::max(best, dist(hull[i], hull[j]));
        best = std::max(best, dist(hull[ni], hull[j]));
    }
    return best;
}

To zadanie dobrze nadaje się na „drugą rundę” po opanowaniu samej otoczki: wymusza zrozumienie, co naprawdę dzieje się na poziomie geometrii, a nie tylko bezmyślne przepisanie kodu.

Minimalny prostokąt otaczający – kolejne zastosowanie rotating calipers

Skoro można znaleźć średnicę, można też znaleźć minimalny prostokąt otaczający otoczkę wypukłą. To już nieco bardziej zaawansowane ćwiczenie, ale bardzo praktyczne – przydaje się chociażby w obliczaniu orientowanych „bounding boxów” obiektów w grach czy grafice.

Idea: dla każdej krawędzi otoczki traktujemy ją jako „bazę” prostokąta i znajdujemy cztery punkty otoczki optymalnie „odsunięte” w kierunku prostopadłym i równoległym. W najprostszej wersji można jednak zaakceptować większą złożoność i skupić się na samej konstrukcji.

struct RotatedRect {
    double area;
    double angle; // kąt obrotu prostokąta
    Point  center;
};

RotatedRect minBoundingRect(const std::vector<Point>& hull) {
    int n = (int)hull.size();
    RotatedRect best{std::numeric_limits<double>::infinity(), 0.0, {0, 0}};
    if (n == 0) return best;
    if (n == 1) { best.area = 0.0; best.center = hull[0]; return best; }

    for (int i = 0; i < n; ++i) {
        Point A = hull[i];
        Point B = hull[(i + 1) % n];
        Point edge = sub(B, A);
        double ang = atan2(edge.y, edge.x); // kąt obrotu, by krawędź poszła wzdłuż osi X

        double minx =  1e100, maxx = -1e100;
        double miny =  1e100, maxy = -1e100;

        double cosT = cos(-ang);
        double sinT = sin(-ang);

        // obracamy wszystkie punkty na układ, w którym aktualna krawędź leży na osi X
        for (const auto& p : hull) {
            double rx = p.x * cosT - p.y * sinT;
            double ry = p.x * sinT + p.y * cosT;
            minx = std::min(minx, rx);
            maxx = std::max(maxx, rx);
            miny = std::min(miny, ry);
            maxy = std::max(maxy, ry);
        }

        double area = (maxx - minx) * (maxy - miny);
        if (area < best.area) {
            best.area = area;
            best.angle = ang;
            double cx = (minx + maxx) / 2.0;
            double cy = (miny + maxy) / 2.0;

            // cofamy obrót środka prostokąta
            double cosB = cos(ang);
            double sinB = sin(ang);
            best.center = {cx * cosB - cy * sinB, cx * sinB + cy * cosB};
        }
    }
    return best;
}

Dla bardziej wymagających zadań można tę procedurę zoptymalizować do typowego wariantu rotating calipers, ale nawet w tej formie pokazuje ciekawy most między geometrią analityczną a transformacjami układu współrzędnych.

Przecięcia, odległości i proste – fundamenty wielu zadań

Przecięcie dwóch odcinków – klasyczny budulec

W bardzo wielu problemach pojawia się potrzeba sprawdzenia, czy dwa odcinki się przecinają, oraz – opcjonalnie – wyznaczenia punktu przecięcia. Dobrze napisany fragment kodu tego typu staje się potem „klockiem LEGO” do kolejnych projektów: clipping wielokątów, diagramy Voronoia w wersji „ręcznej”, proste systemy CAD.

bool segmentsProperlyIntersect(Point A, Point B, Point C, Point D) {
    double c1 = cross(sub(B, A), sub(C, A));
    double c2 = cross(sub(B, A), sub(D, A));
    double c3 = cross(sub(D, C), sub(A, C));
    double c4 = cross(sub(D, C), sub(B, C));

    return (c1 * c2 < 0) && (c3 * c4 < 0);
}

bool segmentsIntersect(Point A, Point B, Point C, Point D) {
    const double EPS = 1e-9;
    if (segmentsProperlyIntersect(A, B, C, D)) return true;

    // przypadki brzegowe - punkt na odcinku
    if (fabs(cross(sub(B, A), sub(C, A))) < EPS && onSegment(A, B, C)) return true;
    if (fabs(cross(sub(B, A), sub(D, A))) < EPS && onSegment(A, B, D)) return true;
    if (fabs(cross(sub(D, C), sub(A, C))) < EPS && onSegment(C, D, A)) return true;
    if (fabs(cross(sub(D, C), sub(B, C))) < EPS && onSegment(C, D, B)) return true;
    return false;
}

Zadanie łatwo rozwinąć: zamiast zwracać tylko wartość bool, można zwracać typ wyliczeniowy (brak przecięcia, przecięcie w jednym punkcie, nieskończenie wiele punktów – odcinki współliniowe z nachodzącymi fragmentami) oraz współrzędne przecięcia, jeśli istnieje.

Punkt przecięcia prostych i odcinków – wersja numeryczna

Drugi krok po wykrywaniu przecięcia to policzenie samego punktu przecięcia. Dla odcinków przecinających się właściwie sprowadza się to do przecięcia prostych, a potem sprawdzenia, czy rozwiązanie leży w przedziale.

bool lineIntersection(Point A, Point B, Point C, Point D, Point& out) {
    // proste: A + t (B - A), C + u (D - C)
    Point r = sub(B, A);
    Point s = sub(D, C);
    double denom = cross(r, s);
    const double EPS = 1e-9;

    if (fabs(denom) < EPS) return false; // równoległe lub współliniowe

    double t = cross(sub(C, A), s) / denom;
    out = {A.x + t * r.x, A.y + t * r.y};
    return true;
}

bool segmentIntersectionPoint(Point A, Point B, Point C, Point D, Point& out) {
    if (!segmentsProperlyIntersect(A, B, C, D)) return false;
    return lineIntersection(A, B, C, D, out);
}

Taką funkcję można później łączyć np. z algorytmem wycinania wielokąta (Sutherland–Hodgman) lub bardziej zaawansowanymi operacjami na kształtach.

Odległość punktu od prostej i odcinka

Kolejne częste zadanie: minimalna odległość punktu od prostej lub odcinka. Użyteczne przy detekcji kolizji, obliczaniu „błędu dopasowania” do prostej, a nawet w prostych systemach snapowania elementów do linii.

double distPointLine(Point P, Point A, Point B) {
    // długość wektora prostopadłego / długość podstawy
    Point AB = sub(B, A);
    Point AP = sub(P, A);
    double area2 = fabs(cross(AB, AP));
    double base = len(AB);
    if (base == 0) return len(AP);
    return area2 / base;
}

double distPointSegment(Point P, Point A, Point B) {
    Point AB = sub(B, A);
    Point AP = sub(P, A);
    Point BP = sub(P, B);
    double dot1 = dot(AP, AB);
    double dot2 = dot(BP, AB);

    if (dot1 <= 0) return len(AP);  // najbliżej do A
    if (dot2 >= 0) return len(BP);  // najbliżej do B

    // rzut prostopadły wewnątrz odcinka
    return distPointLine(P, A, B);
}

To niewielki fragment kodu, który często „robi robotę” w całym projekcie – chociażby w prostym edytorze wektorowym, gdzie trzeba zaznaczyć, która krawędź jest najbliżej kursora.

Transformacje, okręgi i trochę trygonometrii

Obroty, translacje, skalowania – geometrię też się „przesuwa”

Z punktu widzenia kodowania warto mieć w jednym miejscu podstawowe transformacje liniowe i afiniczne: przesunięcie, skalowanie, obrót wokół zera i wokół zadanego punktu. To zadanie łączy geometrię analityczną z algebrą liniową, ale implementacyjnie jest dość proste.

Point translate(Point p, Point v) {
    return {p.x + v.x, p.y + v.y};
}

Point scale(Point p, double k) {
    return {p.x * k, p.y * k};
}

Point rotateAroundZero(Point p, double angle) {
    double cs = cos(angle);
    double sn = sin(angle);
    return {p.x * cs - p.y * sn, p.x * sn + p.y * cs};
}

Point rotateAround(Point p, Point c, double angle) {
    Point t = sub(p, c);
    Point r = rotateAroundZero(t, angle);
    return add(c, r);
}

Na bazie takich funkcji można bez bólu implementować obracane prostokąty, animacje obiektów czy bardziej wymyślne zadania z lokalnymi układami współrzędnych.

Okrąg przechodzący przez trzy punkty

Bardzo wdzięczne zadanie: znajdź okrąg przechodzący przez trzy zadane punkty nie współliniowe. W praktyce to równoważne znalezieniu punktu przecięcia dwóch symetralnych boków trójkąta. Wzory można wyprowadzić raz, zamknąć w funkcji i spokojnie używać.

struct Circle {
    Point c;
    double r;
};

bool circleThrough3Points(Point A, Point B, Point C, Circle& out) {
    const double EPS = 1e-9;
    double d = 2 * (A.x * (B.y - C.y) +
                    B.x * (C.y - A.y) +
                    C.x * (A.y - B.y));
    if (fabs(d) < EPS) return false; // punkty prawie współliniowe

    double a2 = A.x * A.x + A.y * A.y;
    double b2 = B.x * B.x + B.y * B.y;
    double c2 = C.x * C.x + C.y * C.y;

    double ux = (a2 * (B.y - C.y) +
                 b2 * (C.y - A.y) +
                 c2 * (A.y - B.y)) / d;
    double uy = (a2 * (C.x - B.x) +
                 b2 * (A.x - C.x) +
                 c2 * (B.x - A.x)) / d;

    out.c = {ux, uy};
    out.r = dist(out.c, A);
    return true;
}

Ten motyw pojawia się w zadaniach o minimalnych okręgach obejmujących punkty, geometrii Deliunay/Voronoi czy przy estymowaniu promienia zakrzywienia trajektorii.

Najmniejszy okrąg otaczający punkty – projekt na dłuższy wieczór

Ciekawszym, większym projektem jest minimalny okrąg zawierający wszystkie punkty (minimum enclosing circle). Jedno z elegantszych rozwiązań to losowe podejście Welzla o złożoności oczekiwanej O(n). Wbrew pozorom, implementacja jest dość kompaktowa i idealna do przećwiczenia rekurencji oraz geometrii.

Circle circleFrom2(Point A, Point B) {

Circle c;

c.c = {(A.x + B.x) / 2.0, (A.y + B.y) / 2.0};

c.r = dist(A, B) / 2.0;

return c;

}
Circle circleFrom3(Point A, Point B, Point C) {

Circle c;

circleThrough3Points(A, B, C, c);

return c;

}
bool isInside(const Circle& c, Point p, double eps = 1e-9) {

return dist(c.c, p) <= c.r + eps;

}
Circle welzl(std::vector<Point>& pts, std::vector<Point> R, int n) {

if (n == 0 || R.size() == 3) {

if (R.empty()) return {{0, 0}, 0};

if (R.size() == 1) return {R[0], 0};

if (R.size() == 2) return circleFrom2(R[0], R[1]);

return circleFrom3(R[0], R[1], R[2]);

}
    Point p = pts[n - 1];

Circle c = welzl(pts, R, n - 1);

if (isInside(c, p)) return c;
    R.push_back(p);

return welzl(pts, R, n - 1);

}
Circle minimumEnclosingCircle(std::vector<Point> pts) {

std::shuffle(pts.begin(), pts.end(), std::mt19937(std::random_device{}()));

std::vector<Point> R;

return welzl(pts, R, (int)pts.
Najczęściej zadawane pytania (FAQ)
Od jakich zadań z geometrii analitycznej najlepiej zacząć naukę kodowania?
Na początek najlepiej wybrać zadania bardzo konkretne i o prostych warunkach logicznych, np. obliczanie odległości między punktami, sprawdzanie położenia punktu względem prostej lub odcinka, proste operacje na wektorach (dodawanie, odejmowanie, długość wektora).
Takie zadania mają jasne dane wejściowe (współrzędne punktów), łatwo je zwizualizować i przetestować, a kod pozostaje krótki i czytelny. To idealny materiał na pierwsze funkcje i małe moduły geometryczne w projekcie.
Jakie struktury danych są potrzebne do prostych programów z geometrii analitycznej?
W większości podstawowych zadań wystarczy kilka prostych struktur: punkt/wektor, odcinek, opcjonalnie prosta, okrąg i wielokąt. Typowy minimalny zestaw to:
Point (lub Vector) z polami x, y,
Segment z dwoma punktami: a, b,
Circle z punktem center i promieniem r.
Na tej bazie można zbudować większość prostych algorytmów: liczenie odległości, przecięcia odcinków, sprawdzanie położenia punktu, własności trójkątów czy pierwsze zadania z wielokątami.
Jakie operacje wektorowe są najważniejsze w zadaniach do kodowania?
Najczęściej używane operacje na wektorach (punktach) to:
dodawanie i odejmowanie wektorów (np. sub(b, a) tworzy wektor AB),
mnożenie przez skalar (skalowanie wektora),
iloczyn skalarny – pozwala liczyć kąty i rzutować wektory,
iloczyn wektorowy 2D (pseudowektorowy) – służy m.in. do sprawdzania orientacji punktów i przecięcia odcinków,
długość wektora i normalizacja (sprowadzenie do długości 1).
Zaimplementowanie tego zestawu jako prostych funkcji mocno upraszcza i skraca kod w późniejszych, bardziej złożonych zadaniach geometrycznych.
Dlaczego geometria analityczna jest dobra do nauki algorytmiki i programowania?
Geometria analityczna łączy świat wizualny (punkty, proste, odcinki, okręgi) z bardzo precyzyjnym opisem liczbowym (współrzędne, wektory, równania). Dzięki temu zadania są konkretne, łatwo je przetestować i zwizualizować.
Przy okazji uczysz się ważnych umiejętności algorytmicznych: pracy z liczbami zmiennoprzecinkowymi (błędy numeryczne), projektowania struktur danych, dzielenia problemu na mniejsze funkcje (np. od iloczynu skalarnego do przecięcia odcinków) oraz analizowania złożoności obliczeniowej.
Jakie typowe zadania geometryczne pojawiają się w konkursach programistycznych?
W konkursach i olimpiadach często pojawiają się rozwinięcia podstawowych motywów: przecięcia wielu odcinków, sprawdzanie czy punkt leży w wielokącie, liczenie pola i obwodu wielokąta, budowa otoczki wypukłej, bardziej zaawansowane operacje na wielokątach.
Na późniejszym etapie spotkasz też zadania z triangulacją wielokąta, diagramami Voronoi czy optymalizacją położenia punktów. Wszystkie te problemy bazują na solidnym opanowaniu prostych operacji: dystanse, iloczyny wektorowe, testy położenia, reprezentacja obiektów w kodzie.
Jak radzić sobie z błędami numerycznymi w geometrii analitycznej w kodzie?
W zadaniach liczbowych niemal zawsze korzysta się z typu zmiennoprzecinkowego double, co oznacza, że wyniki są przybliżone. Zamiast porównywać liczby na równość, używa się małej tolerancji (epsilon), np. sprawdzając, czy fabs(x) < 1e-9 zamiast x == 0.
Warto też unikać zbędnych pierwiastków, jeśli nie są potrzebne (porównywać kwadraty odległości zamiast samych odległości). Świadome obchodzenie się z dokładnością obliczeń to kluczowa część programowania zadań z geometrii analitycznej.
Najważniejsze lekcje
Geometria analityczna jest idealnym „poligonem” dla programisty, bo łączy wizualne obiekty (punkty, odcinki, okręgi) z prostymi strukturami danych i jasnymi wzorami.
Zadania geometryczne mają czytelne wejście i wyjście, wykorzystują powtarzalne schematy obliczeń i można je łatwo zweryfikować oraz wielokrotnie używać w różnych projektach.
Praca z takimi zadaniami uczy kluczowych umiejętności algorytmicznych: radzenia sobie z błędami numerycznymi, projektowania struktur danych oraz dzielenia problemu na mniejsze funkcje.
„Przyjazne” kodowaniu zadania mają jasne dane (współrzędne), proste modele (punkt, wektor, odcinek), jednoznaczne warunki logiczne oraz łatwą możliwość wizualizacji wyników.
Najbardziej praktyczne grupy zadań to: punktowe, odcinkowe/proste, wielokąty, okręgi oraz transformacje geometryczne, które stopniowo prowadzą od prostych funkcji do złożonych algorytmów.
Podstawą implementacji jest wspólny typ dla punktu i wektora oraz zestaw operacji wektorowych (dodawanie, odejmowanie, skalowanie, iloczyn skalarny i wektorowy, długość, normalizacja).
Dobrze zaprojektowane funkcje pomocnicze do operacji na wektorach znacząco upraszczają późniejszy kod, czyniąc go krótszym, czytelniejszym i łatwiejszym do ponownego użycia.
Jeśli spodobał Ci się ten artykuł, sprawdź też:
Kartezjusz i narodziny geometrii analitycznej
Co to jest geometria analityczna?
Geometria analityczna: odległość punktów i środek…
Algebra w geometrii analitycznej
Układ współrzędnych: jak odczytywać punkty i rysować…
Argument, wartość funkcji i współrzędne – podstawowe pojęcia