An Improved and Efficient Storage Technique for GIS Geometric Primitives Based on Minimum Bounding RectanglesF.Sagayaraj Francis Department of Computer Science & Engineering and Information Technology Pondicherry Engineering College Pondicherry, India fsfrancis@rediffmail.com P.Thambidurai Department of Computer Science & Engineering and Information Technology Pondicherry Engineering College Pondicherry, India B.S.Bharadwaj Department of Computer Science & Engineering and Information Technology Pondicherry Engineering College Pondicherry, India G.N.Balagei Department of Computer Science & Engineering and Information Technology Pondicherry Engineering College Pondicherry, India N.Hemant Department of Computer Science & Engineering and Information Technology Pondicherry Engineering College Pondicherry, India Abstract Geographical Information Systems (GIS) objects such as rivers, roads, railway lines, regions and cities are generally represented using geometric primitives such as points, lines and polygons. These primitives have dimensionalities ranging from 0 to 3. A good number of methods are proposed in the literature and consequently used in commercial packages that require the GIS objects to be approximated to the above said geometrical primitives. These methods put a lot of constraints and require compromising at various fronts when it comes to representation and storage. Hence storing objects has always been a major concern in GIS. It is also obvious that efficiency in storage also improves efficiency in processing. This paper proposes a novel way to represent and store objects in GIS space (0 to 3 dimensions) using MBRs (Minimum Bounding Rectangles). The method is also scalable and extendable to n-dimensional space. Most of the commercial packages are good in handling objects, which have regular structure, but the discrepancies in these methods arise when it comes to storing objects that are distortions, extensions or multiplications of these regular structures. Moreover they also fall short when it comes to handling complex cases like self-crossing structures and disjoint structures. As a matter of fact GIS usually deals with objects that have the above said characteristics. The data structure and the storage method proposed, which is based upon the concept of MBRs follows a generalized procedure to store the GIS objects instead of ad hoc methods. The proposed data structure has been compared with the methods in the literature and commercial packages. It is very much evident that the data structure proposed was more flexible and efficient when encountered objects, which are highly complex. 1. Introduction Spatial data is defined as the data that pertains to the space occupied by objects. Spatial data represents the essential location characteristics of real or conceptual objects as those objects relate to the real or conceptual space in which they exist [3]. Spatial data is conceptually defined as geometric data such as points, lines, rectangles, surfaces, volumes and etc. In GIS these conceptual objects (and hence geometric data) represent the GIS objects such as, cities, rivers, roads, states, crop coverage, mountain ranges etc [1] [2]. Applications like environmental monitoring, geographic information systems, earthquake research etc require GIS that are robust and efficient in terms of storage, retrieval, processing and good graphical reconstructing. The volume of data that is involved in such systems is huge and dynamic. Static querying (queries on spatial relationships, distance measurements, directions, etc.) and dynamic querying (Addition, deletion and updating) are frequent. Graphical reproduction of GIS objects is only of paramount importance. In this paper the ‘spatial data’ and ‘spatial objects’ are used interchangeably with ‘GIS data’ and ‘GIS objects’. The reasons said above are the motivation behind developing a generalized method for representing and storing GIS data, the prime objective of this paper. Any good and generalized representation method must be able to accommodate all types of objects from simple to highly complex. The representation in turn must facilitate efficient storage, retrieval and querying. This paper gives (i) a new GIS object representation method in terms of Minimum Boundary Rectangles (MBRs), (ii) a GIS database Schema and (iii) arguments in support of the efficiency of the proposed methods and schemes. The usage of MBRs is motivated by the effective usage of them in indexing multidimensional data in database applications [14] [12]. Further advantages of employing MBRs to represent GIS objects are listed later in this paper. Much spatial data is made up of coordinates. A coordinate is a number that denotes a position that is relative to a point of reference. For example, in GIS degrees of latitude are coordinates that denote positions relative to the equator. Degrees of longitude are coordinates that denote positions relative to the Greenwich meridian [15] [16]. The simplest spatial data item consists of two coordinates that define the position of a single geographic feature in a two dimensional space. A more extensive spatial data item consists of several coordinates that define a linear path such as a road or river. A third kind consists of coordinates that define the boundary of an area such as the boundary of a land parcel or flood plain. The mapping between GIS objects and geometric objects is given below:
 Figure 1a. Object with branches  Figure 1b. Object with combination of dimensions  Figure 1c. Objects with holes and self-crossing 2. Literature Survey There are wide ranges of commercial GIS software that use data structures that are very specialized and fulfill a particular objective. Commercial packages give ad hoc models and methods on to which the natural models and methods of the application space have to be mapped [15] [16]. There are quite a few models in the literature that are extensions of models used for other type of data or application [6] [4]. The common feature of the commercial software and packages is the usage of points in plotting the boundaries of objects. These points are used for representing, storage, retrieval, processing and reconstruction of the object. In the case of regular objects, the edges of the object are stored if the object is composed of straight lines. On the other hand, if the object is made up of a connected sequence of circular arcs then the starting point of the arc, the end point of the arc and some arbitrary point on the arc describe each arc on the object. In the case of irregular objects, they follow ad hoc procedures, which approximate the boundary of the irregular object by plotting points along the boundary and draw straight lines connecting the points. Space partitioning techniques are also used for approximating the irregular objects [13] [16]. Partitioning is done by successively dividing the space of the object into hierarchical circles [11] or hierarchical rectangles [16] and the circles or rectangles that are occupied by portions of the object are considered as constituents of the object. A variation of this method fills the irregular object with varying sized circles [17] [18]. These circles collectively represent the object. Careful analysis of these methods reveal following shortcomings:
3.1. Representing Spatial Objects This section introduces a new method of representing GIS objects. This method partitions the given GIS objects and each partition in represented by an MBR. Each MBR may be of any dimension from 0 to n in an n-dimensional space. The MBRs may overlap, cover the entire object or cover the individual constituents of the GIS object as shown in figure 1. The GIS object then, is the collection of MBRs. The best strategy for identifying MBRs for a GIS object is beyond the scope of this work and would be taken in future works. This method facilitates the storage all types of GIS objects including regular, non-regular, open and close of any shape and size. The storage space needed for this type of data structure is relatively very small as only the coordinates of the respective MBRs are stored and not of each and every point of the object. This new data structure supports every possible spatial object types such as points, line strings, polygons, multi points, multi line strings, multi polygons and irregular objects. 3.2. Database Schema In the proposed model, the data are stored in many tables. But these tables belong to any one of the two table types defined in the model. The tables are structurally similar to relational tables. But, the constraint on the atomicity of data at the intersection of each row and column is waived. The first type of table is the Object_Table, which collects the objects of a single object space. Each individual object of the space makes up a row of the table and belongs to the type Individual_Object. Each attribute of Individual_Object makes a column of the table. The second type of table, Metadata_Table collects the data about the object spaces. Each row of the Metadata_table record data about one table of Object_Table type (and hence one object space) and belongs to the type Metadata_Table_row. Each attribute of Metadata_table_row makes a column of the table. Obviously for a given single GIS space, there can be only one table of Metadata_Table type and many tables of Object_Table type. Each table of Object_Table type may be a collection of objects that belong to the same semantic or syntactic group based on the requirements of the application. But the definition of Object_Table type does not put any constraints of the type of objects that are collected in the table of this type. It can accommodate all types of GIS objects in all dimensions. The definition of types is given below:
type Individual_Object
{ Object_Id generic,
Object_Name generic,
Non_Spatial_Attributes Set of Attribute_Pair,
Object Set of MBR }
type Attribute_Pair
{ Attribute_Name generic,
Attribute_Value generic }
type MBR
{ Dimension numeric,
Structure_Type generic,
BLPoint Ntuple,
TRPoint Ntuple }
type Ntuple { PArray Axis_Value[N]; }
type Axis_Value { Value generic; }
type Metadata_Table_Row
{ Object_Table_Id generic,
Object_Table_Name generic,
Object_Table_Dimension numeric,
Object_Table_Bounds_Limits Ntuple }
Object_Id provides a unique identification to each object in an object space. Object_Name is the geographical name of the object. Non_Spatial_Attributes column is used to specify the non-spatial attributes that the objects possess. Non-spatial attributes are mainly physical properties of an object rather than the topological characteristics. These physical characteristics include properties like color, texture etc. This is a set of pairs (Attribute_Name, Attribute_Value). Object is the actual set of MBRs that represent the geographical object. The object in the figure is described using MBRs with 0, 1 and 2 dimensions. Dimension gives the dimension of the object. Structure_Type tells the actual structure of the object, i.e., whether the object is a line, a string or an arc or in the case of two-dimensional objects upper triangular or lower triangular area, etc. Some of the predefined values are as follows: 0 - one-dimensional line string; 1 - Upper triangular area; 2 - Lower triangular area; 3 - Whole area; 4- Circular arc. 1, 2, and 3 are used to score over a disadvantage of the inability to store lines, which are not parallel to the axes. BLPoint and TRPoint are the ones, which actually store the lower left, and upper right coordinates of the MBRs. Metadata_Table defines the boundary limits of each object space and also stores the maximum dimension of the object space. Figure 2 gives a partial instant of a schema that contains the objects in figure 1.Object_Table_1  Object_Table_2  Metadata_Table_1  Advantages of the Proposed Method
 Figure 3. Graphical reproduction of the 2-D object stored as MBRs 4. Comparisons and Conclusion Qualitative comparisons of a few features and parameters between the proposed method and very popular commercial software were done on a set of fifty spatial objects. The objects shown in the figures of this paper are a few representative ones. Quantitative comparisons in terms of number of points required were also made. The results of the qualitative and quantitative comparisons with respect to the objects in figure 1 are tabulated in table 1. The contents of the tables are to be understood in conjunction with the commercial software representation which is given below: Commercial software representation of object in figure 1a MDSYS.SDO_GEOMETRY (2002, 8307, NULL, MDSYS.SDO_ELEM_INFO_ARRAY(1,2,1,5,2,1,9,2,1,13,2,1,17,2,1,21,2, 1,25,2,1,29,2,1), MDSYS.SDO_ORDINATE_ARRAY (2,4,4,5,2,4,5,2,5,4,10,6,7,5,8,8, 9,4,12,13,13,4,16,6,17,4,18,3,1,4,18,4)) Commercial software representation of object in figure 1b Not Possible Commercial software representation of object in figure 1c (partial, another part cannot be stored) MDSYS.SDO_GEOMETRY (2002, 8307, NULL, MDSYS.SDO_ELEM_INFO_ARRAY (1, 3, 1, 11, 3, 1), MDSYS.SDO_ORDINATE_ARRAY (0,4,5,4,4,0,1,0,0,4,1,1,1,3,4,3,4,1,1,1))  References
|