Przecinanie odcinków i punkt w trójkącie

🎯 Po co Ci to?

Uzbrojony w jeden test orientacji (10.1) rozwiążesz teraz dwa problemy, które wyglądają na znacznie trudniejsze — a padają jak kostki domina, bo każdy sprowadza się do kilku pytań „po której stronie". Czy dwie drogi się krzyżują? Czy kliknięcie trafiło w trójkątny przycisk? Czy trasa robota przecina przeszkodę? To geometria, którą gry i systemy graficzne wykonują miliony razy na sekundę — a Ty zobaczysz, że wszystko to jest sprytnym składaniem jednego prostego klocka. To lekcja o tym, jak z jednej dobrej idei (znak iloczynu wektorowego) buduje się bogactwo — kwintesencja myślenia algorytmicznego.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

• rozstrzygnąć, czy dwa odcinki się przecinają, używając czterech testów orientacji;
• sprawdzić, czy punkt leży wewnątrz trójkąta (metoda „ta sama strona");
• docenić, jak złożone testy geometryczne rozkładają się na powtórzenia jednej operacji.

🔁 Przypomnij sobie

Z 10.1: orientacja trójki = znak iloczynu wektorowego; strona prostej; z 1.4: dekompozycja — złóż trudny problem z prostych klocków.

📘 Wyjaśnienie

Przecinanie odcinków. Dwa odcinki $AB$ i $CD$ przecinają się, gdy… no właśnie, kiedy? Intuicja: gdy $C$ i $D$ są po przeciwnych stronach prostej $AB$, oraz $A$ i $B$ są po przeciwnych stronach prostej $CD$. Każde „po przeciwnych stronach" to para testów orientacji o przeciwnych znakach:

def przecinaja(A, B, C, D):
    d1 = orientacja(A, B, C)   # C względem prostej AB
    d2 = orientacja(A, B, D)   # D względem prostej AB
    d3 = orientacja(C, D, A)   # A względem prostej CD
    d4 = orientacja(C, D, B)   # B względem prostej CD
    # przecinają się, gdy C,D po przeciwnych stronach AB ORAZ A,B po przeciwnych stronach CD
    return (d1 != d2) and (d3 != d4)   # (uproszczenie: bez przypadków współliniowych)

Cztery wywołania jednej funkcji z 10.1 — i gotowe. Dlaczego oba warunki są potrzebne? Bo sam pierwszy (C i D po przeciwnych stronach $AB$) mówi tylko, że prosta $AB$ rozdziela $C$ i $D$ — ale odcinek $AB$ mógłby być za krótki, by faktycznie dosięgnąć między nie. Drugi warunek pilnuje, że i odcinek $CD$ rozdziela $A$ i $B$. Dopiero razem gwarantują przecięcie odcinków, nie tylko prostych.

Punkt w trójkącie. Czy punkt $P$ leży wewnątrz trójkąta $ABC$? Elegancki test „ta sama strona": $P$ jest wewnątrz, gdy leży po tej samej stronie każdego z trzech boków, co przeciwległy wierzchołek. Praktyczniej — gdy obchodząc trójkąt w ustalonym kierunku, $P$ jest zawsze po tej samej stronie: orientacja(A,B,P), orientacja(B,C,P), orientacja(C,A,P) mają wszystkie ten sam znak. Jeśli któryś się różni — $P$ jest na zewnątrz (za którymś bokiem). Trzy testy orientacji rozstrzygają problem, który wzorem byłby żmudny.

💭 Pomyśl: Metoda „ta sama strona" dla punktu w trójkącie robi trzy testy orientacji. Co oznacza, jeśli jeden z nich wyjdzie zero, a pozostałe mają ten sam znak?

Sprawdź odpowiedź

Zero orientacji dla boku (np. orientacja(A,B,P) = 0) znaczy, że $P$ leży na prostej zawierającej ten bok — a skoro pozostałe dwa testy dają zgodny znak, $P$ jest na samym boku trójkąta (na krawędzi), nie w środku i nie na zewnątrz. To brzeg problemu: „wewnątrz", „na brzegu", „na zewnątrz" to trzy odpowiedzi, nie dwie — a specyfikacja (dział 1!) musi rozstrzygnąć, czy punkt na krawędzi liczy się jako „w trójkącie". W grach zwykle tak (kliknięcie w sam brzeg przycisku ma działać); w innych zastosowaniach niekoniecznie. Znów: brzegi trzeba przemyśleć, nie zignorować.

⚠️ Uwaga, pułapka

Uproszczona wersja przecinaja (z != znaków) pomija przypadki współliniowe — gdy koniec jednego odcinka leży dokładnie na drugim (orientacja = 0). Pełna, poprawna implementacja musi je obsłużyć osobno (czy współliniowy punkt mieści się w pudełku — jak w teście „na odcinku" z 10.1). To typowe dla geometrii obliczeniowej: główna idea jest prosta i piękna, a diabeł mieszka w przypadkach brzegowych (dotknięcia, współliniowości, wspólne końce). Zawodowa implementacja przecinania odcinków jest kilka razy dłuższa od naszej — nie dlatego, że idea jest trudna, lecz dlatego, że brzegów jest wiele. Świadomość „to jest szkielet, brzegi wymagają dopracowania" to część uczciwości inżynierskiej.

🌍 Powiązania

Testy z tej jednostki pracują wszędzie, gdzie liczy się „czy coś się styka": wykrywanie kolizji w grach (czy pocisk przeciął gracza? czy postać weszła w ścianę?), systemy CAD (czy linie projektu się krzyżują?), robotyka (czy planowana trasa przecina przeszkodę?), systemy geograficzne (czy droga przechodzi przez działkę?). „Punkt w wielokącie" (uogólnienie trójkąta) rozstrzyga, w którym kraju/rejonie jest współrzędna GPS. Wszystko to — miliony razy na sekundę — sprowadza się do zliczania znaków iloczynu wektorowego. Jedna operacja z 10.1, cała warstwa interaktywności współczesnego oprogramowania.

🛠️ Teraz Ty

Bez komputera: sprawdź, czy przecinają się odcinki (0,0)–(4,4) i (0,4)–(4,0) (cztery orientacje!) — a potem (0,0)–(1,1) i (3,3)–(4,4) (te same proste, ale...). Sprawdź, czy P(2,1) leży w trójkącie (0,0), (4,0), (2,4). Z komputerem: zaimplementuj przecinaja i w_trojkacie na bazie orientacja z 10.1; przetestuj w_trojkacie na punkcie wewnętrznym, zewnętrznym i na krawędzi.

📐 Definicje tej lekcji

• Przecinanie odcinków — $AB$ i $CD$ przecinają się, gdy $C,D$ po przeciwnych stronach $AB$ oraz $A,B$ po przeciwnych stronach $CD$ (cztery testy orientacji).
• Punkt w trójkącie (ta sama strona) — $P$ wewnątrz, gdy trzy orientacje (A,B,P), (B,C,P), (C,A,P) mają zgodny znak.

📌 Najważniejsze w pigułce

• Złożone testy geometryczne rozkładają się na powtórzenia jednej operacji — znaku iloczynu wektorowego (10.1).
• Przecinanie odcinków: dwa warunki „po przeciwnych stronach" (oba konieczne — prosta ≠ odcinek).
• Punkt w trójkącie: zgodny znak trzech orientacji; zero = na krawędzi (brzeg do rozstrzygnięcia w specyfikacji).

🎒 Zadania

1. Czy przecinają się: (a) (1,1)–(4,4) i (1,4)–(4,1), (b) (0,0)–(2,0) i (3,0)–(5,0), (c) (0,0)–(3,3) i (1,1)–(2,5)? Uzasadnij orientacjami.

Wskazówka i odpowiedź

(a) Przecinają się (przekątne kwadratu — C,D po przeciwnych stronach AB i odwrotnie). (b) Nie — leżą na tej samej prostej (y=0), rozłączne odcinki: to przypadek współliniowy, gdzie uproszczony test może zawieść, a poprawny sprawdza pudełka i stwierdza brak wspólnych punktów. (c) Punkt (1,1) leży na odcinku (0,0)–(3,3), a jest końcem drugiego odcinka → „dotykają się" w (1,1) — kolejny przypadek brzegowy (wspólny punkt końcowy), który uproszczona wersja traktuje niejednoznacznie. Dwa z trzech przykładów to celowo brzegi — bo w geometrii to one są trudne, nie przypadek ogólny.

2. Sprawdź, czy punkt P(2,1) leży w trójkącie A(0,0), B(4,0), C(2,4) metodą trzech orientacji. Pokaż wszystkie trzy znaki.

Wskazówka i odpowiedź

orientacja(A,B,P): $(4)(1)-(0)(2) = 4 > 0$. orientacja(B,C,P): $(2-4)(1-0)-(4-0)(2-4) = -2+8 = 6 > 0$. orientacja(C,A,P): $(0-2)(1-4)-(0-4)(2-2) = 6-0 = 6 > 0$. Wszystkie dodatnie → P wewnątrz ✓. Zgodny znak wszystkich trzech = punkt po tej samej („wewnętrznej") stronie każdego boku. Gdyby jeden wyszedł ujemny, P byłby za tym bokiem, na zewnątrz.

3. Wyjaśnij, jak przy pomocy testu „punkt w trójkącie" sprawdzić, czy punkt leży w dowolnym wielokącie wypukłym (np. pięciokącie). A czemu dla wielokąta niewypukłego ta metoda zawodzi?

Wskazówka i odpowiedź

Wielokąt wypukły: punkt jest wewnątrz, gdy leży po tej samej stronie wszystkich boków (obchodząc wielokąt w jednym kierunku — zgodny znak orientacji dla każdej krawędzi). To wprost uogólnienie trójkąta (trójkąt to wypukły 3-kąt). Dla niewypukłego (np. gwiazdy) metoda zawodzi, bo „ta sama strona każdego boku" nie opisuje już wnętrza — wklęsłości psują regułę. Wielokąty niewypukłe wymagają innej metody (np. „liczba przecięć promienia" — puść półprostą z punktu i policz, ile boków przecina: nieparzyście = wewnątrz). Wypukłość to własność, która czyni geometrię łatwą — i dlatego algorytmy często najpierw dzielą figury na wypukłe kawałki.

🔍 Sprawdź, czy umiesz

• Rozstrzygnąć przecinanie odcinków czterema testami orientacji i uzasadnić oba warunki.
• Sprawdzić punkt w trójkącie metodą zgodnego znaku trzech orientacji.
• Wyjaśnić, czemu brzegi (współliniowość, dotknięcia) są w geometrii obliczeniowej najtrudniejsze.

---