1588093937

2. Zapis danych przestrzennych za pomocą grafów

Na rys.2. przedstawiam prosty wycinek mapy i zapis jej treści w formie modelu topologicznego - grafu. Jak widzimy graf można uzyskać z prostego przełożenia rysunku mapy do schematycznej formy [12], W prostych rozwiązaniach obiekty punktowe mapy identyfikowane są węzłem grafu, obiekty liniowe krawędzią. Graf to zbiór węzłów i krawędzi:

G=[ W, K, f].    (1)

Funkcja f przyporządkowuje krawędzie do węzłów, gdyż każda krawędź zaczyna się i kończy w węźle. W naszym przykładzie węzły to trójstyki dróg i linii granicznych użytków oraz punkty informujące o polu namiotowym i pomniku przydrożnym. Krawędzie grafu to odcinki drogi i linie graniczne użytków.

Przyjmijmy G jako graf geometryczny, czyli taki, w którym węzły mają określone położenie. Jeśli krawędzie G nie przecinają się poza węzłem, to w takim grafie możemy wyróżnić ściany (obszary) grafu. W naszym przypadku jest to możliwe. Można wyróżnić pięć obszarów, które odpowiednio opisują: las, jezioro, łąkę i trzy obszary rolne.

Rys.2. Zapisy przestrzeni geograficznej a) w formie graficznej na mapie b) za pomocą uproszczonego modelu topologicznego obrazowanego grafem G

Zapiszmy model G (rys.Ib) w formie grafu etykietowanego (rys.3) z identyfikatorami: węzłów, krawędzi i obszarów . Stanowi on bazowy model topologiczny danych przestrzennych. Taki model zapisywany jest w tabelach relacyjnych bazy SIP, GIS [3,4, 5, 6, 7. 8], Ten model można wykorzystać jako podstawę do budowania pochodnych modeli topologicznych [1].

Przedstawiony model danych przestrzennych w formie grafu (rys.3) można zapisać w formach macierzowych. W literaturze przedmiotu mówi się o macierzach sąsiedztwa S, macierzy incydencji I i macierzy oczek (obszarów ) O [10, 11]. Macierze te określę jako macierze: sąsiedztwa węzłów S_w, (tab.l), zależności węzłów i krawędzi Z_W._K (tab.2) oraz jako macierz zależności obszarów¹ i krawędzi Z₀-k. (tab.3). Są to podstawowe macierze opisujące graf geometryczny G. Odpowiadają one zapisowi struktury danych przestrzennych w przyjętych formach tabelarycznych [3, 4, 5, 6,7, 8, 16].

Macierze S_w, Zw-k , Zo-k, opisują relacje między węzłami i krawędziami i obszarami grafu G. Macierz S_w informuje, które węzły są połączone krawędzią. Jeśli element macierzy (s_w)jj, (i, j €{1,2, ... 72}) przyjmuje wartość 1, to znaczy, że węzły opisane identyfikatorami i, j, są połączone krawędzią. Macierz Z_W._K przypisuje krawędziom węzły, czyli element macierz (z*^, (i €{1, 2, .... 12], je [i, 2, ..., 151) przyjmuje wartość 1, jeśli węzeł i stanowi wierzchołek krawędzi j. Przyjmując graf G jako graf geometryczny (o określonym położeniu węzłów), można w nim określić minimalne oczka, które stanowią obszary (ściany) w grafie. Kolejna macierz Zo-k przypisuje obszarom krawędzie ograniczające je. Element macierzy' (ZoOij, (i € jl, II, .... VI}, ye 2, .... 151 przyjmuje wartość 1, jeśli krawędź j stanowi granicę obszaru i.

2