RozwiÄ…zanie zestawu E:
Zadanie 1:
Rastrowy zbiór globalny
Model rastrowy (mozaikowy). - ziarniste widzenie przestrzeni, polega na arbitralnym podzieleniu obrazu na małe elementy - piksele. Dzielenie to nazywamy teselacją.
1.Zbiór globalny
Jeżeli na obraz mapy nałożymy siatkę rastra to wszystkie obiekty wyrażone będą za pomocą piksela.
Struktura i cechy zbioru globalnego:
Zbiór globalny ma strukturę tablicy. Ma tyle wierszy ile jest pikseli. Ma tyle kolumn ile jest atrybutów.
Wymiar tej tablicy jest bardzo duży. Cechy dla pojedynczego piksela mogą się powtarzać. Zbiór globalny jest zbiorem binarnym a w rzeczywistości może zawierać dowolne wartości (kolory, barwy). Zbiór globalny jest zbiorem kompletnym. Zapisuje cały przegląd sytuacji. Przyjmuje że coś istnieje albo nie. Możemy wpisywać wartość dowolnych dziedzin.
Jest uniwersalnym zapisem. Wady: jest
bardzo duży, jest nieoszczędny, musimy go selekcjonować.
Zaleta: pełny zapis świata realnego (żeby wygenerować warstwę trzeba przeprowadzić selekcję).
2.Zbiór globalny w wersji rozwarstwionej- zbiór tablic
(każda kolejna tablica to kolejny atrybut.) Z jednej tablicy powstaje tyle tablic ile atrybutów. Nadal ma dużo zer. Generowanie zestawów tematycznych musi być zawiązane z selekcja. Zbiory warstw tematycznych zespalają potrzeby generowania zestawień tematycznych. Takie zbiory powinny być kompresowane.
Kompresja obrazu- pozbycie siÄ™ zer:
Początkowy + liczba powtórzeń
Początkowy + końcowy i co tam jest
Zbiór globalny w wersji rozwarstwionej jest w dalszym ciągu wielki i nieoszczędny, dlatego też powstał trzeci sposób zapisu.
3.Zbiory warstwy tematycznej w oparciu o hierarchiczne rozwinięcie obrazu
Sporządza listę agregatów (blok) które całkowicie mieszczą się w danych obiektach od największego do najmniejszego agregatu - wynikiem jest lista kodów agregatów, które nie dzielą się dalej bo kolejne elementy mają takie same atrybuty
Żeby zbudować każdą klasę musimy sporządzić listę kodów drzewa czwórkowego. Podział przestrzeni jest więc zgodny z drzewem czwórkowym, a zbiór warstw tematycznych ma strukturę listy.
|
|
|
|||
|
|
|
|
||
|
|
|
|
||
|
|
|
|
||
|
|
|
|
||
|
|
|
Kolejność narastania kodów w schemacie drzewa czwórkowego pokrywa się z kierunkiem przebiegania zgodnym z linią Peana.
linia fraktalna Peana umożliwia budowę związków hierarchicznych (bloków pikseli), dalsze stopnie o identycznym kształcie, wykonuje krótkie przebiegi w lokalnej przestrzeni, oscyluje w lokalnej przestrzeni, minimalna liczba skoków. Niezmiernie oszczędny zapis.
Każdy kolejny powstaje z 4 poprzednich
Zalety: - oszczędny zapis przy użyciu stopni podziału. - obszar reprezentowany przez max agregaty -regularność -łatwość zamiany na współrzędne -pola będące sąsiadami mają podobne kody, -hierarchiczna struktura, -wyższy stopień organizacji.
Opis przebiegu zapisu warstwy:
Poszukujemy pełnych agregatów, rejestrujemy kolejne maksymalne agregaty na poszczególnych poziomach podziału, które mieszczą się całkowicie w konturach obiektu danej klasy. Kody tych agregatów zapisujemy w postaci listy. Takie agregaty nie podlegają już dalszemu podziałowi, ponieważ posiadają ten sam atrybut. To daje znaczną oszczędność zapisu, ponieważ duże obszary są reprezentowane przez agregaty o maksymalnej wielkości. W miarę dopasowywania się granic obiektu, tworzymy zapis coraz mniejszych agregatów. Lista się powiększa ale i tak ten zapis jest o wiele bardziej oszczędny, niż zbiór globalny lub zbiór globalny w wersji rozwarstwionej.
Zadanie 2:
Sposób (model rastrowy) - model w którym zapis przestrzeni 2D jest ukierunkowany na elementy składowe obrazu - regularna siatka pól elementarnych jest rozwijana do postaci liniowej, a z chwilą uformowania siatki pól (zwanej rastrem) każdy obraz może być wyrażony wyłącznie poprzez geometrię elementów siatki;
Wybór sposobów przebiegania:
a) wierszowe-
duże skoki
i wiele skoków
b) serpentynowy
-eliminuje skoki
ale zaburza kolejność
c)spiralny-usuwa skoki, jest zawsze
w tych samych kierunkach, sÄ… tu
martwe przebiegi, została
wprowadzona asymetria: gęstość
przebiegania na zewnÄ…trz jest inna
niż gęstość w środku.
d)diagonalny Cantora (usuwa skoki ale zaburza kolejność,
wprowadza dezintegracjÄ™,
sÄ… tu martwe przebiegi,
są duże przebiegi).
sposoby hierarchiczne:
e) przebieganie Hilberta-kierunek umożliwia
budowę związków hierarchicznych, oscyluje
w lokalnej przestrzeni, symetryczny
względem linii płn-płd, wadą jest to że
hierarchia jest oparta o obracanie o 90O
f) linia fraktalna Peana-umożliwia budowę związków hierarchicznych (bloków pikseli), dalsze stopnie o identycznym kształcie, wykonuje krótkie przebiegi w lokalnej przestrzeni, oscyluje w lokalnej przestrzeni, minimalna liczba skoków. Niezmiernie oszczędny zapis.
Każdy kolejny powstaje z 4 poprzednich
g)kody Gray'a- eliminuje
duże błędy, symetryczny
w kierunku linii płn-płd
Zadanie 3:
Nieregularna sieć trójkątów powstaje głownie jako efekt bezpośrednich pomiarów terenowych, gdzie cały zakres opracowania zapełnia się trójkątami opartymi o punkty pomiarowe. Ponieważ w tych modelach wykorzystywane są wszystkie punkty charakterystyczne model jest stosunkowo dokładny.
a) triangulacja Delaunay'a
Trójkąty tworzone są w ten sposób aby żaden z punktów nie należących do niego nie był
położony wewnątrz okręgu opisanego na trójkącie
b) Obszar Thiessena stanowi zbiór wszystkich punktów płaszczyzny, dla których odległość do punktu centralnego jest mniejsza od odległości do pozostałychpunktów. Ograniczenia tego obszaru stanowią odcinki symetralnych do boków triangulacji Delaunay'a.
Triangulacja Delaunaya maksymalizuje wartość minimalnego kąta w trójkącie.( z spośród wszystkich wyselekcjonowanych punktów w kole do polaczenia pkt centralny zostanie polaczony z tymi punktami których symetralne utworzyły wielobok thiessen
Najczęściej stosowany jest algorytm Delaunay'a w którym wykorzystywane są poligony Thiessena. Triangulacja powinna być tak wykonana żeby: - tworzone trójkąty były możliwie zbliżone do równobocznych i możliwie małe; - każdy punkt ze zbioru punktów rozproszonych musi być uwzględniony; -procedura postępowania musi być jednoznaczną
Gdy nie są znane sposoby połączenia punktów stosuje sie triangulacje Delaunay'a z wykorzystaniem wieloboków Thiessena (mamy jak połączyć punkty rozproszone)
-trójkąty zbliżone do równobocznych
-każdy punkt musi być wykorzystany
-procedura musi być jednoznaczna
Przebieg tworzenia:
1. obieramy jakąś odległość R, równą lub większą niż średnia odl między pkt
2. zakreślamy okrąg o promieniu R na każdym punkcie, w tym okręgu znajda się punkty kandydujące do połączenia z tym punktem.
3. łączymy pkt P ze wszystkimi punktami kandydującymi i kreślimy symetralne tych odcinków
4. Z tych symetralnych budujemy najmniejszy wielobok. wielobok ten to wielobok Thiessena. Każdy punkt zawarty wewnątrz tego wieloboku jest bliżej punktu P niż innego punktu.
5. Spośród wszystkich pkt wyselekcjonowanych w okręgu punkt P będzie połączony tylko z tymi punktami, których symetralne utworzyły wielobok Thissena, te pkt będą tworzyły fragment przyszłej siatki.
6. Resztę punktów które nie utworzyły wieloboku się odrzuca.
7. Powyższa procedura powtarza się dalej dla wszystkich punktów rozproszonych
Matematycznie: budujemy ostrosłup i zakładamy, że V=0
Wysokość punktu P jest średnią ważoną z wysokości trzech punktów, gdzie wagami są pola trójkątów leżących naprzeciwko.
Zadanie 4:
4.1). S=(PRACOWNICY [NAZWISKOPRAC] + STUDENCI [NAZWISKOSTUD]) x LISTACZYTELN [NAZWISKOCZYT]
Komentarz: Najpierw musimy wykonać dwie projekcje: tabeli PRACOWNICY, tak aby pozostał jedynie atrybut z nazwiskiem pracownika (NAZWISKOPRAC), oraz tabeli STUDENCI, tak aby pozostał atrybut z nazwiskiem studenta (NAZWISKOSTUD). Projekcja jest to przekształcenie usuwające różnorodności, jest skreślaniem atrybutów i wybieraniem tylko tych, które nas interesują. Następnie przetworzone tablice po projekcji dodajemy do siebie. Dodawanie daje w wyniku relacje zawierające wszystkie krotki, a powtórzenia są usuwane. W dodawaniu wszystkie operanty muszą mieć takie same atrybuty, dlatego wykonano projekcję, aby obie dodawane tablice miały takie same atrybuty NAZWISKO. Nieważne tu jest, że nagłówki są różne (NAZWISKOPRAC i NAZWISKOSTUD), możemy wykonywać operacje na tych tablicach relacji, ponieważ mają atrybuty tego samego typu (nazwisko). Kolejnym krokiem było wykonanie projekcji tabeli LISTACZYTELN, tak aby pozostał tylko atrybut z nazwiskiem (NAZWISKOCZYT). Na koniec wykonano mnożenie pomiędzy wynikową tabelą z dodawania i wynikową tabelą po projekcji. Było to możliwe, ponieważ posiadały one takie same atrybuty. Wynikiem mnożenia jest obszar wspólny - krotki, które występują jednocześnie w obu relacjach. Jako wynik otrzymaliśmy nazwiska studentów i pracowników, którzy choć raz w tym semestrze byli w czytelni.
4.2). S={(PRACOWNICY + STUDENCI) / LISTACZYTELN} [NAZWISKO]
Komentarz: Logiczne jest, że będziemy te nazwiska poszukiwać na ogólnych listach nazwisk PRACOWNICY i STUDENCI. Musimy więc stworzyć taką zsumowaną listę, a później wykreślić z niej te nazwiska, które występują w zbiorze czytelników: LISTACZYTELN. Aby tego dokonać, najpierw wykonujemy dodawanie dwóch tablic relacji: PRACOWNICY i STUDENCI, a następnie od tablicy wynikowej odejmujemy listę czytelników (LISTACZYTELN), aby dowiedzieć się kogo na tej liście nie było. Musimy w tym przypadku być bardzo ostrożni i nie wykonywać projekcji wcześniej, tylko na samym końcu, ponieważ gdy w działaniach na tablicach relacji występuje odejmowanie, to nie możemy robić wcześniej projekcji, bo to zlikwidowałoby różnorodność. Dlatego też ostatnim krokiem było wykonanie projekcji względem NAZWISKA (mimo iż nagłówki w każdej z tablic były różne NAZWISKOSTUD, -PRAC, -CZYT, to działania na tych tablicach były możliwe, ponieważ atrybuty były takie same). W wyniku otrzymaliśmy tabelę z nazwiskami studentów i pracowników, którzy w tym semestrze ani razu nie byli w czytelni.