Coğrafi bilgi sistemlerinde veri yapıları ve uygulamaları

Abstract

Karar destek amaçlı kullanılan Coğrafi Bilgi Sistemlerinde istenen sorgulamaların yapılabilmesi için grafik veri tabanının yapısının amaç doğrultusunda alabileceği çeşitli şekiller vardır. Bunlardan topolojik veri yapısı istenen sorgulamaların en çoğuna cevap verebilen bir veri yapısıdır. Mevcut CAD sistemlerinden elde edilen veya Spagetti veri yapısı ile sayısallaştırılan haritaların topolojik veri yapısına dönüştürülmesi için bir takım işlemlerden geçmeleri gerekir. Bu işlemler sorgulama sırasında yapılırsa işlem hacmi çok yoğun ve cevap süresi çok fazla olur. Bunun için yoğun coğrafi hesaplamalar bir kere yapılıp topolojik yapı içerisine işlenirse daha çok sayıda sorgulamalar yapılabilir ve daha kısa zamanda cevap alınabilir. Bu çalışmada Spagetti veri yapısından Topolojik veri yapısına dönüşüm anlatılmış, bu dönüşüm bir kadastro haritasına uygulanmış ve topolojik sorgulamalardan örnekler bu harita üzerinde denenmiştir

Nowadays, Geographical Information Systems are being used for various kinds of purposes as decission support systems (DSS). Some GIS software can present limited capabilities to implement complex applications and answer complex queries. Mostly the reason for this is the data structure used. In Geographical Information Systems there are several data structures used in order to answer a number of queries. While some data structures are developed for specific purposes, some are developed for computer aided design (CAD) purposes. Topological data structure, most of all, can answer much of the queries. Existing Spaghetti data structured maps must be processed to convert to topological data structure in order to be able to make queries on them. In this study, conversion from spaghetti to topological data structure is explained and applied on a cadastral map, then made some topological queries on the map. It is an advantage that the data structure in GIS is flexible to shape from application to application. This way an optimum solution can be found according to the purpose of the applications. The functional elements of a GIS are data acquisition, data management, conversion, geographic analysis, queries, product generation. Data acquisition is the process for transfering data from the data source to the geographic database. Some examples are scanning, remote sensing, photogrammetry, digitizing, input from CAD systems and manual input. This stage is the most money, time and effort costly stage of a GIS. The second process, data management, is related with database management, logical modeling of geographic data, logical representation and storing. This step includes the implementation of the database and accessing it. Modern database management systems keep the users away from the details of storing data on the hardware. The conversion step can be seperated into several processes like data controls, eliminating errors and providing geometric quality. Some of these processes are interactive grafic editiing, data classification, coding, scrubbing etc. Updating, deleting and adding graphic and non-graphic data are performed in this stage. XI in the geographical analysis step, new geographical data is produced from the data gathered. This data can not be provided directly from the data sources. The processes in this step is the main difference between a CAD system and a GIS. Some geographical analysis tools are buffering, overlaying, reclassification and netvvork analysis. Oueries may start from both graphics and non-graphics parts. The types of queries used in GIS are 1. Graphics to database queries 2. Database queries 3. Database to graphics queries 4. Metne queries 5. Topological queries 6. Order queries ; 1. Graphics to database queries start from graphics, for example by selecting a single graphic element ör elements in a fence. After asking the question "What is this?", ali the information in both graphic and non-graphic database can be listed. The relation betvveen graphics and database is established with unique keys assigned to the graphic elements. 2. Database queries start from the non-graphic part and a list is produced according to the criters given. The combination of more than öne criter can be used. Data base management systems provide capabilities like these. 3. If the results of the database queries are vvanted to be shown on graphics, database to graphics queries are used. The graphic elements vvhich satisfy the criteria given are highlighted on the screen. 4. Metric queries are based on metric relations betvveen graphical elements and analytical geometry rules. Some examples are, the distance betvveen two graphic elements, the direction of öne element with respect to another, the length of a linear element, the area ör perimeter of a face ete. 5. Topological queries are based on the geometric relations and topological relations betvveen graphic elements Vector Data Structures in GIS Vector data structures are formed using points vvhose koordinates are knovvn. Most of graphics softvvare and CAD systems work with basic vector elements like points, lines, circles in their intemal structure. Some common vector data structures are: 1. VVhole polygon data structure 2. DIME (Dual Independent Map Encoding) 3. TIGER (Topologically Integrated Geographic Encoding and Referencing) 4. Spagetti data structure 5. Arc-node data structure 6. Topological data structure These data structures have been improved to increase the number of types of queries and increase the performance of queries. The improvement of these data structures are currently being proceeded. 1. in a vvhole polygon data structure, each layer in the database is divided into a set of polygons. Each polygon is encoded in the database as a sequence of locations that define the boundaries of each closed area in a specified coordinate system. Each polygon is then stored as an independent feature. Attributes of the polygons, such as land cover ör ovvnership may be stored with the coordinate üst. By maintaining each polygon as a separate entry in this way, the topological organization of the polygons is not maintained. 2. DIME (dual independent map encoding) file structure was designed to incorporate topological information about urban areas for use in demographic analyses. VVhile DIME files themselves do not generally correspond to the intemal database organization of a GIS, they are in common use as an archive data format as well as a defined format for data exchange betvveen different systems. The line segments are shared betvveen adjacent polygonal units. When a line segment is a part of street, the address ranges for both sides of the street may be stored. A majör disadvantage of DIME structures lies in the difficulty of manipulating complex lines, as in functions that require search along streets. An advantage of the system for some applications is its ability to match addresses of spatial objects in multiple files, since the addresses are explicitly stored in the DIME file. 3. TIGER (topologically integrated geographic encoding and referencing) files contain topological data structures describing how points and lines relate to each other on a map to define geographic areas. The files combine three sources of data (line-segment-based maps, DIME files and geographic area relationship files) into öne integrated relational database. They contain geographic feature references that can be encoded directly onto computer-produced maps. Unlike the DIME files, vvhich utilize a flat file structure containing point, line, and area information entirely within each record, the TIGER files are relational in structure, with ali geometric and topological relationships and feature attributes stored either explicitly in the tables of the database, ör implicitly in the database structure itself. 4. Most of today's spagetti structured GIS softvvare have been architectured on CAD systems. in CAD systems, some properties are stored along with the coordinate data. This is established by a structure such that the header data is followed by coordinate data. The header information is element type, color, level, X-low, Y-Iow, X-high, Y-high, ete. Most of today's computer assisted mapping and GIS systems store their vector data in spagetti structure as imported form CAD. When entering an element into a CAD, user first sets the level, color, style, and vveight, issues the proper digitizing command and then the CAD system stores the element with these parameters. This should not be the case in GIS. The user should teli GIS vvhich feature class he is going to enter only and the definitions should be taken from tables stored is the database. Spagetti data structure inhibits a number of problems in terms of geometric quality. Because the topology is not shared, common feature components have to be digitized tvvice and this causes gaps and slivers between adjacent elements. in spageetti data structure, ali the graphics-to-database and database-to-graphics queries can be performed. Metric queries can be answered after calculations. Some topological queries can be ansvvered after long calculations because the data structure itself doesn't contain topology. 5. in arc-node data structure, objects have a hirerarchical structure in the database. Arcs are sets of line segments defined with X and Y coordinate pairs. Nodes are at the end points of the arcs. Polygons are areas surrounded with a set of arcs. Nodes are shared by other polygons. There is maximum öne are that joins two nodes. Node can be on more than öne are. Two arcs can not intersect. Arc-node data structure has many advantages compared to spagetti ör polygon data structure. First of ali replications are prevented vvhile producing the geometry because adjacent elements share the same nodes. This way, no slivers and gaps betvveen elements can be observed. This causes a clear geometry. Areas are closed properly, the starting node being the same with the ending node. Ali graphics-to-database and database-to-graphics queries can be ansvvered in arc-node data structure. Not only the element selected, but the elements linked to it can also be queried in this structure, different than spagetti data structure. As metric relations are not stored in the database, metric queries can be ansvvered after calculations as in the spagetti data structure. The difference is that the results of these queries are reliable in arc-node data structure. 6. Topology is often defined as the study of continuity vvhile in discrete situations, topology usually refers to the connectivity aspects. Topology studies the properties that remain unchanged when the figures are transformed by continuous deformations. it can be defined as coordinate-free geometry. Â topological data structure consists of points, edges and faces. Points are 0- dimensional elements defined with a coordinate pair. Edges are linear elements defined with starting and ending points. Edges are formed with line segments. A face is a 2-dimensionaI element bounded by edges, that is not further divided by an edge. Face definition vvhich is different from area boundary in arc-node data structure, ailovvs operations on closed shapes like area fiil, hatching and patteming. Explicit storage of topological relationships like start and end nodes, left and right faces, directions brings marvelous opportunities for the geographical analysis operations. Toplogical data structure can ansvver almost ali types of queries. in graphics-to- database queries, the selected element can belong to more than öne feature. So selecting an element highlights the vvhole feature. There is no difference in database-to-graphics queries betvveen arc-node and topological queries. Metric queries stili need computations. Ali of the topological queries can be ansvvered directly. Conversion from spagetti to arc-node data structure There are three approaches in converting spagetti data structure to arc-node data structure:. Operator driven toplogy creation,. Real time arc-node creataion. Spagetti to arc-node conversion The first of the listed is giving the responsibility of creating the topology to the operator using the screen cursor snapping capability provided by most of the related software. The socond is to create the arcs and nodes automatically during the digitizing. The last is to run batch programs on spagetti data structure to convert to arc-node data structure. The last approach has gained the most popularity because it is the most reliable one and this will be studied in deep in this study. The first step in spagetti to arc-node conversion is the conversion of all the elements to line segments. After, elements which reside within the minimum tolerance are joined. The third step is the calculation of minimum bounding rectangles for each element. This is for performance reasons. To determine whether two elements intersect or not, first their mbr s are scanned. If the mbrs don't overlap, then it can be said that these two elements do not intersect. In the fourth step the mbr groups are formed. This way, there will not be a search between separate mbr groups. In the fifth step, the orders of all the nodes are recorded in the database. The order of the nodes at the end and starting points is 1, the order of middle nodes on an arc is 2. The order of single point is 0. If there is an intersection between elements, a node is added at the intersection point and the elements are divided into two elements at the intersection point. This process is repeated for all the mbr groups in the map. Conversion from arc-node to topological data structure Here again the approach of converting with programs running in batch mode will be studied. In the first step, the termination directions of arcs at nodes with 1st or higher order are calculated an sorted in ascending order between 0 and 360 degrees. Secondly, the edges are constructed by connecting subsequent 2nd order nodes. This is done by starting from a 1st or 3rd or higher order node and connecting arc ends untill another 1st or 3rd or higher order node is reached. Each arc is navigated once. In the third step, an envelope polygon is constructed for the whole map by starting from the min X node and branching to the most left-hand edge at the junctions. After the envelpe polygon is formed, the faces in the envelope are formed. This is done by starting from the same node as before and branching to the most right-hand edge at the junctions. Once the starting point of a face is reached, the face is added to the database and the search continues with the next face. During the navigation over the edges, left and right face information are updated for the edges in the database. This is repeated untill all xv the edges in the map are navigated twice. At the last step, the bounding face for each 0 order node is searched and recorded to the database. In this study, these conversion methods are applied to a spagetti data structure and produced a topological data structure using a relational database. Later, query programs are written to show what kind of queries could be done in toplogical data structure. The listing of the conversion and query programs are listed in the apendices.