Grafy jako narzędzie do definiowania relacji topologicznych pomiędzy danymi przestrzennymi

• Autorzy: Lewandowicz E.

Warianty tytułu

EN

Graphs as a tool for defining topological relationships between spatial data

• Języki publikacji: PL

Abstrakty

EN

Graphs are abstract mathematical objects enabling to describe data in a simple form. The graph theory provides tools for solving specialized tasks, including typical problems related to spatial analysis: travelling salesman problem, path analysis, network flow. This paper discusses the possibility of applying graphs to determine topological data of a complex of geographical objects. A geometric graph has been constructed on the basis of a map fragment showing registration parcels. Its nodes represent boundary points, and edges - boundary lines. The neighborhood matrix describing this graph contains topological data, i.e. relationships between boundary points and lines. The neighborhood matrix describing this graph contains topological data, i.e. relationships between boundary points and lines. Traditionally, these data are saved as database records and associated with single objects.The above matrix contains all data concerning the whole complex of objects, which enables their processing. An algorithm transforming a graph representing boundary lines into a graph describing boundaries is proposed in the paper. This transformation involves reduction of 2-degree nodes, connected with summation of neighboring edges. In the transformed graph edges describe boundaries between two parcels. The data related to the administrative division of a country are specific, as they cover the spatial area completely, without any intervals, blanks or overlaps. These data should be illustrated using special planar graphs. A planar graph is a graph that can be embedded in a plane so that no edges intersect. An example may be a graph representing registration parcels. A geometric planar graph, in the form of a flat drawing, divides a set of points into regions (faces). Known algorithms can be used for obtaining cyclical graphs, describing each region separately, by means of nodes and edges. Such a description is possible even when the so called enclave is located within the parcel. Graphs illustrating this situation are presented in the paper. Enclaves may be represented as the so called islands. In such a case, a graph is composed of two subgraphs. Two independent graphs may be joined by the so called bridge, and two subgraphs . by an edge. In these two solutions concerning enclave representation it is possible to determine regions. The number of regions within a planar graph can be determined from the Euler.s formula, which defines the correlation between the number of regions, and the number of edges and nodes in a graph. Planar graphs describing regions may be transformed into dual graphs, where relationships between neighboring regions are presented in a simple way. In dual graphs nodes represent regions, and edges between nodes indicate that regions have a common edge. The degree of the node informs about the number of neighbors. If a parcel is described using a dual graph, a single matrix contains information on neighborhood relations within the whole complex of parcels. Traditionally, this information is contained in GIS databases in the form of single records corresponding to particular parcels. The theoretical bases of spatial data description applying graphs, presented in the paper, show that topological relationships within the whole complex of geographical objects can be recorded in a simple way. This in turn enables us to perform typical spatial analyses and to process topological data.

Słowa kluczowe

PL

grafy; relacje przestrzenne; relacje topologiczne

EN

graphs; spatial relations; topological relations

• Wydawca: Polskie Towarzystwo Informacji Przestrzennej
• Czasopismo: Roczniki Geomatyki
• Rocznik: 2004
• Tom: T. 2, z. 2
• Strony: 160--171
• Opis fizyczny: Bibliogr. 12 poz., rys.

Twórcy

autor

Lewandowicz E.

• Katedra Geodezji Szczegółowej Uniwersytetu Warmińsko-Mazurskiego w Olsztynie

Bibliografia

• Bera R., Claramunt C., 2003:Topology-based proximities in spatial systems. Journal of Geographical Systems. Springer-Vertag 2003 - 5- s. 353-379.
• Ford L.R., Fulkerson D.R., 1969: Przepływy w sieciach, Wydawnictwo Naukowe PWN, Warszawa.
• Gedgewick R., 2003: Algorithms Jave. Addison Wesley.
• Grover W., D., 2003: Mesh-Based Survivable Networks. Prentice Hall PTR.
• Kulikowski J., L., 1986: Zarys teorii grafów. Państwowe Wydawnictwo Naukowe PWN Warszawa.
• Loudon K., 1999: Mastering algorithms with C. O’Reilly.
• Molenaar M., 1998: An introduction to the theory of spatial object modeling for GIS. Taylor & Francis.
• Sysło M.M., Deo N., Kowalik J.S, 1995: Algorytmy optymalizacji dyskretnej z programami w języku PASCAL, Wydawnictwo Naukowe PWN, Warszawa.
• Reingold E.M., Nievergeld J., Deo N., 1998: Algorytmy kombinatoryczne. Wydawnictwo Naukowe PWN, Warszawa.
• Ross K. A., Wright Ch.R. B., 2000: Matematyka dyskretna. Wydawnictwo Naukowe PWN. Warszawa.
• Urbański J., 1997: Zrozumieć GIS, Analiza informacji przestrzennej. Wydawnictwo Naukowe PWN Warszawa.
• Wilson R., 2000: Wprowadzenie do teorii grafów. Wydawnictwo Naukowe PWN Warszawa.