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)