Przecinanie się odcinków
1. Istota problemu
W niniejszym artykule mam zamiar przedstawić algorytm sprawdzania czy jakiekolwiek odcinki w danym zbiorze odcinków się przecinają. Odcinki umieszczone są na płaszczyźnie równolegle do osi OX lub OY. Pesymistyczny czas działania algorytmu to:
gdzie n to liczba wszystkich odcinków, a t to liczba znalezionych przecięć między odcinkami. Algorytm jest oparty o metodę zamiatania (można sobie wyobrazić prostą przechodząca wzdłuż jednej z osi układu współrzędnych (pionową czyli rownoległą do osi OY)).
2. Algorytm wygląda następująco:
1) Wczytuje n jako liczbę oznaczającą ilość odcinków. 2) Wczytuje współrzędne pojedynczego odcinka (należy pamiętać o tym że odcinki umieszczone są pionowo i poziomo w układzie współrzędnych, czyli względem siebie prostopadle lub równolegle, tak więc w danym algorytmie są dwie opcje): a) pierwsza z nich: jeśli odcinek wczytany ma współrzędne y-owe równe oraz x1<x2 – gdzie x1 to punkt oznaczający początek odcinka, zaś x2 koniec, to wczytany odcinek musi być poziomy. b) druga: jeśli wczytany odcinek ma równe współrzędne x-owe oraz y1<y2 – gdzie y1 to punkt oznaczający początek odcinka, zaś y2 to koniec, to wczytany odcinek jest pionowy. (początek odcinka i koniec odcinka to umowne nazwy, tak żeby algorytm był łatwiejszy do zrozumienia, początek odcinka będzie oznaczał punkt położony bliżej początku układu współrzędnych czyli punktu (0,0) względem drugiego punktu, należącego do tego odcinka) c) współrzędne wczytuje w następującej kolejności: - x1 y1 x2 y2, gdzie x1 oraz y1 oznaczają współrzędne początku odcinka, natomiast x2 oraz y2 koniec odcinka. - przydzielam każdemu odcinkowi numer identyfikacyjny oraz umieszczam go odpowiednio w tablicy. 3) Sortuję tablicę n odcinków po składowej x-owej rosnąco. 4) Dla każdego odcinka kolejno od najmniejszej współrzędnej x-owej: a) Jeśli v jest lewym punktem poziomego odcinka, wstaw go do drzewa binarnego posortowanego wg współrzędnej y odpowiadający mu odcinek. b) Jeśli v jest prawym punktem poziomego odcinka, to usuń z drzewa binarnego odpowiadający mu odcinek. c) Jeśli v jest górnym punktem pionowego odcinka, to wyszukaj wszystkie przecięcia tego odcinka z poziomymi odcinkami w drzewie binarnym takie, których wartości współrzędnej y znajdują się w przedziale wyznaczonym przez górny i dolny punkt tego odcinka. Wszystkie takie poziome odcinki przecinające się mogę wyznaczyć wyszukując je w drzewie. 5) następnie przechodzę drzewo metodą INORDER wypisując po kolei wszystkie pary przecinających się odcinków.
3. Złożoność, krótko:
Pierwszy krok (sortowanie) zajmuje czas
Dodawanie oraz usuwanie z BST zajmuje
na każdym kroku, więc czas dodawania oraz usuwania jest
Szukanie punktów, w których odcinki się przecinają jest ograniczone oczywiście liczbą t, czyli liczbą znalezionych przecięć. Skoro tak jest, więc całkowita złożoność algorytmu wynosi
4. Uwagi:
Do zrozumienia tego algorytmu potrzebna jest podstawowa wiedza z geometrii obliczeniowej oraz znajomość działania struktury – właściwej do tego zadania, aby uzyskać pożądaną złożoność – drzewa poszukiwań binarnych (ang. BST – Binary Serach Tree). BST używane tu jest w zasadzie z konieczności, dlatego że podstawowe operacje wykonywane na drzewie (czyli SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT oraz DELETE) wykonywane są w najgorszym (pesymistycznym) czasie
Wszystkie te funkcje jak i działanie drzewa opisane są szczegółowo w książce Thomasa Cormen’a, pt. „Wprowadzenie do algorytmów”, jak i również jeśli ktoś jest zainteresowany Diks. K z innymi współautorami, książka pt. „Algorytmy i struktury danych”. W linkach podanych niżej również znajduje się dużo przydatnych informacji dotyczących zrozumienia problemu.
Książki:
- Wprowadzenie do Algorytmów, Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest, The MIT Press, wydanie czwarte 1994
- Algorytmy i struktury danych, Banachowski L., Diks K., Rytter W., WNT (1996)
Linki:
- http://pl.wikipedia.org/wiki/Drzewo_poszukiwa%C5%84_binarnych
- http://cgm.cs.mcgill.ca/~perouz/cs251/testsolutions/cs251test2s.pdf
- http://pl.wikipedia.org/wiki/Drzewo_(informatyka)
Aby dodawać komentarze musisz być zalogowany!