Algorytmy wyklady, Intersect, ANY-SEGMENTS_INTERSECT (S);


ANY-SEGMENTS_INTERSECT (S);

{ S jest zbiorem odcinków na płaszczyźnie; zakładamy,

że żaden odcinek nie jest prostopadły do osi Ox

oraz żadne trzy różne odcinki nie przecinają się w jednym

punkcie.

Procedura sprawdza czy w S istnieje co najmniej

jedna para odcinków przecinających się }

begin

T := ∅;

Utwórz listę LS posortowanych końców odcinków z S w kolejności

od najmniejszej współrzędnej x do największej ,

w przypadku równych -najpierw punkt o mniejszej współrzędnej y;

dla każdego zaznacz czy jest lewym czy prawym końcem odcinka;

for każdy punkt p z listy LS do

begin

if p jest lewym końcem odcinka s then

begin

INSERT (T,s);

if (ABOVE (T,s) istnieje i przecina s )

or ( BELOW (T,s) istnieje i przecina s )

then return TRUE

end;

if p jest prawym końcem odcinka s then

begin

if oba odcinki (ABOVE (T,s ) and (BELOW (T,s)) istnieją

and (ABOVE (T,s) przecina BELOW (T,s) )

then return TRUE;

DELETE (T,s);

end;

end;

return FALSE;

end;



Wyszukiwarka

Podobne podstrony:
Algorytmy wyklady, Metody tworzenia algorytmów
Algorytmy wyklady, Elementarne struktury danych
Algorytmy wyklady, Złożoność obliczeniowa algorytmów
Pojęcie algorytmu, wykłady i notatki, dydaktyka matematyki, matematyka przedszkole i 1-3
Algorytmy wyklad 1 id 57804 Nieznany
Algorytmy wyklad 9 10 id 57807 Nieznany (2)
Algorytmy wyklady, Listy
Algorytmy wyklad 6 7 id 57806 Nieznany
algorytmy wykładu
Inforamtyka Algorytmy wyklady
Algorytmy wyklad 4 5 id 57805 Nieznany
Algorytmy wyklady, Programowanie dynamiczne, MATRIX-CHAIN-ORDER ( p );
Algorytmy wykład
Algorytmy wykład2
Algorytmy wyklad 4 5
algorytmy wykładu
Algorytmy wyklady, Metody tworzenia algorytmów
Algorytmy wyklady, Elementarne struktury danych

więcej podobnych podstron