Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00283 007796 13586504 na godz. na dobę w sumie
wyszukaj dokładnie | pobierz wtyczkę
Algorytmy w Perlu - książka
Algorytmy w Perlu - książka
Autor: , , Liczba stron: 676
Wydawca: Helion Język publikacji: polski
ISBN: 83-7197-913-4 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> perl - programowanie
Porównaj ceny (książka, ebook, audiobook).
Czytaj online.
Komentuj
Wielu programistów poszukuje książki, która przedstawiłaby implementacje znanych algorytmów w Perlu. Niestety w podręcznikach do tego języka trudno znaleźć informacje na ten temat. Informatycy opracowali wiele technik związanych z często spotykanymi problemami, takimi jak: Dzięki algorytmom przedstawionym w niniejszej książce będziesz mógł poradzić sobie z tymi problemami używając wydajnego i łatwego do nauczenia się języka, jakim jest Perl.

Autorzy zakładają, że opanowałeś już składnię Perla i znasz jego podstawowe funkcje. Książka 'Algorytmy w Perlu' przystępnie objaśni Ci, kiedy używać klasycznych technik programistycznych i w jakich rodzajach aplikacji znajdują one swoje zastosowanie, a przede wszystkim pokaże Ci, jak je implementować w Perlu.

Jeśli jesteś początkującym programistą, poznasz najważniejsze algorytmy, które pozwolą Ci rozwiązywać problemy programistyczne w sposób profesjonalny. Nawet jeśli znasz już podstawy algorytmiki, będziesz zapewne zaskoczony z jaką łatwością można je zastosować w Perlu. W książce znajdziesz nawet obowiązkowy program rysujący fraktale.

Jest to pierwsza książka spośród licznych pozycji poświęconych algorytmom, która demonstruje ich użycie za pomocą Perla.

Autorami są m.in. Jon Orwant, redaktor The Perl Journal i Jarkko Hietaniemi -- zarządzający biblioteką modułów CPAN. Wszyscy autorzy są stałymi współpracownikami CPAN, stąd wiele z przytoczonych tu fragmentów kodu możesz znaleźć w tej bibliotece. 'Poświęciłem lekturze wiele czasu przeznaczonego na sen -- tak ekscytująca jest ta książka'
Tom Christiansen

Znajdź podobne książki Ostatnio czytane w tej kategorii

Darmowy fragment publikacji:

IDZ DO IDZ DO PRZYK£ADOWY ROZDZIA£ PRZYK£ADOWY ROZDZIA£ SPIS TREĎCI SPIS TREĎCI Algorytmy w Perlu KATALOG KSI¥¯EK KATALOG KSI¥¯EK KATALOG ONLINE KATALOG ONLINE ZAMÓW DRUKOWANY KATALOG ZAMÓW DRUKOWANY KATALOG TWÓJ KOSZYK TWÓJ KOSZYK DODAJ DO KOSZYKA DODAJ DO KOSZYKA CENNIK I INFORMACJE CENNIK I INFORMACJE ZAMÓW INFORMACJE ZAMÓW INFORMACJE O NOWOĎCIACH O NOWOĎCIACH ZAMÓW CENNIK ZAMÓW CENNIK Autorzy: Jon Orwant, Jarkko Hietaniemi, John Macdonald T³umaczenie: S³awomir Dzieniszewski, Marcin Jêdrysiak ISBN: 83-7197-913-4 Tytu³ orygina³u: Mastering Algorithms with Perl Format: B5, stron: 680 Wielu programistów poszukuje ksi¹¿ki, która przedstawi³aby implementacje znanych algorytmów w Perlu. Niestety w podrêcznikach do tego jêzyka trudno znaleĥæ informacje na ten temat. Informatycy opracowali wiele technik zwi¹zanych z czêsto spotykanymi problemami, takimi jak: • Przybli¿one dopasowywanie tekstów (uwzglêdniaj¹ce literówki) • Znajdowanie korelacji w zbiorach danych • Algorytmy zwi¹zane z grami • Przewidywanie zjawisk (np. obci¹¿enia serwera WWW) • Dopasowywanie wielomianowe i za pomoc¹ funkcji sklejanych • Szyfrowanie informacji CZYTELNIA CZYTELNIA Dziêki algorytmom przedstawionym w niniejszej ksi¹¿ce bêdziesz móg³ poradziæ sobie z tymi problemami u¿ywaj¹c wydajnego i ³atwego do nauczenia siê jêzyka, jakim jest Perl. FRAGMENTY KSI¥¯EK ONLINE FRAGMENTY KSI¥¯EK ONLINE Wydawnictwo Helion ul. Chopina 6 44-100 Gliwice tel. (32)230-98-63 e-mail: helion@helion.pl Autorzy zak³adaj¹, ¿e opanowa³eġ ju¿ sk³adniê Perla i znasz jego podstawowe funkcje. Ksi¹¿ka „Algorytmy w Perlu” przystêpnie objaġni Ci, kiedy u¿ywaæ klasycznych technik programistycznych i w jakich rodzajach aplikacji znajduj¹ one swoje zastosowanie, a przede wszystkim poka¿e Ci, jak je implementowaæ w Perlu. Jeġli jesteġ pocz¹tkuj¹cym programist¹, poznasz najwa¿niejsze algorytmy, które pozwol¹ Ci rozwi¹zywaæ problemy programistyczne w sposób profesjonalny. Nawet jeġli znasz ju¿ podstawy algorytmiki, bêdziesz zapewne zaskoczony z jak¹ ³atwoġci¹ mo¿na je zastosowaæ w Perlu. W ksi¹¿ce znajdziesz nawet obowi¹zkowy program rysuj¹cy fraktale. Jest to pierwsza ksi¹¿ka spoġród licznych pozycji poġwiêconych algorytmom, która demonstruje ich u¿ycie za pomoc¹ Perla. Autorami s¹ m.in. Jon Orwant, redaktor The Perl Journal i Jarkko Hietaniemi — zarz¹dzaj¹cy bibliotek¹ modu³ów CPAN. Wszyscy autorzy s¹ sta³ymi wspó³pracownikami CPAN, st¹d wiele z przytoczonych tu fragmentów kodu mo¿esz znaleĥæ w tej bibliotece. „Poġwiêci³em lekturze wiele czasu przeznaczonego na sen — tak ekscytuj¹ca jest ta ksi¹¿ka” — Tom Christiansen Spis treści Przedmowa ..............................................................................................................7 Rozdział 1. Wprowadzenie...............................................................................15 Czym jest algorytm?...................................................a...................................................a...... .15 Efektywność...................................................a...................................................a.............. .......23 Rekurencyjnie powracające problemy w nauce o algorytmach....................................35 Rozdział 2. Podstawowe struktury danych.................................................39 Standardowe struktury danych Perla.................................................a...............................40 Budowanie naszej własnej struktury danych.............................................a......................41 Prosty przykład...................................................a...................................................a.......... .....42 Tablice Perla: wiele struktur danych w jednej...................................................a..............52 Rozdział 3. Zaawansowane struktury danych............................................61 Listy powiązane ...................................................a...................................................a.......... ....62 Zapętlone listy powiązane ...................................................a...............................................73 Oczyszczanie pamięci w Perlu ...................................................a........................................76 Listy dwustronnie powiązane ...................................................a.........................................79 Listy nieskończone ...................................................a...................................................a....... ..85 Koszt trawersowania...................................................a...................................................a......86 ....86 Drzewa binarne...................................................a...................................................a........... ............103 Sterty...................................................a...................................................a................... Sterty binarne ...................................................a...................................................a........... .....105 Sterta Janusowa...................................................a...................................................a.......... ...112 Moduły CPAN dla stert...................................................a..................................................112 Moduły CPAN, które pojawią się wkrótce................................................a.....................114 4 Algorytmy w Perlu Rozdział 4. Sortowanie...................................................................................115 Wprowadzenie do sortowania ...................................................a......................................115 Wszystkie sorty sortowania ...................................................a...........................................132 Podsumowanie naszych rozważań na temat sortowania ............................................164 Rozdział 5. Wyszukiwanie.............................................................................171 Wyszukiwanie w tablicy asocjacyjnej i inne sposoby odszukiwania danych bez wyszukiwania ...................................................a...................................................a........172 Wyszukiwania przeglądowe..................................................a...........................................173 Wyszukiwania generujące...................................................a..............................................191 Rozdział 6. Zbiory ...........................................................................................219 Diagramy Venna...................................................a...................................................a...........220 Tworzenie zbiorów...................................................a...................................................a.......221 Suma i część wspólna zbiorów...................................................a......................................225 Dwa rodzaje odejmowania zbiorów...................................................a.............................233 Zliczanie elementów zbiorów...................................................a........................................238 Wzajemne relacje zbiorów...............................................a..................................................238 Moduły CPAN związane ze zbiorami.................................................a............................243 Zbiory zbiorów........................................a...................................................a...................... ...248 Zbiory wielowartościowe...................................................a...............................................255 Podsumowanie informacji o zbiorach...................................................a..........................258 Rozdział 7. Macierze .......................................................................................259 Tworzenie macierzy ...................................................a...................................................a.....261 Manipulowanie indywidualnymi elementami macierzy.............................................261 Ustalanie rozmiarów macierzy...................................................a......................................262 Wyświetlanie macierzy...................................................a...................................................a262 Dodawanie stałej wartości lub mnożenie przez stałą...................................................a263 Przekształcanie macierzy.............................................a...................................................a...269 Mnożenie macierzy................................................a...................................................a..........271 Wydobywanie podmacierzy...................................................a..........................................273 Łączenie macierzy...............................................a...................................................a............ .274 Transpozycja macierzy...............................................a...................................................a.....275 Wyliczanie wyznacznika macierzy...................................................a...............................276 Eliminacja Gaussa ...................................................a...................................................a........ .277 Wartości własne i wektory własne ...................................................a...............................280 Problem mnożenia kilku macierzy ...................................................a...............................283 Dla tych, którzy chcieliby dowiedzieć się czegoś więcej .............................................286 Spis treści 5 Rozdział 8. Grafy .............................................................................................287 Wierzchołki i krawędzie...................................................a.................................................289 Grafy, które można wywieść z innych grafów...................................................a...........295 Atrybuty grafu ...................................................a...................................................a........... ...300 Sposoby reprezentowania grafów w komputerach.................................................a.........301 Trawersowanie grafu ...................................................a...................................................a...313 Ścieżki i mosty ...................................................a...................................................a.......... .....323 Biologia grafów: drzewa, lasy, skierowane grafy acykliczne, przodkowie i dzieci.......325 Klasy krawędzi i grafów..................................................a...................................................a329 Moduły CPAN dla grafów...................................................a.............................................362 Rozdział 9. Łańcuchy ......................................................................................363 Narzędzia wbudowane w Perla...................................................a....................................364 Algorytmy poszukujące wzorca w łańcuchu tekstu...................................................a......368 Algorytmy fonetyczne ...................................................a...................................................a.398 Odnajdywanie rdzenia wyrazu i problem odmiany wyrazów...................................400 Analiza składniowa...................................................a...................................................a......404 Kompresja danych...................................................a...................................................a........422 Rozdział 10. Algorytmy geometryczne...........................................................435 Odległość...................................................a...................................................a................ ........436 Pole, obwód i objętość...................................................a...................................................a..439 ........443 Kierunek...................................................a...................................................a................. Przecięcie...................................................a...................................................a............... .........444 Zawieranie punktów i wielokątów...................................................a...............................452 Granice............................................a...................................................a......................... ..........458 Najbliższa para punktów ...................................................a...............................................464 Algorytmy geometryczne — podsumowanie...................................................a.............471 Moduły graficzne CPAN...................................................a................................................471 Rozdział 11. Systemy liczbowe .......................................................................475 Liczby całkowite i rzeczywiste ...................................................a......................................475 Inne systemy liczbowe...................................................a...................................................a.486 Trygonometria...................................................a...................................................a............ Ciągi i szeregi ...................................................a...................................................a.......... ...496 ......497 Rozdział 12. Teoria liczb..................................................................................503 Podstawy teorii liczb...................................................a...................................................a....503 Liczby pierwsze ...................................................a...................................................a.......... ..508 Nierozwiązane problemy ...................................................a...............................................525 6 Algorytmy w Perlu Rozdział 13. Kryptografia ................................................................................529 Kwestie prawne ...................................................a...................................................a........... .530 Autoryzacja użytkowników za pomocą haseł ...................................................a............530 Autoryzacja danych — sumy kontrolne i inne metody ...............................................536 Ochrona danych — szyfrowanie...................................................a...................................540 Ukrywanie danych — steganografia ...................................................a............................556 Odsiewanie i wprowadzanie zakłóceń..................................................a..........................558 Zaszyfrowany kod Perla...............................a...................................................a..................562 Pozostałe kwestie...................................................a...................................................a........ ..564 Rozdział 14. Prawdopodobieństwo ................................................................565 ....566 Liczby losowe...................................................a...................................................a............ Zdarzenia ...................................................a...................................................a................ .......568 Permutacje i kombinacje...................................................a.................................................570 Rozkłady prawdopodobieństwa ...................................................a...................................573 Rzut kostką — rozkład równomierny...................................................a..........................575 Nieciągłe rozkłady nierównomierne ...................................................a............................580 Prawdopodobieństwo warunkowe.................................................a.................................587 Nieskończone rozkłady nieciągłe.............................................a........................................588 Rozkłady ciągłe ...................................................a...................................................a.......... ...589 Inne rodzaje rozkładów prawdopodobieństwa...................................................a..........590 Rozdział 15. Statystyka....................................................................................595 Parametry statystyczne...................................................a...................................................a596 Testy istotności...................................................a...................................................a......... Korelacja...................................................a...................................................a................ .....604 .........615 Rozdział 16. Analiza numeryczna ..................................................................621 Obliczanie pochodnych i całek...................................................a......................................622 Rozwiązywanie równań ...................................................a.................................................629 Interpolacja, ekstrapolacja i dopasowywanie krzywej .................................................636 Dodatek A Bibliografia..................................................................................643 Dodatek B Zestaw znaków ASCII ..............................................................647 Skorowidz ............................................................................................................651 10 Algorytmy geometryczne Nie niszcz moich kół! — Archimedes (287 – 212 p.n.e.) Geometria nie wymaga wprowadzenia. Jest to najbardziej wizualna dziedzina matema- tyki, dzięki której możliwe jest wyświetlanie obrazu na ekranie monitora. Ten rozdział przedstawia algorytmy pozwalające na wykonanie poniższych zadań: Tworzenie grafiki zawierającej hiperodnośniki (mapy obrazu) W jaki sposób można sprawdzić, czy użytkownik kliknął myszą w obszarze o dziwnych kształtach? Szczegóły można odnaleźć w podrozdziale „Zawieranie punktów i wielokątów”. Nakładanie okien Jak można otworzyć nowe okno, aby w minimalnym stopniu zasłaniało już istniejące okna? Zobacz podrozdział „Granice”. Kartografia W jaki sposób można oznaczyć obszar ograniczający grupę rozsianych punktów? Zobacz podrozdział „Granice”. Symulacje Które z 10 000 punktów znajdują się najbliżej siebie, co oznacza niebezpieczeństwo zderzenia? Odpowiedź znajduje się w podrozdziale „Najbliższa para punktów”. W tym rozdziale przedstawiane są różne wzory i algorytmy geometryczne. Znajdujące się tu przykłady stanowią tylko komponenty, które powinny być ulepszane przez Ciebie, Czytelniku, gdyż nie jesteśmy w stanie przewidzieć wszystkich przykładów ich zasto- sowania. Większość programów została ograniczona do pracy tylko w dwóch wymiarach. Nie są tu również poruszane zaawansowane zagadnienia, które można znaleźć w książkach poświęconych grafice komputerowej, takie jak śledzenie promieni (ang. ray tracing), oświe- tlanie sceny, animacja lub mapowanie tekstur. Jedynym wyjątkiem są tu krzywe złożone, 436 Rozdział 10. Algorytmy geometryczne które zostały omówione w rozdziale 16. poświęconym analizie numerycznej. Zalecana literatura poświęcona grafice to m.in. książka „Computer Graphics: Principles and Prac- tice” (autorstwa Foleya, van Dama, Feinera i Hughesa) oraz seria książek „Graphics Gems”. Pod koniec rozdziału znajdują się informacje dotyczące obsługi okien, tworzenia grafiki biznesowej, języka OpenGL (język grafiki trójwymiarowej) oraz języka VRML (Virtual Reality Markup Language). Prawie wszystkie procedury z tego rozdziału akceptują współrzędne przekazywane jako płaskie listy liczb. Aby możliwe było utworzenie interfejsu do już istniejących programów, może wystąpić konieczność dokonania modyfikacji tych procedur, dzięki czemu możliwe będzie przekazywanie punktów, prostych i wielokątów poprzez tablice lub tablice aso- cjacyjne. Ta metoda będzie także szybsza w przypadku dużej ilości danych. Więcej infor- macji na ten temat można znaleźć w rozdziale 1. Należy pamiętać o pewnej bardzo istotnej kwestii. Wiele problemów geometrycznych ma specjalne przypadki, które wymagają zwrócenia dodatkowej uwagi. Wiele algorytmów nie działa poprawnie dla wklęsłych obiektów, przez co przed użyciem algorytmu należy podzielić takie obiekty na mniejsze, wypukłe fragmenty. Skomplikowane obiekty, takie jak drzewa, ludzie oraz potwory z filmów SF, są zwykle reprezentowane w postaci wielo- kątów (najczęściej trójkątów lub czterościanów, jeśli są to obiekty trójwymiarowe). Zde- rzenia takich obiektów są sprawdzane przy użyciu powłok wypukłych prostopadłościanów ograniczających. Więcej informacji na ten temat można znaleźć w dalszej części rozdziału. Odległość Jedną z podstawowych koncepcji geometrycznych jest odległość między dwoma obiektami. Odległość euklidesowa Istnieje wiele sposobów definiowania odległości między dwoma punktami, ale najczę- ściej używaną i najbardziej intuicyjną definicją jest odległość euklidesowa, czyli odległość w linii prostej1. Aby uzyskać tę odległość, należy obliczyć różnice w położeniu dla każdej osi, zsumować kwadraty różnic i obliczyć pierwiastek kwadratowy tej sumy. W przypadku dwóch wymiarów sprowadza się to do znajomego twierdzenia Pitagorasa2: d = (x 1 − x 0 ) 2 + (y − y )2 0 1 Rysunek 10.1 przedstawia odległość euklidesową dla różnej liczby wymiarów. Ostatnie dwa przykłady są jedynie projekcją trzech i czterech wymiarów na kartkę papieru. 1 Euklides — ok. 370 p.n.e. 2 Pitagoras — 750 – 490 p.n.e. Odległość 437 Rysunek 10.1. Odległość euklidesowa w jednym, dwóch, trzech i czterech wymiarach Przedstawiona poniżej procedura służy do obliczania odległości euklidesowej w dowolnej liczbie wymiarów. # Procedura odleglosc( @p ) oblicza odleglosc euklidesowa pomiedzy dwoma # punktami o d wymiarow, dla ktorych istnieje 2 * d wspolrzednych. # Dla przykladu, para punktow trojwymiarowych powinna byc przekazana do tej # procedury jako ( $x0, $y0, $z0, $x1, $y1, $z1 ). sub odleglosc { my @p = @_; # Wspolrzedne punktow. my $d = @p / 2; # Liczba wymiarow. # Procedura zostala zoptymalizowana dla przypadku z dwoma wymiarami. return sqrt( ($_[0] - $_[2])**2 + ($_[1] - $_[3])**2 ) if $d == 2; my $S = 0; # Suma kwadratow. my @p0 = splice @p, 0, $d; # Uzyskanie punktu startowego. for ( my $i = 0; $i $d; $i++ ) { my $di = $p0[ $i ] - $p[ $i ]; # Roznica... $S += $di * $di; # ...podniesiona do kwadratu i zsumowana. } return sqrt( $S ); } Odległość euklidesowa pomiędzy punktami (3, 4) i (10, 12) może być obliczona w nastę- pujący sposób: print odleglosc( 3,4, 10,12); 10.6301458127346 Odległość Manhattan Kolejną miarą odległości jest odległość Manhattan, która została przedstawiona graficznie na rysunku 10.2. Nazwa tej odległości jest związana z prostokątną siatką, zgodnie z którą ułożone są ulice w Nowym Jorku. Taksówkarze jeżdżący po tym mieście zwykle mierzą wszystko odległością Manhattan, podczas gdy piloci śmigłowców są przyzwyczajeni do odległości euklidesowej. 438 Rozdział 10. Algorytmy geometryczne Rysunek 10.2. Odległość Manhattan W celu obliczenia odległości Manhattan zamiast potęgowania różnic między punktami należy dokonać ich sumowania. Poniżej przedstawiono odpowiednią procedurę. # odleglosc_manhattan( @p ) # Oblicza odleglosc Manhattan pomiedzy dwoma # punktami o d wymiarow, dla ktorych istnieje 2 * d wspolrzednych. # Dla przykladu, para punktow trojwymiarowych powinna byc przekazana do tej # procedury jako ( $x0, $y0, $z0, $x1, $y1, $z1 ). sub odleglosc_manhattan { my @p = @_; # Wspolrzedne punktow. my $d = @p / 2; # Liczba wymiarow. my $S = 0; # Suma kwadratow. my @p0 = splice @p, 0, $d; # Uzyskanie punktu startowego. for ( my $i = 0; $i $d; $i++ ) { my $di = $p0[ $i ] - $p[ $i ]; # Roznica... $S += abs $di; # ...zsumowanie absolutnej wartosci. } return $S; } Oto przykładowa odległość Manhattan między punktami (3, 4) i (10, 12): print odleglosc_manhattan( 3, 4, 10, 12); 15 Maksymalna odległość Czasami odległość najlepiej zdefiniować jako największą różnicę między współrzędnymi: d = max di, gdzie di jest różnicą i-tej współrzędnej. Jeśli odległość Manhattan stanowi przybliżenie pierwszego stopnia odległości (ponieważ różnice między współrzędnymi są podnoszone do potęgi 1), to odległość euklidesowa jest przybliżeniem drugiego stopnia. Granicą tego ciągu jest maksymalna odległość: ∞ ∑k d k i k=1 Innymi słowy, wraz ze wzrostem k zaczyna dominować maksymalna odległość, natomiast w nieskończoności dominuje ona już całkowicie. Pole, obwód i objętość 439 Odległość na powierzchni kulistej Najkrótsza odległość na powierzchni kulistej nosi nazwę odległości koła wielkiego. Uzy- skanie prawidłowego wzoru stanowi dobre zadanie trygonometryczne, ale programista może po prostu skorzystać z funkcji great_circle_distance(), która jest dostępna w module Math::Trig dołączonym do Perla w wersji 5.005_03 lub nowszej. Choć ten moduł znajduje się także we wcześniejszych wersjach Perla, to nie zawiera funkcji great_circle_ distance(). Poniżej pokazano sposób, w jaki można obliczyć przybliżoną odległość w kilometrach między Londynem (51,3° N, 0,5° W) oraz Tokio (35,7° N, 139,8° E). #!/usr/bin/perl use Math::Trig qw(great_circle_distance deg2rad); # Prosze zauwazyc odejmowanie szerokosci geograficznej od 90 stopni; # fi zero znajduje sie na biegunie polnocnym. @londyn = (deg2rad(- 0.5), deg2rad(90 - 51.3)); @tokio = (deg2rad( 139.8), deg2rad(90 - 35.7)); # 6378 to promien rownikowy Ziemi. print great_circle_distance(@londyn, @tokio, 6378); Odległość między Londynem i Tokio wynosi: 9605.26637021388 Szerokość geograficzna jest odejmowana od 90, ponieważ funkcja great_circle_ distance() wykorzystuje azymutowe współrzędne sferyczne. φ=0 wskazuje kierunek z bie- guna północnego, podczas gdy w innych miejscach świata jest to kierunek od równika. Z tego powodu należy odwrócić współrzędne o 90 stopni. Więcej informacji na ten temat można odnaleźć w dokumentacji modułu Math::Trig. Oczywiście wynik nie jest dokładny, ponieważ Ziemia nie jest idealną kulą, a 0,1° stopnia na tych szerokościach geograficznych wynosi około 8 km. Pole, obwód i objętość Ponieważ uzyskaliśmy już niezbędne informacje na temat odległości, możemy zająć się tematyką pola, obwodu i objętości. Trójkąt Pole trójkąta może być obliczone na wiele sposobów, które są zależne od dostępnych infor- macji. Na rysunku 10.3 przedstawiono jedną z najstarszych metod obliczania pola trójkąta, znaną jako wzór Herona.3 3 Heron żył w latach 65 – 120 n.e. 440 Rozdział 10. Algorytmy geometryczne Rysunek 10.3. Wzór Herona pozwala na obliczenie pola trójkąta, jeśli znana jest długość jego boków Parametrami poniższej procedury implementującej wzór Herona mogą być zarówno długości boków trójkąta, jak i jego wierzchołki. W tym drugim przypadku procedura pole_trojkata_heron() obliczy długości boków z użyciem odległości euklidesowej: #!/usr/bin/perl # pole_trojkata_heron( $dlugosc_pierwszego_boku, # $dlugosc_drugiego_boku, # $dlugosc_trzeciego_boku ) # Mozliwe jest takze podanie szesciu argumentow, ktore beda trzema parami # wspolrzednych (x,y) rogow trojkata. # Procedura zwraca pole trojkata. sub pole_trojkata_heron { my ( $a, $b, $c ); if ( @_ == 3 ) { ( $a, $b, $c ) = @_ } elsif ( @_ == 6 ) { ( $a, $b, $c ) = ( odleglosc( $_[0], $_[1], $_[2], $_[3] ), odleglosc( $_[2], $_[3], $_[4], $_[5] ), odleglosc( $_[4], $_[5], $_[0], $_[1] ) ); } my $s = ( $a + $b + $c ) / 2; # Parametr posredni. return sqrt( $s * ( $s - $a ) * ( $s - $b ) * ( $s - $c ) ); } print pole_trojkata_heron(3, 4, 5), , pole_trojkata_heron( 0, 1, 1, 0, 2, 3 ), ; Uruchomienie procedury da następujące wyniki: 6 2 Pole wielokąta Pole wielokąta wypukłego może być obliczone poprzez podzielenie go na kilka trójkątów, a następnie zsumowanie ich pól, co pokazano na rysunku 10.4. Sytuacja staje się bardziej skomplikowana w przypadku wielokątów wklęsłych, gdyż ko- nieczne jest zignorowanie „dziur”. Znacznie prostszym sposobem jest użycie wyznacz- ników, które zostały omówione bliżej w rozdziale 7. poświęconym macierzom. Tę metodę przedstawiają rysunek 10.5 oraz poniższy wzór: A = 1 2 0  x   x1 + y 0 y1 x 1 x 2 y 1 y 2 + ...+ x n−1 y n−1 x 0 y 0    Pole, obwód i objętość 441 Rysunek 10.4. Podzielone na trójkąty wielokąty wypukłe i wklęsłe Rysunek 10.5. Wyznaczanie pól przez wyznaczniki Każdy wyznacznik wyznacza pole prostokąta zdefiniowanego przez dwa wierzchołki wielokąta. Ponieważ każda krawędź wieloboku dzieli prostokąt na pół, to obliczone pole prostokąta należy podzielić przez 2. Nakładające się fragmenty prostokątów (prawy wie- lokąt na rysunku 10.5) mogą być zignorowane. Proszę zauważyć, jak przedstawiony powyżej wzór łączy ostatni punkt — (xn-1, yn-1) — z pierwszym punktem — (x0, y0). Jest to naturalne, ponieważ należy uwzględnić wszyst- kie n krawędzi wielokąta, co oznacza zsumowanie dokładnie n wyznaczników. W tym przypadku potrzebny jest wyznacznik macierzy 2 x 2, co jest proste. Poniżej przedstawiono odpowiednią procedurę. # wyznacznik( $x0, $y0, $x1, $y1 ) # Procedura oblicza wyznacznik dla czterech elementow macierzy # podanych jako argumenty. # sub wyznacznik { $_[0] * $_[3] - $_[1] * $_[2] } Teraz możemy już obliczyć pole wielokąta: # pole_wielokata( @xy ) # Procedura oblicza pole wielokata z uzyciem wyznacznika. Do procedury # nalezy przekazac punkty w postaci ( $x0, $y0, $x1, $y1, $x2, $y2, ...). # sub pole_wielokata { my @xy = @_; 442 Rozdział 10. Algorytmy geometryczne my $A = 0; # Pole. # Polaczenie ostatniego i pierwszego punktu jest wykonywane juz na poczatku # procedury, a nie na jej koncu (punkt [-2, -1] ponizej). for ( my ( $xa, $ya ) = @xy[ -2, -1 ]; my ( $xb, $yb ) = splice @xy, 0, 2; ( $xa, $ya ) = ( $xb, $yb ) ) { # Przejscie do kolejnego punktu. $A += wyznacznik( $xa, $ya, $xb, $yb ); } # Jesli punkty zostaly podane w kierunku przeciwnym do ruchu wskazowek # zegara, to zmienna $A bedzie miala wartosc ujemna. Z tego powodu nalezy # obliczyc wartosc absolutna. return abs $A / 2; } Pole pięciokąta zdefiniowanego przez punkty (0, 1), (1, 0), (3, 2), (2, 3) i (0, 2) może być obliczone w następujący sposób: print pole_wielokata( 0, 1, 1, 0, 3, 2, 2, 3, 0, 2 ), ; Wynik wynosi: 5 Należy pamiętać, że kolejne punkty muszą być podane w kolejności zgodnej lub przeciw- nej do kierunku ruchu wskazówek zegara (bliższe wyjaśnienia można odnaleźć w kolej- nym podrozdziale). Przekazanie punktów do procedury w innej kolejności oznacza inną definicję prostokąta, co pokazano na poniższym przykładzie: print pole_wielokata( 0, 1, 1, 0, 0, 2, 3, 2, 2, 3 ), ; Przeniesienie ostatniego punktu do środka dało w efekcie wynik równy: 1 Obwód wielokąta Procedura służąca do obliczania pola wielokąta może być użyta także do uzyskania jego obwodu. W tym celu wystarczy zsumować długości, a nie wyznaczniki. Poniżej przed- stawiono odpowiednią procedurę: # obwod_wielokata( @xy ) # Procedura oblicza dlugosc obwodu wielokata. Do procedury nalezy # przekazac punkty w postaci ( $x0, $y0, $x1, $y1, $x2, $y2, ...). # sub obwod_wielokata { my @xy = @_; my $P = 0; # Obwod. # Polaczenie ostatniego i pierwszego punktu jest wykonywane juz na poczatku # procedury, a nie na jej koncu (punkt [-2, -1] ponizej). for ( my ( $xa, $ya ) = @xy[ -2, -1 ]; Kierunek 443 my ( $xb, $yb ) = splice @xy, 0, 2; ( $xa, $ya ) = ( $xb, $yb ) ) { # Przejscie do kolejnego punktu. $A += dlugosc( $xa, $ya, $xb, $yb ); } return $P / 2; } Obwód pięciokąta z poprzedniego przykładu można obliczyć w następujący sposób: print obwod_wielokata( 0, 1, 1, 0, 3, 2, 2, 3, 0, 2 ), ; Wynik to: 8.89292222699217 Kierunek Czasami warto wiedzieć, czy obiekty znajdują się na prawo (zgodnie z kierunkiem ruchu wskazówek zegara) lub na lewo od nas (przeciwnie do kierunku ruchu wskazówek zegara). Może to być przydatne na przykład do ustalenia, czy dany punkt znajduje się wewnątrz trójkąta. W tym rozdziale ograniczymy się jedynie do dwóch wymiarów, ponieważ trzy wymiary zmieniają znaczenie określeń „lewo” i „prawo” w zależności od kierunku wy- branego jako „góra”. Dla dowolnych trzech punktów możliwe jest ustalenie, czy tworzą one ścieżkę zgodną lub przeciwną do kierunku ruchu wskazówek zegara (a być może nie istnieje żadna taka ścieżka). Punkty (1, 1), (4, 3) i (4, 4) na rysunku 10.6 tworzą ścieżkę zgodną z kierunkiem ruchu wskazówek zegara (ścieżka kieruje się w lewo), natomiast punkty (1, 1), (4, 3) i (7, 4) tworzą ścieżkę o przeciwnym kierunku (skierowaną w prawo). Rysunek 10.6. Dwie ścieżki — jedna skierowana w lewo, druga w prawo 444 Rozdział 10. Algorytmy geometryczne Parametrami procedury kierunek() są trzy punkty, natomiast zwracana jest pojedyncza liczba. Jeśli zwrócona zostanie wartość dodatnia, to ścieżka przechodząca przez wszystkie trzy punkty jest zgodna z kierunkiem ruchu wskazówek zegara. Liczba ujemna oznacza ścieżkę przeciwną do kierunku ruchu wskazówek zegara, natomiast wartość bliska 0 oznacza, że trzy punkty znajdują się na linii prostej. # kierunek( $x0, $y0, $x1, $y1, $x2, $y2 ) # Procedura zwraca wartosc dodatnia, jesli przesuwajac sie z p0 (x0, y0) # do przez p1 do p2 nalezy skrecic w prawo, wartosc ujemna, jesli nalezy # skrecic w lewo. # Zero jest zwracane w przypadku, gdy wszystkie trzy punkty leza na tej samej # linii prostej. Nalezy jednak uwazac na bledy zmiennoprzecinkowe. # sub kierunek { my ( $x0, $y0, $x1, $y1, $x2, $y2 ) = @_; return ( $x2 - $x0 ) * ( $y1 - $y0 ) - ( $x1 - $x0 ) * ( $y2 - $y0 ); } Np. poniższe wywołania: print kierunek( 1, 1, 4, 3, 4, 4 ), ; print kierunek( 1, 1, 4, 3, 7, 5 ), ; print kierunek( 1, 1, 4, 3, 7, 4 ), ; zwrócą wartości: -3 0 3 Innymi słowy, punkt (4, 4) znajduje się na lewo (wartość ujemna) od wektora przebiegają- cego od (1, 1) do (4, 3), punkt (7, 5) znajduje się na tym wektorze (wartość zero), natomiast punkt (7, 4) znajduje się na prawo (wartość dodatnia) od tego wektora. Procedura kierunek() stanowi spłaszczoną, dwuwymiarową wersję iloczynu wekto- rowego. Iloczyn wektorowy jest obiektem trójwymiarowym, który wskazuje na zewnątrz od płaszczyzny zdefiniowanej przez wektory p0 – p1 oraz p1 – p2. Przecięcie W tej części rozdziału będziemy często wykorzystywali podprocedurę epsilon() do obliczeń zmiennoprzecinkowych. Można wybrać dowolną wartość epsilon, ale zalecamy użycie wartości równej 1e–10: sub epsilon () { 1E-10 } Szybsza wersja tej procedury to: sub constant epsilon = 1E-10; Więcej informacji na ten temat znajdziesz w rozdziale 11. poświęconym systemom licz- bowym. Przecięcie 445 Punkt przecięcia prostych Istnieją dwie odmiany przecięcia prostej. W ogólnym przypadku linie mogą mieć dowolne nachylenie, natomiast w bardziej restrykcyjnym przypadku wszystkie linie muszą być poziome lub pionowe; ten przypadek jest nazywany przecięciem Manhattan. Przecięcie prostych — ogólny przypadek W celu odnalezienia punktu przecięcia dwóch prostych wystarczy tylko odnaleźć miejsce, w którym krzyżują się proste y0 = box + a0 i y1 = b1x + a1. Pomocne tu będą techniki opisane w rozdziałach 7. i 16. poświęcone rozwiązywaniu równań i eliminacji Gaussa, ale trzeba pamiętać o możliwości wystąpienia pewnych problemów. Aby uniknąć błędów dzielenia przez 0, należy zwrócić uwagę na przypadek, w którym jedna z linii jest pozioma lub pionowa. Specjalnym przypadkiem są również proste równoległe. Rysunek 10.7 ilustruje różne rodzaje przecięcia prostych. Rysunek 10.7. Przecięcia prostych: przypadek ogólny, prosta pozioma i pionowa oraz proste równoległe Obecność tych specjalnych przypadków sprawia, że algorytm obliczający punkt przecięcia prostych staje się dość skomplikowany. Również implementacja tego algorytmu wymaga dużej ilości kodu: # przeciecie_prostych( $x0, $y0, $x1, $y1, $x2, $y2, $x3, $y3 ) # # Procedura oblicza punkt przeciecia odcinkow # (x0,y0)-(x1,y1) i (x2,y2)-(x3,y3). # # Mozliwe jest takze podanie czterech argumentow decydujacych # o nachyleniu obu prostych oraz punktach przeciecia z osia y. Innymi slowy, # jesli obie proste zostana przedstawione jako y = ax+b, to nalezy podac # dwie wartosci a i dwie wartosci b . # # Procedura przeciecie_prostych() zwraca trzy wartosci ($x, $y, $s) dla punktu # przeciecia, gdzie $x i $y to wspolrzedne tego punktu, a $s jest prawda, # jesli odcinki przecinaja sie, lub falsz, jesli odcinki nie maja punktu # przeciecia (ale ekstrapolowane proste przecinalyby sie). # # W innych przypadkach zwracany jest ciag opisujacy przyczyne, dla ktorej # odcinki nie przecinaja sie: # poza prostopadloscianem ograniczajacym # rownolegle # rownolegle wspolliniowe # rownolegle poziome # rownolegle pionowe 446 Rozdział 10. Algorytmy geometryczne # Ze wzgledu na kontrole prostopadloscianow ograniczajacych przypadki # rownolegle poziome i rownolegle pionowe nigdy nie wystepuja. # (Prostopadlosciany ograniczajace zostana omowione w dalszej czesci # rozdzialu.) # sub przeciecie_prostych { my ( $x0, $y0, $x1, $y1, $x2, $y2, $x3, $y3 ); if ( @_ == 8 ) { ( $x0, $y0, $x1, $y1, $x2, $y2, $x3, $y3 ) = @_; # Prostopadlosciany ograniczajace dziela proste na odcinki. # Procedura prostopadloscian_ograniczajacy() zostanie zdefiniowana # w dalszej czesci rozdzialu. my @prostokat_a = prostopadloscian_ograniczajacy( 2, $x0, $y0, $x1, $y1 ); my @prostokat_b = prostopadloscian_ograniczajacy( 2, $x2, $y2, $x3, $y3 ); # Po usunieciu tego testu odcinki stalyby sie nieskonczonymi prostymi. # Procedura prostopadloscian_ograniczajacy_przeciecie() zostanie # zdefiniowana w dalszej czesci rozdzialu. return poza prostopadloscianem ograniczajacym unless prostopadloscian_ograniczajacy_przeciecie( 2, @prostokat_a, @prostokat_b ); } elsif ( @_ == 4 ) { # Forma parametryczna. $x0 = $x2 = 0; ( $y0, $y2 ) = @_[ 1, 3 ]; # Nalezy pomnozyc przez mnoznik , aby uzyskac wystarczajaca wielkosc. my $abs_y0 = abs $y0; my $abs_y2 = abs $y2; my $mnoznik = 10 * ( $abs_y0 $abs_y2 ? $abs_y0 : $abs_y2 ); $x1 = $x3 = $mnoznik; $y1 = $_[0] * $x1 + $y0; $y3 = $_[2] * $x2 + $y2; } my ($x, $y); # Jeszcze nieustalony punkt przeciecia. my $dy10 = $y1 - $y0; # dyPQ, dxPQ to roznice wspolrzednych my $dx10 = $x1 - $x0; # miedzy punktami P i Q. my $dy32 = $y3 - $y2; my $dx32 = $x3 - $x2; my $dy10z = abs( $dy10 ) epsilon; # Czy roznica $dy10 jest zerowa? my $dx10z = abs( $dx10 ) epsilon; my $dy32z = abs( $dy32 ) epsilon; my $dx32z = abs( $dx32 ) epsilon; my $dyx10; # Nachylenie. my $dyx32; $dyx10 = $dy10 / $dx10 unless $dx10z; $dyx32 = $dy32 / $dx32 unless $dx32z; # Po uzyskaniu wszystkich roznic i nachylen mozna wykonac rozpoznanie # specjalnych przypadkow z poziomymi i pionowymi prostymi. # Nachylenie rowne zero oznacza pozioma prosta. unless ( defined $dyx10 or defined $dyx32 ) { return rownolegle pionowe ; } elsif ( $dy10z and not $dy32z ) { # Pierwsza prosta pozioma. $y = $y0; $x = $x2 + ( $y - $y2 ) * $dx32 / $dy32; Przecięcie 447 } elsif ( not $dy10z and $dy32z ) { # Druga prosta pozioma. $y = $y2; $x = $x0 + ( $y - $y0 ) * $dx10 / $dy10; } elsif ( $dx10z and not $dx32z ) { # Pierwsza prosta pionowa. $x = $x0; $y = $y2 + $dyx32 * ( $x - $x2 ); } elsif ( not $dx10z and $dx32z ) { # Druga prosta pionowa. $x = $x2; $y = $y0 + $dyx10 * ( $x - $x0 ); } elsif ( abs( $dyx10 - $dyx32 ) epsilon ) { # Obie wartosci nachylenia sa zaskakujaco zblizone. # Prawdopodobnie jest to przypadek rownoleglych prostych wspolliniowych # lub zwykle proste rownolegle. # Kontrola prostokatow ograniczajacych spowodowala juz odrzucenie # przypadkow rownolegle poziome i rownolegle pionowe . my $ya = $y0 - $dyx10 * $x0; my $yb = $y2 - $dyx32 * $x2; return rownolegle wspolliniowe if abs( $ya - $yb ) epsilon; return rownolegle ; } else { # Nie wystapil zaden specjalny przypadek. # Obie proste rzeczywiscie sie przecinaja. $x = ($y2 - $y0 + $dyx10*$x0 - $dyx32*$x2)/($dyx10 - $dyx32); $y = $y0 + $dyx10 * ($x - $x0); } my $h10 = $dx10 ? ($x - $x0) / $dx10 : ($dy10 ? ($y - $y0) / $dy10 : 1); my $h32 = $dx32 ? ($x - $x2) / $dx32 : ($dy32 ? ($y - $y2) / $dy32 : 1); return ($x, $y, $h10 = 0 $h10 = 1 $h32 = 0 $h32 = 1); } Na rysunku 10.8 przedstawiono kilka przykładów przecinających się prostych. Rysunek 10.8. Przykłady przecinających się prostych 448 Rozdział 10. Algorytmy geometryczne Procedura przeciecie_prostych() zostanie wykorzystana do sprawdzenia sześciu potencjalnych przypadków przecinających się prostych: print @{[przeciecie_prostych( 1, 1, 5, 5, 1, 4, 4, 1 )]} ; print @{[przeciecie_prostych( 1, 1, 5, 5, 2, 4, 7, 4 )]} ; print @{[przeciecie_prostych( 1, 1, 5, 5, 3, 0, 3, 6 )]} ; print @{[przeciecie_prostych( 1, 1, 5, 5, 5, 2, 7, 2 )]} ; print przeciecie_prostych( 1, 1, 5, 5, 4, 2, 7, 5 ), ; print przeciecie_prostych( 1, 1, 5, 5, 3, 3, 6, 6 ), ; Poniżej przedstawiono wyniki: 2.5 2.5 1 4 4 1 3 3 1 2 2 rownolegle rownolegle wspolliniowe Obliczenie dokładnego punktu przecięcia czasem nie jest wymagane, gdyż wystarczy informacja o tym, że dwie proste przecinają się. Do uzyskania tej informacji wystarczy zbadanie znaków dwóch iloczynów wektorowych, a mianowicie (p2 – p0) × (p1 – p0) oraz (p3 – p0) × (p1 – p0). Przedstawiona poniżej procedura przecinanie_prostych() zwraca prawdę lub fałsz w zależności od tego, czy dwie linie proste przecinają się. # przecinanie_prostych( $x0, $y0, $x1, $y1, $x2, $y2, $x3, $y3 ) # Procedura zwraca prawde, jesli dwie linie proste zdefiniowane # przez podane punkty przecinaja sie. # W przypadkach granicznych o wyniku decyduje wartosc epsilon. sub przecinanie_prostych { my ( $x0, $y0, $x1, $y1, $x2, $y2, $x3, $y3 ) = @_; my @prostokat_a = prostopadloscian_ograniczajacy( 2, $x0, $y0, $x1, $y1 ); my @prostokat_b = prostopadloscian_ograniczajacy( 2, $x2, $y2, $x3, $y3 ); # Jesli nawet prostopadlosciany ograniczajace nie przecinaja sie, to mozna # natychmiast przerwac prace procedury. return 0 unless prostopadloscian_ograniczajacy_przeciecie( 2, @prostokat_a, @prostokat_b ); # Jesli znaki obu wyznacznikow (wartosci absolutnych lub dlugosci # iloczynow wektorowych) roznia sie, to proste przecinaja sie. my $dx10 = $x1 - $x0; my $dy10 = $y1 - $y0; my $wyzn_a = wyznacznik( $x2 - $x0, $y2 - $y0, $dx10, $dy10 ); my $wyzn_b = wyznacznik( $x3 - $x0, $y3 - $y0, $dx10, $dy10 ); return 1 if $wyzn_a 0 and $wyzn_b 0 or $wyzn_a 0 and $wyzn_b 0; if ( abs( $wyzn_a ) epsilon ) { if ( abs( $wyzn_b ) epsilon ) { # Oba iloczyny wektorowe sa zerowe. return 1; } elsif ( abs( $x3 - $x2 ) epsilon and abs( $y3 - $y2 ) epsilon ) { Przecięcie 449 # Jeden z iloczynow wektorowych ma wartosc zerowa, # a drugi wektor (od (x2,y2) do (x3,y3)) # jest rowniez zerowy. return 1; } } elsif ( abs( $wyzn_b epsilon ) ) { # Jeden z iloczynow wektorowych ma wartosc zerowa, # a drugi wektor jest rowniez zerowy. return 1 if abs( $dx10 ) epsilon and abs( $dy10 ) epsilon; } return 0; # Domyslny wynik to brak przeciecia. } Przetestujmy procedurę przecinanie_prostych() dla dwóch par linii prostych. Pierwsza para przecina się w punkcie (3, 4), natomiast druga para prostych nie krzyżuje się w ogóle, ponieważ są to linie równoległe. print Przeciecie if przecinanie_linii( 3, 0, 3, 6, 1, 1, 6, 6 ); print Brak przeciecia unless przecinanie_linii( 1, 1, 6, 6, 4, 2, 7, 5 ); Przeciecie Brak przeciecia Przecięcie prostych pionowych i poziomych Bardzo często ogólny przypadek przecięcia prostych jest zbyt ogólny; jeśli linie proste są zgodne z zasadami geometrii Manhattan (to znaczy są pionowe lub poziome), to dostępna jest zupełnie inna metoda wyszukiwania punktów przecięcia. W tym przypadku wykorzystywane są drzewa binarne, które zostały przedstawione w roz- dziale 3. poświęconym zaawansowanym strukturom danych. Pozioma prosta jest prze- suwana od dołu do góry płaszczyzny, co daje w efekcie drzewo binarne pionowych linii prostych posortowanych według ich współrzędnej x. Z tego powodu takie drzewo nosi nazwę drzewa x. Drzewo x jest tworzone w następujący sposób: • Punkty są przetwarzane od dołu do góry i od lewej do prawej. Linie pionowe są przetwarzane przed liniami poziomymi. Oznacza to, iż oba punkty końcowe poziomej prostej są widoczne jednocześnie, podczas gdy punkty końcowe prostej pionowej będą widoczne oddzielnie. • Każde pojawienie się dolnego punktu końcowego pionowej prostej powoduje dodanie tego węzła do drzewa binarnego. Wartością tego węzła jest współrzędna x. Powoduje to podzielenie punktów w drzewie w następujący sposób: jeśli prosta a znajduje się na lewo od prostej b, to węzeł a znajdzie się w drzewie na lewo od węzła b. • Każde pojawienie się górnego punktu końcowego pionowej prostej powoduje usunięcie odpowiadającego mu węzła z drzewa binarnego. • Po napotkaniu poziomej prostej węzły drzewa (aktywne proste pionowe) są sprawdzane w celu ustalenia, czy występuje przecięcie z tą prostą. Poziome linie proste nie są dodawane do drzewa, gdyż ich jedynym zadaniem jest wywołanie kontroli przecięcia. 450 Rozdział 10. Algorytmy geometryczne Rysunek 10.9 przedstawia sposób tworzenia drzewa x w czasie przesuwania wyimaginowa- nej prostej od dołu do góry płaszczyzny. Rysunek po lewej stronie przedstawia jedynie ko- lejność wykrywania poszczególnych odcinków — najpierw odcinek c, potem e itd. Środko- wy rysunek ilustruje drzewo x tuż po wykryciu odcinka e, natomiast rysunek po prawej przedstawia drzewo binarne po wykryciu odcinków a i d. Zwróć uwagę, że odcinek d nie został dodany do drzewa, ponieważ służy on tylko do wywołania kontroli przecięcia. Rysunek 10.9. Przecinanie poziomych i pionowych linii0 prostych w geometrii Manhattan Przedstawiona tutaj procedura przeciecie_manhattan() implementuje opisany wcze- śniej algorytm. # przeciecie_manhattan ( @proste ) # Procedura wyszukuje punkty przeciecia poziomych i pionowych linii prostych. # Ta procedura wymaga funkcji proste_dodawanie_do_drzewa(), # proste_usuwanie_z_drzewa() i proste_przeszukiw_drzewa(), ktore zostaly # zdefiniowane w rozdziale 3. # sub przeciecie_manhattan { my @op; # Wspolrzedne sa tutaj przeksztalcane jak operacje. while (@_) { my @prosta = splice @_, 0, 4; if ($prosta[1] == $prosta[3]) { # Pozioma prosta. push @op, [ @prosta, drzewo_sprawdzenia_przedzialu ]; } else { # Pionowa prosta. # Odwrocenie, jesli do gory nogami. @prosta = @prosta[0, 3, 2, 1] if $prosta[1] $prosta[3]; push @op, [ @prosta[0, 1, 2, 1], proste_dodawanie_do_drzewa ]; push @op, [ @prosta[0, 3, 2, 3], proste_usuwanie_z_drzewa ]; } } my $drzewo_x; # Drzewo sprawdzania przedzialu. # Procedura porownujaca wspolrzedne x. my $porownaj_x = sub { $_[0]- [0] = $_[1]- [0] }; my @przeciecie; # Przeciecia prostych. foreach my $op (sort { $a- [1] = $b- [1] || $a- [4] == drzewo_sprawdzenia_przedzialu || $a- [0] = $b- [0] } @op) { Przecięcie 451 if ($op- [4] == drzewo_sprawdzenia_przedzialu) { push @przeciecie, $op- [4]- ( $drzewo_x, $op, $porownaj_x ); } else { # Dodanie lub usuniecie. $op- [4]- ( $drzewo_x, $op, $porownaj_x ); } } return @przeciecie; } # drzewo_sprawdzenia_przedzialu( $powiazanie_drzewa, $pozioma, $porownanie ) # Ta podprocedura zwraca liste wezlow drzewa, ktore znajduja sie w przedziale # od $pozioma- [0] do $pozioma- [1]. Procedura jest zalezna od drzew # binarnych, ktore zostaly przedstawione w rozdziale 3. # sub drzewo_sprawdzenia_przedzialu { my ( $drzewo, $pozioma, $porownanie ) = @_; my @przedzial = ( ); # Wartosc zwrotna. my $wezel = $$drzewo; my $pionowa_x = $wezel- {val}; my $pozioma_dolny = [ $pozioma- [ 0 ] ]; my $pozioma_gorny = [ $pozioma- [ 1 ] ]; return unless defined $$drzewo; push @przedzial, drzewo_sprawdzenia_przedzialu( $wezel- {left}, $pozioma, $porownanie ) if defined $wezel- {left}; push @przedzial, $pionowa_x- [ 0 ], $pozioma- [ 1 ] if $porownanie- ( $pozioma_dolny, $pozioma ) = 0 $porownanie- ( $pozioma_gorny, $pozioma ) = 0; push @przedzial, drzewo_sprawdzenia_przedzialu( $wezel- {right}, $pozioma, $porownanie ) if defined $wezel- {right}; return @przedzial; } Procedura przeciecie_manhattan() działa w czasie nie dłuższym niż O (N logN + k), gdzie k to liczba przecięć, która nie może być większa niż (N/2)2. Sposób użycia procedury przeciecie_manhattan() zostanie przedstawiony na przy- kładzie odcinków z rysunku 10.10. Poszczególne odcinki zostają zapisane w tablicy. Wyszukiwanie przecięć odbywa się w następujący sposób: @proste = ( 1, 6, 1, 3, 1, 2, 3, 2, 1, 1, 4, 1, 2, 4, 7, 4, 3, 0, 3, 6, 4, 3, 4, 7, 5, 7, 5, 4, 5, 2, 7, 2 ); print join( , przeciecie_manhattan (@proste)), ; Uzyskane wyniki to: 3 1 3 2 1 4 3 4 4 4 5 4 452 Rozdział 10. Algorytmy geometryczne Rysunek 10.10. Odcinki dla przykładu zastosowania a0lgorytmu Manhattan Na podstawie uzyskanych wyników można stwierdzić, że istnieje sześć punktów prze- cięcia; na przykład punkt (3, 1) stanowi najniższy punkt przecięcia, natomiast (5, 4) to najwyższy taki punkt. Zawieranie punktów i wielokątów W tej części rozdziału przedstawimy metody umożliwiające ustalenie, czy punkt znajduje się wewnątrz wielokąta. Pozwala to na przeprowadzenie bardziej skomplikowanych ope- racji, takich jak sprawdzenie, czy wewnątrz wielokąta znalazł się cały odcinek czy tylko jego część. Punkt wewnątrz wielokąta Sprawdzenie, czy punkt znajduje się wewnątrz figury geometrycznej, wymaga wyprowa- dzenia prostej od tego punktu do „nieskończoności” (czyli do dowolnego punktu, który na pewno znajduje się poza obszarem wielokąta). Algorytm jest bardzo prosty — wystar- czy ustalić, ile razy prosta przecina krawędzie wielokąta. Jeśli ta liczba będzie nieparzysta (punkty e, f, h i j na rysunku 10.11), to punkt znajduje się wewnątrz figury. W przeciwnym razie punkt jest umieszczony na zewnątrz (punkty a, b, c, d, g i i na tym samym rysunku). Istnieją jednak pewne specjalne przypadki (bardzo rzadko zdarza się algorytm geome- tryczny, który nie powoduje problemów) wymagające specjalnego potraktowania. Co się stanie, jeśli wyprowadzona prosta przetnie wierzchołek wielokąta (punkty d, f, g i j)? W jeszcze gorszym przypadku prosta może przebiegać wzdłuż krawędzi figury geome- trycznej (punkt j). Przedstawiony tu algorytm gwarantuje zwrócenie prawdy dla punktów naprawdę znajdujących się wewnątrz wielokąta lub fałszu dla pozostałych przypadków. Przypadki graniczne są traktowane zgodnie z wybranym sposobem liczenia. Zawieranie punktów i wielokątów 453 Rysunek 10.11. Czy punkt znajduje się wewnątrz wieloką0ta? Wystarczy policzyć przecięcia krawędzi Procedura punkt_wewnatrz_wielokata() zwraca prawdę, jeśli dany punkt (pierwsze dwa argumenty) znajduje się wewnątrz wielokąta opisanego przez kolejne argumenty: # punkt_wewnatrz_wielokata ( $x, $y, @xy ) # # Parametry to punkt ($x,$y) oraz wielokat ($x0, $y0, $x1, $y1, ...) w @xy. # Procedura zwraca 1 dla punktow znajdujacych sie wewnatrz wielokata # i 0 dla punktow poza wielokatem. W przypadku punktow granicznych sytuacja # jest bardziej skomplikowana, a jej omowienie wykraczaloby poza tematyke # tej ksiazki. Punkty graniczne sa jednak ustalane jednoznacznie; # jesli plaszczyzna zostanie podzielona na wiele wielokatow, to kazdy punkt # znajdzie sie dokladnie w jednym wielokacie. # # Procedura wywodzi sie z dokumentu FAQ dla grupy dyskusyjnej # comp.graphics.algorithms i zostala udostepniona przez Wm. Randolpha # Franklina. # sub punkt_wewnatrz_wielokata { my ( $x, $y, @xy ) = @_; my $n = @xy / 2; # Liczba punktow wielokata. my @i = map { 2 * $_ } 0 .. (@xy/2); # Parzyste indeksy @xy. my @x = map { $xy[ $_ ] } @i; # Parzyste indeksy: wspolrzedne x. my @y = map { $xy[ $_ + 1 ] } @i; # Nieparzyste indeksy: wspolrzedne y. my ( $i, $j ); # Indeksy. my $polozenie = 0; # 0 = na zewnatrz, 1 = wewnatrz. for ( $i = 0, $j = $n - 1 ; $i $n; $j = $i++ ) { if ( ( # Jesli y znajduje sie w granicach (y-)... ( ( $y[ $i ] = $y ) ( $y $y[ $j ] ) ) || ( ( $y[ $j ] = $y ) ( $y $y[ $i ] ) ) ) and # ... i prosta poprowadzona od punktu (x,y) do nieskonczonosci # przecina krawedz pomiedzy i-tym i j-tym punktem... ($x ( $x[ $j ] - $x[ $i ] ) * 454 Rozdział 10. Algorytmy geometryczne ( $y - $y[ $i ] ) / ( $y[ $j ] - $y[ $i ] ) + $x[ $i ] )) { $polozenie = not $polozenie; # Zmiana polozenia. } } return $polozenie ? 1 : 0; } Sprawdzenie parzystości lub nieparzystości liczby przecięć nie wymaga nawet zliczania tych przecięć, gdyż istnieje znacznie szybsza metoda polegająca na przełączaniu wartości zmiennej logicznej $polozenie. Wykorzystując wielokąt z rysunku 10.12, możemy sprawdzić, które z dziewięciu punktów znajdują się wewnątrz tej figury: @wielokat = ( 1, 1, 3, 5, 6, 2, 9, 6, 10, 0, 4,2, 5, -2); print ( 3, 4): , punkt_wewnatrz_wielokata( 3, 4, @wielokat ), ; print ( 3, 1): , punkt_wewnatrz_wielokata( 3, 1, @wielokat ), ; print ( 3,-2): , punkt_wewnatrz_wielokata( 3,-2, @wielokat ), ; print ( 5, 4): , punkt_wewnatrz_wielokata( 5, 4, @wielokat ), ; print ( 5, 1): , punkt_wewnatrz_wielokata( 5, 1, @wielokat ), ; print ( 5,-2): , punkt_wewnatrz_wielokata( 5,-2, @wielokat ), ; print ( 7, 4): , punkt_wewnatrz_wielokata( 7, 4, @wielokat ), ; print ( 7, 1): , punkt_wewnatrz_wielokata( 7, 1, @wielokat ), ; print ( 7,-2): , punkt_wewnatrz_wielokata( 7,-2, @wielokat ), ; Rysunek 10.12. Przykładowy wielokąt z punktami wewnętr0znymi i zewnętrznymi Oto uzyskane wyniki: (3, 4): 1 (3, 1): 1 (3,-2): 0 (5, 4): 0 (5, 1): 0 (5,-2): 0 (7, 4): 0 (7, 1): 1 (7,-2): 0 Zawieranie punktów i wielokątów 455 Udało się nam stwierdzić, że punkty (3, 4), (3, 1) i (7, 1) są położone wewnątrz wielokąta, natomiast pozostałe punkty leżą na zewnątrz. Punkt wewnątrz trójkąta W przypadku prostszych wielokątów, takich jak trójkąty, możliwe jest zastosowanie alter- natywnego algorytmu. Po wybraniu jednego z wierzchołków trójkąta odbywa się spraw- dzanie, czy punkt jest widoczny po lewej czy po prawej stronie. Teraz należy przejść do drugiego wierzchołka i powtórzyć procedurę. Jeśli punkt widoczny jest po innej stronie niż poprzednio, to nie może znajdować się wewnątrz trójkąta. Operacja jest powtarzana także dla trzeciego wierzchołka. Jeśli punkt będzie widoczny zawsze po tej samej stronie (lub leży na krawędzi trójkąta), to można bezpiecznie przyjąć, że znajduje się wewnątrz trójkąta. Rysunek 10.13 stanowi ilustrację powyższego algorytmu. Kolejne wierzchołki trójkąta są badane w kolejności przeciwnej do kierunku ruchu wskazówek zegara. Punkty znajdujące się wewnątrz trójkąta powinny być widoczne po lewej stronie. Jeśli punkt znajduje się na zewnątrz, to będzie możliwe zaobserwowanie zmiany kierunku. Rysunek 10.13. Sprawdzanie, czy punkt znajduje się wewnątrz trójkąta Przedstawiona powyżej metoda została zaimplementowana w podprocedurze punkt_ wewnatrz_trojkata(): # punkt_wewnatrz_trojkata( $x, $y, $x0, $y0, $x1, $y1, $x2, $y2 ) # Procedura zwraca prawde, jesli punkt ($x,$y) znajduje sie wewnatrz # trojkata zdefiniowanego przez punkty ($x0, $y0, $x1, $y1, $x2, $y2). # sub punkt_wewnatrz_trojkata { my ( $x, $y, $x0, $y0, $x1, $y1, $x2, $y2 ) = @_; # Procedura kierunek() pochodzi z wczesniejszej czesci rozdzialu. my $cw0 = kierunek( $x0, $y0, $x1, $y1, $x, $y ); return 1 if abs( $cw0 ) epsilon; # Pierwsza krawedz. my $cw1 = kierunek( $x1, $y1, $x2, $y2, $x, $y ); return 1 if abs( $cw1 ) epsilon; # Druga krawedz. # Niepowodzenie w przypadku zmiany znaku. return 0 if ( $cw0 0 and $cw1 0 ) or ( $cw0 0 and $cw1 0 ); 456 Rozdział 10. Algorytmy geometryczne my $cw2 = kierunek( $x2, $y2, $x0, $y0, $x, $y ); return 1 if abs( $cw2 ) epsilon; # Trzecia krawedz. # Niepowodzenie w przypadku zmiany znaku. return 0 if ( $cw0 0 and $cw2 0 ) or ( $cw0 0 and $cw2 0 ); # Sukces! return 1; } Zdefiniujmy teraz trójkąt o wierzchołkach (1, 1), (5, 6) i (9, 3), a następnie sprawdźmy, czy siedem przykładowych punktów znajduje się wewnątrz tego trójkąta: @trojkat = ( 1, 1, 5, 6, 9, 3 ); print (1, 1): , punkt_wewnatrz_trojkata( 1, 1, @trojkat ), ; print (1, 2): , punkt_wewnatrz_trojkata( 1, 2, @trojkat ), ; print (3, 2): , punkt_wewnatrz_trojkata( 3, 2, @trojkat ), ; print (3, 3): , punkt_wewnatrz_trojkata( 3, 3, @trojkat ), ; print (3, 4): , punkt_wewnatrz_trojkata( 3, 4, @trojkat ), ; print (5, 1): , punkt_wewnatrz_trojkata( 5, 1, @trojkat ), ; print (5, 2): , punkt_wewnatrz_trojkata( 5, 2, @trojkat ), ; Oto uzyskane wyniki: (1, 1): 1 (1, 2): 0 (3, 2): 1 (3, 3): 1 (3, 4): 0 (5, 1): 0 (5, 2): 1 Punkty (1, 2), (3, 4) i (5, 1) znajdują się na zewnątrz trójkąta, natomiast pozostałe punkty są umieszczone wewnątrz niego. Punkt wewnątrz czworokąta Każdy czworokąt wypukły (wszystkie kwadraty i prostokąty są czworokątami) może być podzielony na dwa trójkąty poprzez połączenie dwóch przeciwległych wierzchołków. Wykorzystując tę cechę i podprocedurę punkt_wewnatrz_trojkata(), możemy spraw- dzić, czy dany punkt znajduje się wewnątrz czworokąta. Należy uważać jedynie na spe- cjalny rodzaj czworokątów z nakładającymi się wierzchołkami, które mogą ulec redukcji do trójkątów, odcinków, a nawet punktów. Podział czworokąta na dwa trójkąty przed- stawiono na rysunku 10.14. Rysunek 10.14. Podział czworokąta na dwa trójkąty Zawieranie punktów i wielokątów 457 Poniższa podprocedura punkt_wewnatrz_czworokata() dwukrotnie wywołuje pro- cedurę punkt_wewnatrz_trojkata() dla każdego trójkąta, który powstał po podziale: # punkt_wewnatrz_czworokata( $x, $y, $x0, $y0, $x1, $y1, $x2, $y2, $x3, $y3 ) # Procedura zwraca prawde, jesli punkt ($x,$y) znajduje sie wewnatrz # czworokata # zdefiniowanego przez punkty p0 ($x0,$y0), p1, p2 oraz p3. # Wykorzystywana jest podprocedura punkt_wewnatrz_trojkata(). # sub punkt_wewnatrz_czworokata { my ( $x, $y, $x0, $y0, $x1, $y1, $x2, $y2, $x3, $y3 ) = @_; return punkt_wewnatrz_trojkata( $x, $y, $x0, $y0, $x1, $y1, $x2, $y2 ) || punkt_wewnatrz_trojkata( $x, $y, $x0, $y0, $x2, $y2, $x3, $y3 ) } Działanie procedury punkt_wewnatrz_czworokata() zostanie zademonstrowane na przykładzie czworokąta i punktów pokazanych na rysunku 10.15. Rysunek 10.15. Ustalenie punktów znajdujących się wewn0ątrz czworokąta Wierzchołki czworokąta to (1, 4), (3, 0), (6, 2) i (5, 5), a więc procedurę punkt_wewnatrz_ czworokata() należy wywołać w następujący sposób: @czworokat = ( 1, 4, 3, 0, 6, 2, 5, 5 ); print (0, 2): , punkt_wewnatrz_czworokata( 0, 2, @czworokat ), ; print (1, 4): , punkt_wewnatrz_czworokata( 1, 4, @czworokat ), ; print (2, 2): , punkt_wewnatrz_czworokata( 2, 2, @czworokat ), ; print (3, 6): , punkt_wewnatrz_czworokata( 3, 6, @czworokat ), ; print (3, 4): , punkt_wewnatrz_czworokata( 3, 4, @czworokat ), ; print (4, 2): , punkt_wewnatrz_czworokata( 4, 2, @czworokat ), ; print (5, 4): , punkt_wewnatrz_czworokata( 5, 4, @czworokat ), ; print (6, 2): , punkt_wewnatrz_czworokata( 6, 2, @czworokat ), ; Uzyskane wyniki to: (0, 2): 0 (1, 4): 1 (2, 2): 1 (3, 6): 0 (3, 4): 1 458 Rozdział 10. Algorytmy geometryczne (4, 2): 1 (5, 4): 1 (6, 2): 1 Jedyne punkty znajdujące się na zewnątrz czworokąta to (0, 2) i (3, 6). Granice W tej części rozdziału zajmiemy się badaniem granic figur geometrycznych, co może być przydatne do sprawdzenia, czy figury nakładają się. Należy być jednak bardzo uważnym, gdyż uzyskane granice są tylko pierwszym przybliżeniem, a obiekty wklęsłe mogą spra- wiać problemy. Prostopadłościany ograniczające Prostopadłościan ograniczający to obiekt geometryczny definiowany jako najmniejszy pro- stopadłościan d-wymiarowy zawierający obiekt d-wymiarowy, którego krawędzie są rów- noległe do osi. Prostopadłościany ograniczające są często wykorzystywane w grach kom- puterowych do wykrywania kolizji obiektów. Przykład takiego prostopadłościanu znajduje się na rysunku 10.16. Rysunek 10.16. Wielokąt i jego prostopadłościan ograni0czający (zaznaczony kropkowaną linią) Poniższa podprocedura prostopadloscian_ograniczajacy() zwraca tablicę punk- tów. Jeśli zmienna $d ma wartość 2 (dwa wymiary), to prostopadłościan ograniczający będzie miał postać prostokąta. W tym przypadku procedura zwróci cztery elementy będące dwoma wierzchołkami prostokąta. # prostopadloscian_ograniczajacy_punkty($d, @p) # Procedura zwraca prostopadloscian ograniczajacy dla zbioru $d-wymiarowych # punktow @p. sub prostopadloscian_ograniczajacy_punkty { my ($d, @punkty) = @_; my @bb; while (my @p = splice @punkty, 0, $d) { @bb = prostopadloscian_ograniczajacy($d, @p, @bb); # Zdefiniowane # ponizej. } Granice return @bb; } 459 # prostopadloscian_ograniczajacy($d, @p [,@b]) # Procedura zwraca prostopadloscian ograniczajacy dla punktow @p w $d # wymiarach. # @b to opcjonalny, wstepny pr
Pobierz darmowy fragment (pdf)

Gdzie kupić całą publikację:

Algorytmy w Perlu
Autor: , ,
Sklep
Format
Cena
Helion.pl Helion.pl
książka
69,00 zł
Idź do sklepu »

Opinie na temat publikacji:

Inne popularne pozycje z tej kategorii:

Czytaj również:

Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: