Punkt, prosta, odcinek — orientacja

🎯 Po co Ci to?

„Czy postać w grze widzi przeciwnika?" „Po której stronie linii mety jest samochód?" „Czy kliknięcie trafiło w przycisk?" Za każdym z tych pytań stoi geometria, którą komputer musi wyliczyć — bo nie ma oczu. A najbardziej fundamentalne pytanie geometrii obliczeniowej brzmi rozbrajająco prosto: po której stronie prostej leży punkt? Odpowiedź — jeden wzór dający znak — okaże się szwajcarskim scyzorykiem: z niej wyprowadzisz przecinanie odcinków, przynależność do trójkąta i pół tuzina innych testów. To jeden z tych momentów, gdy jedna elegancka idea otwiera całą dziedzinę.

✅ Czego się nauczysz

Po tej jednostce potrafisz:

  • wyznaczyć orientację trójki punktów (w lewo / w prawo / współliniowo) iloczynem wektorowym;
  • rozstrzygnąć, po której stronie prostej leży punkt, używając znaku tego iloczynu;
  • sprawdzić, czy punkt leży na odcinku.

🔁 Przypomnij sobie

Z 2.4: porównania z progiem (geometria na liczbach zmiennoprzecinkowych!); z 4.1: znak iloczynu jako test (f(a)*f(s) < 0 w bisekcji — tu podobnie).

📘 Wyjaśnienie

Orientacja trójki punktów. Idziesz z punktu $A$ do $B$, a potem chcesz dojść do $C$. Skręcasz w lewo, w prawo, czy $C$ leży dokładnie na przedłużeniu prostej? To pytanie o orientację trójki $(A, B, C)$ — i jest sercem całej jednostki.

Rozstrzyga je jedna liczba, tzw. iloczyn wektorowy wektorów $\overrightarrow{AB}$ i $\overrightarrow{AC}$:

$$d = (B_x - A_x)(C_y - A_y) - (B_y - A_y)(C_x - A_x)$$

Nie wzór jest tu ważny, lecz jego znak:

  • $d > 0$: $C$ jest po lewej stronie kierunku $A \to B$ (skręt w lewo, orientacja przeciwna do ruchu wskazówek zegara);
  • $d < 0$: $C$ po prawej (skręt w prawo);
  • $d = 0$: $A$, $B$, $C$ są współliniowe (leżą na jednej prostej).
C po lewej: d > 0 (skręt w lewo)ABCC po prawej: d < 0 (skręt w prawo)ABCC na prostej: d = 0 (współliniowe)ABCd = (Bx−Ax)(Cy−Ay) − (By−Ay)(Cx−Ax)znak d rozstrzygastronę i skręt
Orientacja trójki punktów: z punktu A do B, trzeci punkt C po lewej stronie (iloczyn wektorowy dodatni, skręt w lewo), po prawej (ujemny) lub na prostej AB (zero); ten sam znak rozstrzyga stronę prostej. · rys. własny
def orientacja(A, B, C):
    d = (B[0]-A[0])*(C[1]-A[1]) - (B[1]-A[1])*(C[0]-A[0])
    if d > 0: return "lewo"
    if d < 0: return "prawo"
    return "wspolliniowe"

Strona prostej. Prosta przez $A$ i $B$ dzieli płaszczyznę na dwie połowy. Który punkt jest po której stronie? Dokładnie ten sam znak $d$: punkty ze znakiem $+$ są po jednej stronie, ze znakiem $-$ po drugiej, z zerem — na prostej. Jedno pytanie („orientacja"), dwa zastosowania („skręt" i „strona") — bo to geometrycznie to samo.

Punkt na odcinku. Odcinek to kawałek prostej między $A$ i $B$. Punkt $P$ leży na odcinku $AB$, gdy (1) jest współliniowy z $A, B$ (orientacja = 0) oraz (2) mieści się w „pudełku" wyznaczonym przez końce ($\min(A_x, B_x) \le P_x \le \max(A_x, B_x)$ i podobnie dla $y$). Sam warunek współliniowości nie wystarcza — bo współliniowy punkt może leżeć na przedłużeniu odcinka, poza jego końcami. To subtelna, ale kluczowa różnica: prosta jest nieskończona, odcinek — ograniczony.

💭 Pomyśl: Trzy miasta na mapie: A(0,0), B(4,4), C(1,1). Policz orientację — co mówi znak? Co to znaczy geometrycznie i praktycznie (czy z A widać B „obok" C)?

Sprawdź odpowiedź

$d = (4-0)(1-0) - (4-0)(1-0) = 4 - 4 = 0$ — współliniowe! C(1,1) leży dokładnie na prostej przez A(0,0) i B(4,4) (to prosta $y=x$). Praktycznie: jadąc z A do B, przejechałbyś przez C (a właściwie: C jest na odcinku AB, bo mieści się w pudełku $[0,4]\times[0,4]$). Zero iloczynu to sygnał „idealnie na linii" — a że dane geometryczne bywają zmiennoprzecinkowe (2.4!), w praktyce sprawdza się abs(d) < epsilon, nie d == 0; dokładne zero to luksus liczb całkowitych.

⚠️ Uwaga, pułapka

Iloczyn wektorowy na współrzędnych całkowitych daje dokładny wynik — ale na zmiennoprzecinkowych (2.4!) porównanie d == 0 prawie nigdy nie trafi w prawdziwe zero (błędy zaokrągleń). Punkty „prawie współliniowe" to zmora geometrii obliczeniowej: algorytm musi zdecydować, czy mikroskopijne $d = 0{,}0000001$ to „na prostej" czy „ledwie obok" — a od tej decyzji zależy poprawność. Stąd zasada: geometrię licz na całkowitych, gdy tylko możesz; a gdy musisz na zmiennoprzecinkowych — porównuj z progiem i wiedz, że brzegowe przypadki (punkt tuż-tuż na linii) są tu naprawdę trudne.

🌍 Powiązania

Test orientacji to fundament geometrii obliczeniowej — dziedziny, która ożywia gry (czy pocisk trafił?), grafikę (która ściana jest widoczna?), robotykę (czy droga wolna?), systemy map (w którym rejonie jest punkt?) i projektowanie wspomagane komputerowo. Ten sam znak iloczynu wektorowego, którego się właśnie nauczyłeś, buduje otoczkę wypukłą (najmniejszy wielokąt obejmujący zbiór punktów — jak gumka naciągnięta na pinezki), sprawdza, czy wielokąt jest wypukły, i triangularyzuje powierzchnie do renderowania 3D. Jedna liczba, cała dziedzina.

🛠️ Teraz Ty

Bez komputera: policz orientację trójek: (a) A(0,0), B(3,0), C(1,2); (b) A(0,0), B(3,0), C(1,-2); (c) A(0,0), B(2,2), C(3,3). Zinterpretuj każdy znak. Sprawdź, czy P(2,1) leży na odcinku od (0,0) do (4,2). Z komputerem: zaimplementuj orientacja i na_odcinku; przetestuj na_odcinku na punkcie współliniowym, ale poza odcinkiem (np. (6,3) dla odcinka (0,0)–(4,2)) — musi wyjść „nie".

📐 Definicje tej lekcji

  • Orientacja trójki $(A,B,C)$ — znak iloczynu wektorowego $\overrightarrow{AB} \times \overrightarrow{AC}$: dodatni (lewo), ujemny (prawo), zero (współliniowe).
  • Strona prostej — ten sam znak rozstrzyga, po której stronie prostej $AB$ leży punkt.
  • Punkt na odcinku — współliniowość (orientacja = 0) oraz mieszczenie się w pudełku końców.

📌 Najważniejsze w pigułce

  • Jedna liczba (iloczyn wektorowy) i jej znak odpowiadają: skręt lewo/prawo, strona prostej, współliniowość.
  • Odcinek to prosta ograniczona — na odcinku = współliniowy I w pudełku końców.
  • Geometrię licz całkowicie, gdy możesz; na zmiennoprzecinkowych porównuj z progiem (brzegi są trudne).

🎒 Zadania

  1. Dla A(1,1), B(5,3) rozstrzygnij stronę prostej dla punktów P(2,4), Q(4,0), R(3,2). Który leży na prostej?
Wskazówka i odpowiedź

$d(P) = (5-1)(4-1) - (3-1)(2-1) = 12 - 2 = 10 > 0$ (lewo). $d(Q) = 4\cdot(-1) - 2\cdot3 = -4-6 = -10 < 0$ (prawo). $d(R) = 4\cdot1 - 2\cdot2 = 0$ — R(3,2) na prostej. Zauważ symetrię: P i Q mają przeciwne znaki o tej samej wartości — leżą po przeciwnych stronach, symetrycznie względem prostej. Znak = strona, wartość ~ odległość od prostej (przyda się, gdy będziesz chciał wiedzieć nie tylko „która strona", ale „jak daleko").

  1. Wyjaśnij, czemu sam warunek „orientacja = 0" NIE wystarcza, by punkt leżał na odcinku. Podaj kontrprzykład.
Wskazówka i odpowiedź

Współliniowość znaczy „na prostej", a prosta jest nieskończona. Punkt (10,10) jest współliniowy z odcinkiem (0,0)–(2,2) (wszystkie na $y=x$), ale leży daleko poza odcinkiem. Trzeba dołożyć warunek pudełka: $0 \le 10 \le 2$? Nie → nie na odcinku. Rozróżnienie prosta/odcinek to ta sama pułapka, co podciąg/podsłowo (8.4) czy </<= w binarnym (6.2) — brzegi i zakresy rządzą poprawnością.

  1. W grze gracz stoi w punkcie G i celuje wzdłuż linii do punktu M (mysz). Wróg jest w punkcie W. Jak jednym testem orientacji sprawdzić, czy strzał (wzdłuż prostej G→M) przechodzi po lewej czy po prawej od wroga?
Wskazówka i odpowiedź

Policz orientacja(G, M, W): dodatni → wróg po lewej od linii strzału, ujemny → po prawej, zero → strzał trafia idealnie (W na linii G→M). To dosłownie tak działa celowanie i „aim assist" w grach — jeden iloczyn wektorowy na klatkę mówi, w którą stronę korygować. Wartość $|d|$ (podzielona przez długość G→M) dałaby nawet odległość wroga od linii strzału — czyli „o ile chybiłeś". Geometria obliczeniowa to niewidzialny silnik każdej gry akcji.

🔍 Sprawdź, czy umiesz

  • Policzyć orientację trójki punktów i zinterpretować znak (lewo/prawo/współliniowo).
  • Rozstrzygnąć stronę prostej i sprawdzić przynależność punktu do odcinka.
  • Wyjaśnić, czemu na zmiennoprzecinkowych „na prostej" jest trudne.

Ucz się tej jednostki z asystentem