odcinek przecina prostą?
dwa odcinki się przecinają?
punkt leży wewnątrz trójkąta?
punkt leży wewnątrz wielokąta?

• jedna strona składa się z tych punktów (x,y), dla których Ax+By+C < 0,

• druga strona składa się z tych punktów (x,y), dla których Ax+By+C > 0,

• a przedzielające je prosta - z tych punktów (x,y), dla których Ax+By+C = 0.

Oczywiście to, która strona jest ''ujemna'', a która ''dodatnia'', zależy od wyboru równania ogólnego prostej: x-y = 0 i y-x = 0 to dwa równania ogólne tej samej prostej y = x, i strona ''ujemna'' dla jednego równania jest ''dodatnia'' dla drugiego równania:

Stronę prostej można wybrać, podając punkt, który do niej należy, np. strona prostej y = x do której należy punkt (1,0) jest ''dodatnia'' dla równania x-y = 0 i ''ujemna'' dla równania y-x = 0.

Dwa punkty P = (x₁,y₁) oraz P = (x₂,y₂)

• leżą po tej samej stronie prostej Ax+By+C = 0 gdy wyrażenie

  ( Ax1+By1+C)( Ax2+By2+C)

  jest dodatnie,

• leżą po przeciwnych stronach prostej Ax+By+C = 0 gdy wyrażenie

  ( Ax1+By1+C)( Ax2+By2+C)

  jest ujemne,

Półpłaszczyzny są ważne, bo każdy zbiór wypukły na płaszczyźnie jest częścią wspólną zawierających go półpłaszczyzn, a gdy zbiór jest wielokątem wystarczy skończona liczba półpłaszczyn - wyznaczonych przez boki wielokąta.

Warto pamiętać, że prosta przechodząca przez dwa różne punkty (a,b), (c,d) ma równanie ogólne

1.1  Czy odcinek przecina prostą?

Odcinek o danych końcach P = (x₁,y₁), Q = (x₂,y₂) przecina prostą o równaniu Ax+By+C = 0 wtedy i tylko wtedy, gdy jego końce nie leżą po jednej stronie prostej. Zatem są trzy możliwości:

• odcinek domknięty PQ nie przecina prostej Ax+By+C = 0 wtedy i tylko wtedy, gdy

  ( Ax1+By1+C)( Ax2+By2+C) > 0,

• odcinek otwarty PQ przecina prostą Ax+By+C = 0 wtedy i tylko wtedy, gdy

  ( Ax1+By1+C)( Ax2+By2+C) < 0,

• jeden z końców odcinka PQ leży na prostej Ax+By+C = 0 wtedy i tylko wtedy, gdy

  ( Ax1+By1+C)( Ax2+By2+C) = 0.

1.2  Czy dwa odcinki się przecinają?

> Jak sprawdzić, czy odcinki PQ i
> RS o końcach P = (x_P,y_P), Q = (x_Q,y_Q), R = (x_R,y_R), S = (x_S,y_S)
> się przecinają?

Metodą z punktu 1.1 sprawdzamy, czy odcinek PQ przecina prostą RS i czy odcinek RS przecina prostą PQ.

• Jeśli choć jeden z nich nie przecina prostej, zawierającej drugi, to oczywiście odcinki się nie przecinają.

• Jeśli każdy z nich przecina prostą, na której leży drugi, to punkt przecięcia tych prostych leży na każdym z odcinków, czyli odcinki się przecinają.

1.3  Czy punkt leży wewnątrz trójkąta?

> Dany jest trójkąt o wierzchołkach P = (x_P,y_P), Q = (x_Q,y_Q), R = (x_R,y_R).
> Jak sprawdzić, czy punkt (a,b) leży wewnątrz tego trójkąta?

Trójkąt jest częscią wspólną trzech półpaszczyzn: tych stron prostych, zawierających jego boki (czyli dwa wierzchołki), do których należy trzeci wierzchołek.

Właściwie odpowiedź można uznać za algorytm.

1. Według wzoru 1 piszemy równania prostych, zawierających boki trójkąta:

   APx+BPy+CP = 0 - prosta QR, AQx+BQy+CQ = 0 - prosta PR, ARx+BRy+CR = 0 - prosta PQ.

2. Dla każdego wierzchołka P,Q,R obliczamy znak wyrażenia

   ( APxP+BPyP+CP) ( APa+BPb+CP) , ( AQxQ+BQyQ+CQ) ( AQa+BQb+CQ) , ( ARxR+BRyR+CR) ( ARa+BRb+CR) .

   • Jeśli wszystkie te trzy wyrażenia są dodatnie, to (a,b) leży wewnątrz trójkąta DPQR.

   • Jeśli jedno z tych trzech wyrażeń jest równe 0, to albo trókąt jest odcinkiem, albo (a,b) leży na odpowiednim boku trójkąta.

   • Jeśli żadne z tych wyrażeń nie jest zerem, ale choć jedno jest ujemne, to (a,b) leży na zewnątrz DPQR.

1.4  Czy punkt leży wewnątrz wielokąta?

>Dane są wierzchołki P_i = (x_i,y_i), i = 1,2,...,n
>wielokąta, i punkt Q = (a,b).
>Jak sprawdzić, czy punkt Q leży wewnątrz wielokąta?

Sformułowanie zagadnienia nie jest jednoznaczne: nie stwierdzono, czy amana P₁P₂...P_nP₁ jest brzegiem badanego wielokąta.

• Jeśli jest, i jest łamaną zwyczajną (bez samoprzecięć), to trzeba najpierw zbadać wypukłość tego wielokąta i postepować odpowiednio do rezultatu.

• Jeśli zaś łamana P₁P₂...P_nP₁ nie musi być brzegiem badanego wielokąta, to sam spis (zbiór) wierzchoków określa wielokąt tylko przy dodatkowym założeniu, że chodzi o wielokąt wypukły.

A zatem pierwszy przypadek - wielokąt ograniczony łamaną zamknitą zwyczajną P₁P₂...P_nP₁:

1. Sprawdzenie wypukłości. Dla każdej prostej P_iP_i+1 i prostej P_nP₁ sprawdzamy metodą, opisaną na wstępie, czy pozostałe wierzchołki leżą po jednej stronie tej prostej. Jeśli tak, to badany wielokąt jest częścią wspólną półpłaszczyzn, więc jest wypukły.

2. Jeśli wielokąt okazał się wypukły, to aby sprawdzić, czy punkt Q leży wewnątrz niego, wystarczy sprawdzić - dla każdej z prostych P_iP_i+1 i prostej P_nP₁ - czy punkt Q leży po tej samej stronie prostej, co wierzchołek P_i+2 (wierzchołek P₁ dla i = n-1, wierzchoek P₂ dla i = n). Jeśli tak, to należy do każdej z półpłaszczyzn, których cześcią wspólną jest badany wielokąt, czyli leży wewnątrz wielokąta. Jeśli nie, to leży na zewnatrz lub na brzegu wielokąta.

3. Jeśli wielokąt okazał się niewypukły, to trzeba podzielić go na sumę wielokątów wypukłych. W tym celu szukamy nieprzedłużalnego łańcucha kolejnych wierzchołków P_iP_i+1...P_j takiego, że wszystkie pozostałe wierzchołki leżą po jednej stronie każdej prostej łączacej dwa kolejne wierzchołki w tym łańcuchu. Nieprzedłużalność oznacza, że ani prosta P_i-1P_i, ani prosta P_jP_j+1 nie mają już tej własności, tzn. wierzchołki wielokąta leżą po obu stronach każdej z tych prostych. Taki łańcuch wyznacza wystający ''róg'' wielokąta. Wielokąt przedstawiamy jako sumę wielokąta wypukłego P_iP_i+1...P_jP_i i wielokąta P₁P₂...P_i-1P_j+1...P_nP₁ (z odciętym ''rogiem''), który ma mniej wierzchołków. Punkt Q leży wewnątrz wielokąta P₁P₂...P_nP₁ wtedy i tylko wtedy, gdy leży wewnątrz wielokąta (wypukłego!) P_iP_i+1...P_jP_i lub leży na boku P_jP_i lub leży wewnątrz wielokąta P₁P₂...P_i-1P_j+1...P_nP₁.

Drugi przypadek - wielokąt jest powłoką wypukłą Conv(P₁,P₂, ...,P_n) zbioru danych punktów A = {P₁,P₂, ..., P_n}. W tym przypadku trzeba znaleźć łamaną, która jest brzegiem badanego wielokąta. Tworzymy dwa obiekty: podzbiór W zbioru {P₁,P₂, ...,P_n} - zbiór punktów wewnętrznych, i ciąg wierzchołków x. Zaczynamy od dowolnego punktu P_i i dla każdej prostej P_iP_j, j š i sprawdzamy, czy wszystkie pozostałe wierzchołki leżą po tej samej stronie prostej. Jeśli nie ma takiego punktu P_j, to punkt P_i przenosimy ze zbioru A do zbioru punktów wewnętrznych W. Jeśli istnieje taki punkt P_j, to punkt P_i przenosimy ze zbioru A na koniec ciągu wierzchołków x, i powtarzamy procedurę z punktem P_j zamiast P_i, aż okaże się, że ciągu wierzchołków nie da się przedłużyć. Wtedy sprawdzany punkt dopisujemy na końcu ciągu wierzchołków, a pozostałe w zbiorze A punkty przenosimy do zbioru W punktów wewnętrznych. Ciąg wierzchołków wyznacza łamaną zwyczajną, która ogranicza badany wielokąt, i zagadnienie sprowadziło się do pierwszego przypadku, przy czym już wiadomo, że badany wielokąt jest wypukły.

Geometria analityczna

Powrót do FAQ