Definicja geometrii analitycznej

Rozmawiając o algorytmach geometrycznych, nie sposób pominąć geometrii analitycznejgeometria analitycznageometrii analitycznej. Jest to dział geometrii, który zajmuje się figurami geometrycznymi umieszczonymi w układzie współrzędnych.

Więcej informacji na temat geometrii analitycznej znajdziesz w e‑materiale Punkty na płaszczyźnie z układem współrzędnychP187v3w2ePunkty na płaszczyźnie z układem współrzędnych oraz w innych e‑materiałach oznaczonych tagiem „geometria analityczna” na platformie zpe.gov.pl.

Wykorzystanie geometrii analitycznej w algorytmach

Przynależność punktu do prostej opisanej równaniem

Zacznijmy od jednego z prostszych algorytmów – sprawdzenia, czy punkt należy do prostej. Zauważ, że prosta leżąca na płaszczyźnie to zbiór punktów spełniających pewne równanie. Wyróżnić możemy kilka równań prostych. Jednym z nich jest równanie kierunkowe, którego wzór możemy zapisać jako:

gdzie:

• $a$ to współczynnik kierunkowy;

• $b$ to wyraz wolny.

Aby sprawdzić, czy dany punkt leży na prostej, należy sprawdzić, czy po podstawieniu jego współrzędnych do równania prostej, równanie będzie spełnione.

Jeśli prosta jest równoległa do osi $y$, korzystamy ze wzoru $x = b$, gdzie $b$ to pewna stała.

Rozważmy następującą sytuację.

Prosta opisana jest równaniem $y = x$. Dane są również punkty $A=\left(1,\ 3\right)$ oraz $C=\left(2,\ 2\right)$. Sprawdzimy, czy punkty leżą na prostej.

R18dt8ovdenqF

Ilustracja przedstawia układ współrzędnych z osiami X oraz Y, gdzie umieszczono punkty: A=(1, 3) i C=(2, 2).
Na osi tej znajduje się również prosta przechodząca przez punkt o współrzędnych (0, 0) oraz punkt C o współrzędnych (2, 2). Punkt A znajduje się ponad linią w punkcie o współrzędnych (1, 3).

Podstawiamy współrzędne punktu $A$ do równania prostej i otrzymujemy:

$3=1$

Równanie jest sprzeczne. Zatem punkt ten nie leży na prostej.

Sprawdźmy teraz, jak sytuacja wygląda w przypadku punktu $C$. Podstawiamy współrzędne do wzoru funkcji:

$2=2$

Zachodzi równanie, zatem punkt $C$ leży na prostej.

By sprawdzić, czy punkt $A(x, y)$ należy do prostej $x = b$, wystarczy sprawdzić, czy współrzędna $x$ punktu $A$ jest równa $b$.

Warunek współliniowości punktów umieszczonych w układzie współrzędnych

Jak sprawdzić, czy dane trzy punkty leżą na jednej prostej?

Wykorzystamy współliniowość punktów.

Załóżmy, że mamy trzy punkty opisane następującymi współrzędnymi:$A=\left(x_a,y_a\right);\ B=\left(x_b,y_b\right);\ C=\left(x_c,y_c\right)$.

Z lekcji matematyki wiemy, że warunek współliniowości trzech punktów wygląda następująco:

Dane są trzy punkty $A$, $B$ i $C$.

Współrzędne punktów: $A=\left(5,\ 11\right);\ B=\left(1,\ 3\right);\ C=\left(7,\ 15\right)$. By sprawdzić, czy punkty leżą na jednej prostej, podstawmy odpowiednie wartości do wzoru.

$(1-5)(15-11)=(3-11)(7-5)$

$-4\cdot4=-8\cdot2$

$-16=-16$

Równanie jest spełnione, zatem te trzy punkty są współliniowe.

Przynależność punktu do odcinka

Dany jest odcinek o końcach w punktach: $A=(x_a,y_a);B=(x_b,y_b)$. Aby sprawdzić, czy dany punkt $C=(x_c,y_c)$ należy do tego odcinka, możemy wykorzystać równanie prostej przechodzącej przez punkty:

Jeżeli po podstawieniu do równania współrzędnych punktu $C$ równanie jest spełnione, punkt $C$ leży na prostej zawierającej odcinek $|AB|$.

By punkt $C$ należał do odcinka $|AB|$, spełnione muszą być również następujące założenia:

• $x_{c\ }\ \ge\ \min\left(x_a\ ;\ x_b\right)\$

• $x_{c\ }\ \le\ \max\left(x_a\ ;\ x_b\right)\ $

• $y_{c\ }\ \ge\ \min\left(y_a\ ;\ y_b\right)\$

• $y_{c\ }\ \le\ \max\left(y_a\ ;\ y_b\right)\ $

Możemy zatem zauważyć, że położenie jednego punktu wobec dwóch innych punktów, które wyznaczają dany odcinek, może być następujące:

1. Punkt $C$ leży na jednej prostej z punktami $A$ i $B$ oraz należy do odcinka.

2. Punkt $C$ leży na jednej prostej z punktami $A$ i $B$, ale nie należy do odcinka.

3. Punkt $C$ nie leży na jednej prostej z punktami $A$ i $B$ i nie należy do odcinka.

R13HMDl9yVcUx

Ilustracja

Przynależność punktu do okręgu lub koła

Równanie okręgu w układzie współrzędnych o środku w punkcie $O=(a,b)$ oraz promieniu $r$ wygląda następująco:

Nierówność koła wygląda następująco:

Aby sprawdzić, czy dany punkt należy do okręgu, wystarczy zatem sprawdzić, czy spełnione jest dla niego równanie okręgu. Możemy również zbadać, czy punkt leży wewnątrz koła, podstawiając współrzędne punktu do nierówności koła.

Przećwiczmy to na przykładzie:

Dane są punkty $(5,10),(1,5),(7,8)$. Należy sprawdzić, które z nich leżą wewnątrz koła lub na okręgu o środku w punkcie $O=(3,5)$ oraz promieniu $r=5$.

Napiszmy najpierw nierówność koła:

Podstawiamy współrzędne pierwszego punktu do nierówności koła:

$(5-3)^2+(10-5)^2\le25$

$2^2+5^2\le25$

$4+25\le25$

$29\le25$

Otrzymaliśmy nieprawdę, zatem pierwszy punkt nie leży wewnątrz koła.

Sprawdźmy drugi punkt:

$(1-3)^2+(5-5)^2\le25$

$(-2)^2+0^2\le25$

$4+0\le25$

$4\le25$

Otrzymaliśmy prawdę, drugi punkt należy do koła.

Sprawdzamy trzeci punkt: $(7-3)^2+(8-5)^2\le25$

$4^2+3^2\le25$

$16+9\le25$

$25\le25$

Nierówność jest spełniona, zatem punkt leży wewnątrz koła. Ponieważ zachodzi równość, możemy od razu stwierdzić, że punkt leży na okręgu.

Przynależność punktu do wielokąta wypukłego

Odpowiedzmy teraz na pytanie zawarte we wstępie do tego e‑materiału: jak sprawdzić, czy punkt należy do wielokąta wypukłegowielokąt wypukływielokąta wypukłego

Zacznijmy od przywołania pewnej własności.

R13q6QnpaGZER

Ilustracja przedstawia obszar będący nieforemnym pięciokątem wklęsłym oraz losowo rozmieszczone punkty: a, b, c, d, e, f, g.
Punkty A, F oraz G znajdują się poza obszarem.
Punkty B i E znajdują się wewnątrz obszaru.
Punkty C i D znajdują się po prawej stronie obszaru.
Od każdego punktu wychodzi czerwona strzałka skierowana w lewą stronę, strzałki od punktów B oraz E przechodzą przez jeden bok figury,
natomiast od punktów C i D przez dwa boki.

Co łączy wszystkie punkty leżące poza wielokątem? Jeśli poprowadzimy półproste z każdego punktu w dowolnym kierunku (np. w dół), to liczba ich przecięć z bokami wielokąta jest parzysta (zero traktujemy jako liczbę parzystą). Półproste wychodzące z punktów leżących w środku wielokąta przecinają jego boki nieparzystą liczbę razy.

Możemy wykorzystać ten fakt do stworzenia algorytmu, który na podstawie liczby tych przecięć określi, czy dany punkt $P=(x_p,y_p)$ należy do wielokąta, czy leży poza nim.

Ustalmy, jak będziemy definiowali nasz wielokąt. Rozpatrzmy to na przykładzie równoległoboku.

RXIZMBFNGvNyf

Ilustracja przedstawia równoległobok o wierzchołkach: A, B, C, D połączonych połączonych.

Każdy rozpatrywany przez nas wielokąt będzie uporządkowaną listą kolejnych jego wierzchołków. Oznacza to, że przedstawiony na rysunku wielokąt zapiszemy jako: $A,B,C,D$.

Uwaga!

Lista wierzchołków musi być podana w kolejności zgodnej z kierunkiem ruchu wskazówek zegara albo w przeciwnej. Dla kolejności: $A,C,B,D$ wielokąt wyglądałby następująco:

R1FHAWwCfwhCa

Ilustracja przedstawia równoległobok o wierzchołkach: A, B, C, D połączonych połączonych.

Wówczas algorytm mógłby dać nieoczekiwany rezultat.

Przed przystąpieniem do budowy algorytmu, warto omówić parę problematycznych sytuacji, które należy rozwiązać osobno. Zanim jednak do nich przejdziemy, musimy zdecydować się na wybór równania oraz zwrotu półprostej, której użyjemy do wyznaczenia przecięć. Możemy przypuszczać, że gdy wybrana półprosta będzie prostopadła lub równoległa do osi układu współrzędnych, tworzenie algorytmu będzie prostsze. Przypuszczenia te są uzasadnione, dlatego na potrzeby naszych rozważań została wybrana półprosta równoległa do osi OY, zwrócona w dół. Jej równanie jest następujące:

Zwrot w dół powoduje, że rozpatrywana będzie ona dla wartości $y<y_p$.

Oto rysunek, na którym ukazano niektóre przypadki, z jakimi możemy się spotkać:

RJnh1iUnOgB5k

Ilustracja przedstawia równoległobok o wierzchołkach: A, B, C, D połączonych połączonych.

Pierwszy problematyczny przypadek to taki, w którym punkt $P$ będzie leżał na bokach wielokąta (również jeśli będzie wierzchołkiem).

R1eqqKMvlsDeu

Półproste poprowadzone z punktów P indeks dolny, jeden, koniec indeksu dolnego i P indeks dolny, trzy, koniec indeksu dolnego przecinają boki wielokąta nieparzystą liczbę razy. Półprosta poprowadzona z punktu P indeks dolny, dwa, koniec indeksu dolnego przecina boki wielokąta parzystą liczbę razy. Według wprowadzonej reguły punkty P indeks dolny, jeden, koniec indeksu dolnego i P indeks dolny, trzy, koniec indeksu dolnego zostałyby uznane za należące do wielokąta, a punkt P indeks dolny, dwa, koniec indeksu dolnego nie. Przypadek ten należy rozpatrzyć oddzielnie.

W celu wyeliminowania tego przypadku, należy sprawdzić przynależność punktu $P$ do każdego z boków wielokąta przed przystąpieniem do głównej części algorytmu. Zagadnienie to zostało omówione powyżej w akapicie zatytułowanym Przynależność punktu do odcinka. Jeśli punkt $P$ leży na boku wielokąta, możemy od razu stwierdzić, że należy do tego wielokąta.

Drugi przypadek to taki, gdy wybrana półprosta przetnie wielokąt w punkcie, który będzie równocześnie wierzchołkiem wielokąta. Niestety, przypadek ten jest trochę bardziej skomplikowany, ponieważ zawiera w sobie sytuację brzegową, którą należy zidentyfikować.

RXqXjyXQ41DUh

Ilustracja przedstawia równoległobok o wierzchołkach: A, B, C, D połączonych połączonych.

Przecięcie półprostej poprowadzonej z punktu $P_2$ mogłoby zostać policzone podwójnie — raz dla krawędzi $\mathrm{AB}$, drugi raz dla krawędzi $\mathrm{EA}$. Aby temu zapobiec, możemy założyć, że każdy wierzchołek należy tylko do jednej krawędzi wielokąta. Przykładowo: wierzchołek $A$ należy do krawędzi $\mathrm{AB}$, jednak nie należy do krawędzi $\mathrm{EA}$. Rozwiązanie to nie zadziała jednak w przypadku punktów objętych sytuacją brzegową.

Sytuacja brzegowa ma miejsce wówczas, gdy wybrana półprosta przechodzi przez wierzchołek najbardziej wysunięty w stronę ujemnych lub dodatnich wartości x. Na rysunku będą to zatem punkty $P_1$, $P_4$, oraz $P_5$. Wykluczyliśmy już sytuację, w której punkt $P$ leży na krawędzi wielokąta. Jeśli wykryjemy, że punkt ten ma taką samą współrzędną x‑ową co najbardziej wysunięte w lewo lub prawo punkty wielokąta, możemy od razu stwierdzić, że nie należy on do wielokąta. Musimy w tym celu sprawdzić, jaki jest zakres zajmowanych przez wielokąt współrzędnych. Wyszukujemy dwie wartości:

• $x_{max}$ — maksymalną wartość pierwszej współrzędnej ($x$) wierzchołków wielokąta,

• $x_{min}$ — minimalną wartość pierwszej współrzędnej ($x$) wierzchołków wielokąta.

Następnie sprawdzamy, czy $x_p=x_{max}$ lub $x_p=x_{min}$. Jeśli warunek jest spełniony, punkt $P$ nie leży wewnątrz wielokąta.

Rozwiązaliśmy wszystkie problematyczne sytuacje, zatem teraz możemy już przejść do głównej części algorytmu.

1. Narysuj półprostą wychodzącą z punktu, który sprawdzamy.

2. Przejdź po wszystkich krawędziach wielokąta i policz, ile z nich przecina narysowana w pierwszym kroku półprosta. W tym kroku pamiętamy, że przecięcie uznajemy, jeśli wypadło w pierwszym punkcie krawędzi, a nie uznajemy, jeśli wypadło w drugim punkcie.

3. Jeżeli policzona liczba jest parzysta, punkt leży poza wielokątem. W przeciwnym wypadku punkt należy do tego wielokąta.

Pozostaje tylko pytanie: jak sprawdzimy, czy półprosta przecina daną krawędź wielokąta?

Oznaczmy sprawdzaną krawędź jako parę punktów $(A,B)$, gdzie $A=\left(x_a,\ y_a\right)$, $B=\left(x_b,\ y_b\right)$.

Należy tu skorzystać z dwóch warunków.

Pierwszy z nich będzie sprawdzał, czy pierwsza współrzędna ($x$) punktu $P$ zawiera się między pierwszymi współrzędnymi krańców rozpatrywanej krawędzi. Dopuszczalna jest sytuacja, w której $x_p$ jest równe $x_a$, jednak nie może być równe $x_b$. Możliwe są dwie sytuacje:

Ra8RQGSlocPz4

Ilustracja

lub

R8R7CmKHDiGtn

Ilustracja

Drugi warunek, który ma być spełniony, powinien sprawdzać, czy punkt $P$ jest położony nad odcinkiem $AB$. Oznacza to, że $y_p$ musi być większe niż wartość prostej $AB$ w punkcie $x_p$.

Odwołując się do wiedzy z lekcji matematyki, możemy wyprowadzić równanie prostej $AB$:

Zatem ostateczna postać tego warunku to:

Jeżeli spełnione są jednocześnie oba warunki, wiemy, że półprosta przetnie bok wielokąta. Przedstawmy zatem algorytm w całości w postaci pseudokodu:

Specyfikacja problemu:

Dane:

• n — liczba wierzchołków wielokąta

• tab[1..n][1..2] — tablica uporządkowanych wierzchołków wielokąta; każdy wierzchołek jest reprezentowany przez tablicę dwóch liczb zmiennoprzecinkowych, z których pierwsza oznacza pierwszą współrzędną ($x$), a druga — drugą współrzędną ($y$)

• P[1,2] — sprawdzany punkt; tablica dwóch liczb zmiennoprzecinkowych, z których pierwsza oznacza pierwszą współrzędną ($x$), a druga — drugą współrzędną ($y$)

Wynik:

Program wypisuje, czy dany punkt P zawiera się wewnątrz wielokąta, czy nie.

funkcja czy_punkty_są_współliniowe(A[1..2], B[1..2], C[1..2])
	jeżeli (B[1] - A[1]) * (C[2] - A[2]) = (B[2] - A[2]) * (C[1] - A[1]):
		zwróć prawda
	zwróć fałsz

funkcja czy_punkt_należy_do_krawędzi(P[1..2], A[1..2], B[1..2])
	jeżeli czy_punkty_są_współliniowe(P, A, B):
		jeżeli (A[1] <= P[1] oraz P[1] <= B[1]) lub (A[1] >= P[1] oraz P[1] >= B[1]):
			jeżeli (A[2] <= P[2] oraz P[2] <= B[2]) lub (A[2] >= P[2] oraz P[2] >= B[2]):
				zwróć prawda
	zwróć fałsz

funkcja czy_półprosta_przecina_krawędź(P[1..2], A[1..2], B[1..2])
	// pierwszy warunek
	jeżeli (A[1] <= P[1] oraz P[1] < B[1]) lub (A[1] >= P[1] oraz P[1] > B[1]):
		// drugi warunek
		jeżeli P[2] > (A[2] - B[2]) / (A[1] - B[1]) * (P[1] - A[1]) + A[2]:
			zwróć prawda
	zwróć fałsz

// sprawdź, czy punkt P leży na krawędziach wielokąta
dla i = 1, 2, ..., n wykonuj:
	pierwszy_wierzchołek ← tab[i]
	jeżeli i = n:
		drugi_wierzchołek ← tab[1]
	w przeciwnym wypadku:
		drugi_wierzchołek ← tab[i + 1]
    
    jeżeli czy_punkt_należy_do_krawędzi(P, pierwszy_wierzchołek, drugi_wierzchołek) == prawda:
    	wypisz "Punkt P należy do wielokąta"
    	zakończ wykonywanie programu

// sprawdź, czy półprosta przecina wielokąt w najbardziej wysuniętych w lewo lub prawo punktach wielokąta
max_x ← tab[1][1]
min_x ← tab[1][1]

dla i = 2, 3, ..., n wykonuj:
	jeżeli tab[i][1] > max_x:
		max_x ← tab[i][1]
	w przeciwnym wypadku jeżeli tab[i][1] < min_x:
		min_x ← tab[i][1]
    
jeżeli P[1] = max_x lub P[1] = min_x:
    wypisz "Punkt P nie należy do wielokąta"
	zakończ wykonywanie programu

// policz, ile razy półprosta przecina wielokąt
przecięcia ← 0

dla i = 1, 2, ..., n wykonuj:
	pierwszy_wierzchołek ← tab[i]
	jeżeli i = n:
		drugi_wierzchołek ← tab[1]
	w przeciwnym wypadku:
		drugi_wierzchołek ← tab[i + 1]

	jeżeli czy_półprosta_przecina_krawędź(P, pierwszy_wierzchołek, drugi_wierzchołek) = prawda:
		przecięcia ← przecięcia + 1

jeżeli przecięcia mod 2 = 0:
	wypisz "Punkt P nie należy do wielokąta"
w przeciwnym wypadku:
	wypisz "Punkt P należy do wielokąta"
zakończ wykonywanie programu

Słownik