Waldemar Izdebski - Wykłady z przedmiotu SIT / Mapa zasadnicza 37
Rys. 2.28. Zapis rastra w strukturze drzewa czwórkowego
W prezentowanej strukturze z każdego węzła wychodzą cztery rozgałęzienia,
odpowiadające podziałowi danego elementu powierzchniowego na cztery części. Podział
rozpoczyna się od obszaru całego rastra i jest kontynuowany przez kolejne coraz mniejsze
elementy. Jak widać dla pewnych (jednolitych) obszarów rastra podział może być
zakończony już na pierwszym podziale płaszczyzny bez utraty jakiejkolwiek informacji. Nie
występuje więc potrzeba wyodrębniania dla tego obszaru kolejnych mniejszych elementów.
2.3.2. Kalibracja rastrów
Wykorzystanie rastrów w systemach informacji przestrzennej musi być poprzedzone ich
odpowiednim przygotowaniem, polegającym na określeniu związku między układem rastra
(zapisanym w tablicy pikseli) a układem terenowym. Jeżeli określony związek będzie
wymagał innych przekształceń niż przesunięcie i zmiana skali, trudno wyobrazić sobie pracę
na rastrach, złożonych z wielu milionów pikseli, które co chwila trzeba będzie poddawać
skomplikowanym przekształceniom. Konieczność takich przekształceń może wynikać ze
skręcenia oryginału podczas skanowania, błędów powstałych w trakcie skanowania czy też
błędów oryginału, wynikających z właściwości materiału na jakim został wykonany.
Kalibracja jest procesem, który eliminuje opisane zniekształcenia przez utworzenie nowego
Waldemar Izdebski - Wykłady z przedmiotu SIT / Mapa zasadnicza 38
rastra, odpowiednio zlokalizowanego w układzie współrzędnych, powstałego w wyniku
przetransformowania pikseli rastra oryginalnego na piksele rastra nowego wolnego od
zniekształceń. Schematycznie proces ten przedstawiono na rysunku 2.29.
Rys. 2.29. Ilustracja procesu kalibracji
Skuteczność eliminacji błędów zależy w znacznej mierze od zastosowanego modelu
transformacji oraz od tego czy model zastosujemy bezpośrednio dla całego rastra czy
będziemy go stosowali do fragmentów rastra, które po transformacji zostaną ze sobą
połączone. Do wyznaczenia parametrów transformacji wykorzystujemy punkty łączne czyli
takie, które posiadające określone współrzędne terenowe oraz są identyfikowalne na rastrze.
Rys. 2.30. Ilustracja procesu kalibracji
Waldemar Izdebski - Wykłady z przedmiotu SIT / Mapa zasadnicza 39
W przypadku map jest to głównie siatka kwadratów ale mogą być wykorzystywane
również inne punkty (np. punkty osnowy, graniczniki). Minimalna liczba punktów łącznych
zależy od przyjętego modelu transformacji. Zazwyczaj parametry transformacji wyznacza się
metodą najmniejszych kwadratów na podstawie większej liczby punktów niż minimalna
wynikająca z modelu, co pozwala na oszacowanie dokładność uzyskanej transformacji.
Poniżej przedstawiono kilka najczęściej stosowanych do kalibracji rastrów modeli
transformacji.
Transformacja Helmerta
Najprostszy model transformacji wymagajÄ…cy do jednoznacznego wyznaczenia
parametrów jedynie dwóch punktów. Model pozwala na obrót, przesunięcie i zmianę skali.
X cosÕ sinÕ x Xo
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
= k *ïÅ‚ *ïÅ‚ śł +
ïÅ‚Y śł ïÅ‚Yośł
ðÅ‚ ûÅ‚ ðÅ‚- sinÕ cosÕśł ðÅ‚yûÅ‚ ðÅ‚ ûÅ‚
ûÅ‚
Transformacja afiniczna
Model w którym współrzędna w nowym układzie wynika z zależności przedstawionej
poniżej. Minimalna liczba potrzebnych punktów wynosi 3. Transformacja zachowuje
równoległość linii i środki odcinków zmienia natomiast długości odcinków i wartości kątów.
x
îÅ‚ Å‚Å‚
X a2 a1 a0 ïÅ‚yśł
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
= *
ïÅ‚Y śł ïÅ‚b b1 b0 śł
ïÅ‚ śł
ðÅ‚ ûÅ‚ ðÅ‚ 2 ûÅ‚
ïÅ‚
ðÅ‚1śł
ûÅ‚
Transformacja biliniowa
Model w którym współrzędna w nowym układzie wynika z zależności przedstawionej
poniżej. Minimalna liczba potrzebnych punktów wynosi 4. Transformacja ma szczególne
znaczenie ze względu na przekształcanie czworokąta w czworokąt co znakomicie nadaje się
do transformacji fragmentami.
xy
îÅ‚ Å‚Å‚
śł
X a3 a2 a1 a0 ïÅ‚ x
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
ïÅ‚ śł
= *
ïÅ‚Y śł ïÅ‚b b2 b1 b0 śł
ïÅ‚ śł
y
ðÅ‚ ûÅ‚ ðÅ‚ 3 ûÅ‚
ïÅ‚ śł
1
ðÅ‚ ûÅ‚
Waldemar Izdebski - Wykłady z przedmiotu SIT / Mapa zasadnicza 40
Transformacja rzutowa
Transformacja określająca zależność rzutową pomiędzy punktami układu pierwotnego
i wtórnego. Do określenia wartości współczynników transformacji potrzebne są cztery punkty
rozmieszczone tak aby żadne 3 nie leżały na jednej prostej.
a1x + a2 y + a3
X =
a7 x + a8 y +1
a4x + a5 y + a6
Y =
a7x + a8 y +1
Transformacje wielomianowe
W transformacji afinicznej do określenia zależności między układami zastosowany jest
wielomian dwóch zmiennych P(x,y) stopnia pierwszego. Zwiększając stopień wielomianu
będziemy potrzebowali więcej punktów do wyznaczenia parametrów wielomianu ale
jednocześnie transformacja może wyeliminować znaczne większe zniekształcenia.
Najczęściej wykorzystywane są transformacje do 3-go stopnia wielomianu nazywane
odpowiednio transformacjÄ…:
bikwadratowÄ…,
îÅ‚ Å‚Å‚
x2
ïÅ‚ śł
ïÅ‚xyśł
X a5 a4 a3 a2 a1 a0 ïÅ‚y2 śł
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
= *
ïÅ‚ śł
ïÅ‚Y śł ïÅ‚b b4 b3 b2 b1 b0 śł
x
ðÅ‚ ûÅ‚ ðÅ‚ 5 ûÅ‚
ïÅ‚ śł
ïÅ‚ śł
y
ïÅ‚ śł
1
ïÅ‚ śł
ðÅ‚ ûÅ‚
bikubicznÄ….
îÅ‚ Å‚Å‚
x3
ïÅ‚ śł
2
ïÅ‚x yśł
ïÅ‚xy2 śł
ïÅ‚ śł
y3
ïÅ‚ śł
X a9 a8 a7 a6 a5 a4 a3 a2 a1 a0 ïÅ‚ śł
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ x2
= * ïÅ‚ śł
ïÅ‚Y śł ïÅ‚b b8 b7 b6 b5 b4 b3 b2 b1 b0 śł
y2
ïÅ‚ śł
ðÅ‚ ûÅ‚ ðÅ‚ 9 ûÅ‚
ïÅ‚ śł
xy
ïÅ‚ śł
ïÅ‚ x śł
ïÅ‚ śł
y
ïÅ‚ śł
ïÅ‚ śł
1
ðÅ‚ ûÅ‚
Waldemar Izdebski - Wykłady z przedmiotu SIT / Mapa zasadnicza 41
Należy zwrócić uwagę na fakt, że każde przekształcenie rastra powoduje jego stopniową
degradację. Możemy to sprawdzić doświadczalnie wykonując kilka obrotów rastra o małe
kąty i powrót do pozycji wyjściowej. Poniżej przedstawiono raster z rysunku 2.30 po trzech
obrotach o wartość 3 stopni i powrót do pozycji wyjściowej.
Rys. 2.31. Raster po kilku przekształceniach
5. Organizacja dostępu do danych przestrzennych
Duża liczba danych przestrzennych oraz ich specyficzny charakter sprawiają, że do
sprawnego funkcjonowania systemu, przetwarzania zgromadzonych w nim danych, nie
wystarczÄ… jedynie wyrafinowane algorytmy przetwarzania danych, ale potrzebna jest
odpowiednia organizacja danych zapewniająca możliwie szybki do nich dostęp. Szczególnie
istotne jest to w aspekcie wyszukiwania danych spełniających określone warunki
przestrzenne. Efekty wyszukiwania jest na ogół pierwszym krokiem do wykonywania
jakichkolwiek innych operacji na danych, jak wykonywanie zestawień w postaci
tabelarycznej czy graficznej prezentacji na ekranie monitora, drukarce lub innym urzÄ…dzeniu
wyjścia. Ze względu na interaktywny charakter, szczególne znaczenie ma w tym miejscu
prezentacja danych na ekranie, która musi być realizowana w określonych reżimach
czasowych, aby nie dekoncentrować operatora. Podstawowe zadania związane z
wyszukiwaniem danych na podstawie warunków przestrzennych możemy sformułować
następująco:
" znalezienie wszystkich obiektów zawierających się w określonym wielokącie,
wykorzystywane głównie przy udostępnieniu fragmentów baz danych,
" znalezienie wszystkich obiektów zawierających się w określonym prostokącie,
wykorzystywane głównie przy graficznej prezentacji,
" znalezienie obiektów najbliższych wskazanemu punktowi, wykorzystywane przy
wyborze obiektu w trybie interaktywnym (kursorem).
Ilustrację graficzną przedstawionych powyżej zadań wyszukiwania danych przedstawiono na
rysunku 5.1.
Waldemar Izdebski - Wykłady z przedmiotu SIT / Mapa zasadnicza 53
Rys. 5.1. Ilustracja zadań wyszukiwania danych przestrzennych
Mając na uwadze wymienione wyżej względy wykonuje się wiele zabiegów
zmierzających do poprawienia efektywności dostępu do danych. Kilka z nich przedstawimy w
kolejnych podrozdziałach.
6. ProstokÄ…ty ograniczajÄ…ce
Jedną z najprostszych metod organizacji danych sprzyjającą szybszemu dostępowi jest
wprowadzenie w stosowanych do reprezentacji obiektów strukturach danych pewnych
dodatkowych informacji. Zadaniem ich jest uproszczone, w sensie przestrzennym,
zobrazowanie obiektów, które możemy nazwać aproksymacją obiektów właściwych. Istotą
takiej aproksymacji będzie zachowywanie przybliżonej informacji o obiekcie, zapisanej w
maksymalnie uproszczony sposób wygodny do wykonywania analiz. Najpowszechniejszym
ze spotykanych uproszczeń jest aproksymacja obiektu minimalnym prostokątem o bokach
równoległych do osi układu współrzędnych, w którym można zmieścić cały rozpatrywany
obiekt. Prostokąt taki będziemy nazywali minimalnym prostokątem ograniczającym. W
literaturze polskiej można się spotkać z określaniem takiego prostokąta  pudełkiem
[Adamczewski, Nowak 1977] oraz [Nowak, Åšliwka 1979].
Waldemar Izdebski - Wykłady z przedmiotu SIT / Mapa zasadnicza 54
maxX
maxY
minX
minY
Rys. 5.2. Ilustracja prostokÄ…ta ograniczajÄ…cego
Innymi uproszczeniami (aproksymacjami) jakie można stosować do obiektów
przestrzennych może być punkt lub okrąg. Oczywiście rozpatrujemy tutaj zagadnienie na
płaszczyz
nie w przypadku większego wymiaru przestrzeni wspomniane twory będą również
odpowiednio wyższego wymiaru.
Wprowadzanie, przechowywanie i modyfikacja danych zwiÄ…zanych z aproksymacjÄ…
właściwego obiektu jest wewnętrzna sprawą oprogramowania i właściwie użytkownik rzadko
wie o istnieniu takich dodatkowych danych.
W celu zilustrowania korzyści płynących z zastosowania prostokątów ograniczających
przeanalizujmy zadanie przedstawione na rysunku 5.3. ZnajdujÄ… siÄ™ tam obiekty w formie
wielokątów oraz prostokąt stanowiący obszar zainteresowania (okno zapytań) wyróżniony
pogrubioną linią. Interesuje nas, które obiekty mają część wspólną z oknem zapytań.
Zakładając, że w zastosowanej strukturze danych mamy jedynie wierzchołki poszczególnych
wielokątów musimy w celu podania odpowiedzi, dla każdego z nich stosować algorytmy
sprawdzające istnienie części wspólnej wielokąta z prostokątem. W wielu przypadkach
wielokąty mogą zawierać nawet wiele tysięcy punktów, co ma ogromne znaczenie dla czasu
działania tych algorytmów. Oczywiście można wtedy algorytm taki rozpoczynać od
wyznaczenia prostokąta ograniczającego ale, jak wynika to z zastosowań praktycznych,
wygodniej jednak przechowywać taki prostokąt ograniczający niż każdorazowo go
wyznaczać. Jeśli jednak prostokąt ograniczający jest przechowywany musimy pamiętać aby
dokonywać jego modyfikacji wraz z modyfikacjami obiektu właściwego. W przeciwnym
wypadku wykorzystywanie prostokątów ograniczających może doprowadzić do mylnych
wniosków.
Waldemar Izdebski - Wykłady z przedmiotu SIT / Mapa zasadnicza 55
12
3
5
4
67
Rys. 5.3. Wybór obiektów zawierających się w prostokątnym oknie
Zadanie powyższe przybiera znacznie uproszczoną postać jeśli dla każdego obiektu znany
jest jego prostokÄ…tnÄ… aproksymacjÄ™, jak przedstawiono to na rysunku 5.4.
12
3
5
4
67
Rys. 5.4. Aproksymacja obiektów prostokątami ograniczającymi
Waldemar Izdebski - Wykłady z przedmiotu SIT / Mapa zasadnicza 56
Korzystając jedynie z prostokątów ograniczających, badając relacje prostokąt ograniczający
obiektu - okno zapytań możemy ze szczegółowego sprawdzania wyeliminować wiele
obiektów co pozwala na duże oszczędności czasowe. Warunkiem koniecznym posiadania
przez wielokąty części wspólnej jest jej posiadanie przez odpowiadające im prostokąty
ograniczające. W tym miejscu należy zwrócić uwagę na fakt, że warunek ten jest warunkiem
koniecznym ale nie wystarczającym i może się zdarzyć, że mimo posiadania części wspólnej
okna zapytań z prostokątem ograniczającym, obiekt w rzeczywistości obiekt nie zawiera się
w oknie zapytań. Zadanie wykonywane jest więc w dwóch etapach. W etapie pierwszym dla
wszystkich obiektów analizujemy prostokąty ograniczające wybierając kandydatów do
drugiego etapu sprawdzania szczegółowego. Ilustracja pierwszego etapu przedstawiono na
rysunku 5.5.
12
3
5
4
67
Rys. 5.5. Wybór obiektów na podstawie prostokątów ograniczających
W trakcie sprawdzania prostokątów wystarczy zaistnienie tylko jednego z przedstawionych
poniżej warunków aby można było pominąć dany obiekt, uznając, że nie posiada części
wspólnej z oknem zapytań:
Waldemar Izdebski - Wykłady z przedmiotu SIT / Mapa zasadnicza 57
Tabela 5.1 Warunki sprawdzania położenia prostokątów ograniczających
Postać warunku Działania warunku Ilustracja graficzna
odrzucanie wszystkich obiektów o
o
prostokątach ograniczających leżących
Xmin > Xmax
okno zapytań
nad oknem prezentacji
odrzucanie wszystkich obiektów o
o
prostokątach ograniczających leżących
Ymin > Ymax okno zapytań
po prawej stronie okna prezentacji
odrzucanie wszystkich obiektów o
okno zapytań
o
prostokątach ograniczających leżących
Xmax < Xmin
poniżej okna prezentacji
odrzucanie wszystkich obiektów o
o
prostokątach ograniczających leżących
Ymax < Ymin okno zapytań
po lewej stronie okna prezentacji
W wyniku sprawdzenia warunków dla prostokątów ograniczających do sprawdzenia w
sposób szczegółowy pozostają nam jedynie obiekty przedstawione poniżej.
5
4
67
Rys. 5.6. Wybór obiektów na podstawie prostokątów ograniczających
W przypadku obiektu oznaczonego cyfrÄ… 6 widzimy zaistnienie sytuacji opisywanej
wcześniej. Prostokąt ograniczający tego obiektu posiada część wspólną z oknem zapytań,
natomiast w rzeczywistości obiekt takiej części nie posiada. Stwierdzenie jednak tego faktu
może nastąpić dopiero na drodze szczegółowej analizy wierzchołków wielokąta.
Waldemar Izdebski - Wykłady z przedmiotu SIT / Mapa zasadnicza 58
7. Indeksowanie przestrzenne
Wprowadzenie aproksymacji obiektów przez prostokąty ograniczające jest
niewątpliwą koniecznością z punktu widzenia efektywnego dostępu do obiektów
przechowywanych w systemie. Należy sobie jednak zdawać sprawę, że prostokąty
ograniczające rozwiązują jedynie częściowo problem dostępu do danych. Kolejnym bardzo
ważnym czynnikiem w optymalizacji dostępu do danych SIP jest zastosowanie odpowiednich
systemów indeksowania przestrzennego, aby przy wyborze nie przebiegać zawsze przez całą
listę obiektów lecz operować na pewnych uporządkowanych przestrzennie grupach obiektów,
które mogą posiadać również własne (grupowe) prostokąty ograniczające. Tak więc jeśli
stwierdzimy, że prostokąt ograniczający danej grupy daje się odrzucić wtedy ją całą
pomijamy. Poniżej przedstawiono charakterystykę dwóch najczęściej stosowanych metod
indeksowania przestrzennego quadtree i R-tree. Stosowanie tych metod nie oznacza
rezygnacji z prostokątów ograniczających, które stanowią także podstawę do zastosowania
metod indeksowania.
8. Quadtree
Quadtree jest strukturą znacznie przyspieszającą dostęp do danych przestrzennych. W
celu przedstawienia idei niniejszej struktury, rozważmy obiekty przedstawione na rysunku
5.7.
3
9
2
8
4
10
5
1
11
12
6
7
Rys. 5.7. Lokalizacja obiektów
Waldemar Izdebski - Wykłady z przedmiotu SIT / Mapa zasadnicza 59
Obszar w którym zlokalizowane są obiekty będziemy dzielili w sposób schematycznie
przedstawiony na rysunku 5.8, do osiągnięcia założonego, maksymalnego stopnia podziału.
Pierwszy podział całości obszaru na cztery daje podobszary oznaczone jako: 0, 1, 2, 3 a
następnie każdy z podobszarów w analogiczny sposób dzielony jest na kolejne podobszary
otrzymujÄ…ce w oznaczeniu dodatkowÄ… cyfrÄ™. W przypadku podobszaru 2 oznaczenia te sÄ…
następujące: 20, 21, 22, 23.
232
233
22
23
231
230
2
3
20
21
1
0
Rys. 5.8. Schemat podziału obszaru w strukturze quadtree
W wyniku nałożenia siatki podziału na obiekty, co ilustruje rysunek 5.9, możemy każdemu
obiektowi przypisać indeksy wynikające z oznaczenia obszaru w jakim obiekt jest całkowicie
zawarty.
3
9
2
8
4
10
5
1
11
12
6
7
Rys. 5.9. Schemat tworzenia indeksów
Waldemar Izdebski - Wykłady z przedmiotu SIT / Mapa zasadnicza 60
Dla przedstawionych na rysunku 5.7 obiektów otrzymujemy więc następujące indeksy:
Nr INDEX Nr INDEX
obiektu obiektu
quadtree quadtree
1 PUSTY 7 1
2 22 8 231
3 23 9 33
4 3 10 31
5 2 11 13
6 0 12 12
których interpretacja pozwala wnioskować o przestrzennej lokalizacji poszczególnych
obiektów. Dokładnie wynika to z interpretacji poszczególnych cyfr indeksu. Stosując
omówioną zasadę możemy indeks przypisać każdemu obiektowi, utworzyć indeks liniowy
lub na bazie indeksu tworzyć strukturę drzewa dla przechowywania danych jak zilustrowano
to na rysunku 5.10.
1,...,
1 3
0 2
6... 7... 5.... 4...
12... 11... 2... 3... 10... 9..
8...
Rys. 5.10. Schemat drzewa quadtree
W celu znalezienia obiektów znajdujących się w pewnym obszarze należy określić indeks
quadtree dla tego obszaru i na jego podstawie odnalez
ć właściwą listę obiektów. Następnie
przeszukać ją oraz wszystkie listy położone poniżej i powyżej.
Waldemar Izdebski - Wykłady z przedmiotu SIT / Mapa zasadnicza 61
9. R-tree
Indeksowanie danych z wykorzystaniem struktury R-tree podobnie jak quadtree opiera
się na podziale obszaru właściwego dla bazy danych na mniejsze prostokątne fragmenty. W
podziale niniejszym w odróżnieniu do quadtree dozwolone jest pokrywanie się utworzonych
w wyniku podziału fragmentów (rys. 5.11). Utworzone w fragmenty organizuje się w
strukturÄ™ drzewa jak przedstawiono to na rys. 5.12. Charakterystyczne w utworzonym
drzewie jest występowanie dwóch rodzajów węzłów to jest tzw. węzłów pośrednich oraz
liści. Węzły pośrednie zawierają informacje o zakresie grupowanych węzłów pośrednich
niższego poziomu. Liście natomiast zawierają dostęp do konkretnych obiektów terenowych.
Struktura R-tree charakteryzowana jest maksymalną liczbą możliwych potomków w węz
le M
oraz liczbÄ… minimalnÄ… obliczanÄ… jako M/2. IlustracjÄ™ organizacji struktury R-tree
przedstawiono na rysunkach rys. 5.12 i 5.12.
3
9
Y
2
8
A
4
10
5
C
1
11
12
6
7
X
B
D
Rys. 5.11. Podział płaszczyzny zgodnie ze strukturą R-tree
X Y
A B C D
2 3 8 1 5 6 4 9 10 7 11 12
Rys. 5.12. Schemat drzewa korespondujący z podziałem przestawionym na rysunku 1.11.
Waldemar Izdebski - Wykłady z przedmiotu SIT / Mapa zasadnicza 62
Organizacja struktury R-tree może być statyczna lub dynamiczna. Organizacja statyczna
charakteryzuje się tym, że już na starcie znane są wszystkie elementy do podziału natomiast
w organizacji dynamicznej kolejne elementy dodawane są do już istniejącej struktury. W
przypadku dodawania nowego elementu do węzła zawierającego już maksymalną ich liczbę
wiąże się z dokonaniem podziału elementów na dwa nowe węzły.