Скачать 89.23 Kb.

Hypergraphbased Objectoriented Model for GIS Application Jin ZHANG Jianya GONG Dep. Of Surveying and Geomatics National Key Laboratory of LIESMARS Taiyuan University of Technology Wuhan University Taiyuan 030024, P.R. China Wuhan 430079, P.R. China Email: zhangjin@public.ty.sx.cn jgong@geoc.rcgis.wutsm.edu.cn Abstract: This paper discusses the features and relevant theories of GIS spatial data model based on hypergraph and ObjectOriented. The integrated concept model based on hypergraph and ObjectOriented model (HOOM) is proposed by author. HOOM has many advantages, such as its semantics features, its visualizing relationship among spatial objects or classes, and solving the general drawback of HBDS(Hypergraph based data structure),namely lacking math analyzing methods or theories. The principal contribution of this paper is that we study the Ksection and other theories of Hypergraph. According to research results, we can find that the Ksection can simplify relationships between feature classes or objects. The representation graph of Hypergraph can help transforming the viewpoint between the feature object and feature object relationship. Viz. the feature object relationship is transformed as a feature object and the feature object as a kind of relationship. An application example using HOOM is given at the end.of the paper. Key words: Hypergraph Objectoriented GIS Spatial data model HBDS DEM
With the developments of geomatics theories and applications, some GIS systems whose spatial data models are based on georelation or layer model are facing with great challenges. The GIS is used in many areas, where exist many theory problems, such as, the dynamic management of huge GIS data, the automatic generalization of GIS spatial entities and features, temporal GIS model and vectorraster integrating model, etc. All of these problems are concerned with GIS spatial model. General speaking, traditional GIS spatial model exists following primary problems[Jin ZHANG,1998a]: . GIS model and application used Objectoriented model and approaches are very popular in recent years, Objectoriented model and approache is one of the general method, which are lacking spatial relationship guideline in modeling spatial entities and features. . Attributive data or thematic data and spatial data are mostly only an ID relation. To solve above problem, we use hypergraph data model and Object –oriented model and approaches to define spatial entities and features, called HOOM. Hypergraph model and hypergraph data structure inherite the characteristics of object model. Depending on hypergraph model, complex and composite spatial relations can be described more easily; spatial 、attributive and temporal data also can be integrated more efficiently[Jin ZHANG,1998b]. Objectorient model and approaches are used to realize above perceptions.
The GIS spatial entities and features can be viewed in three abstractive levels: spatial concepts, spatial data models, and spatial data structures [E. Lynn Usery, 1996]. Cognizing and organizing spatial entities and features we form GIS spatial concepts, such as spatial concepts featurebased and georelationshipbased. Formalization of the spatial concepts leads to spatial data models. The most frequent spatial formalization for geographic phenomena is based on the Euclidean geometry and georelationship. Frequently, the spatial data model is used to refer to the combination of spatial and nonspatial or thematic data. The formalization includes the basic elements of the spatial concepts such as the point, line, area, polygon, volume, and pixel and attributes of these objects, such as location in some spatial reference system and their interrelations, such as topology. 3. HBDS HBDS (Hypergraphbased data structure) [F. Bouille, 1978,1994a, 1994b, 1994c] is a general model, which has been used for building an integrated object oriented platform, as a kernel of GIS. It is a knowledge model based on six basic abstract data type: class, attribute of class, link between classes, object, attribute of object, and link between objects, with some extensions. Hyperclass, hyperattribute, hyperlink, embryo, prototype, and all structure types are implicitly persistent. These types have a graphical representation allowing an ease and immediate understanding of the real world and provide a convenient communication between geographers. HBDS makes it easy and immediate to understand the real world and provide a convenient communication between geographers, but no suitable algorithm for HBDS. Especially, in HBDS, nobody try to apply hypergraph theory in HBDS. This paper will do so. The concept of attribution in hypergraph spatial data model has many meanings. It may be following items: (1) a number; (2) a Ndimension array; (3) the program or law; (4) a structure that can be described by hypergraph data model. Therefore attribution described not only the static character of object, but also the dynamic character of object. Hypergraph class and object have many relations, such as hierarchical structure and nonhierarchical structure. The hierarchical structure among hypergraph class shows class inheritance, association, and aggregation very clearly. The nonhierarchical structure is the base of distributed calculating and object generalization. One of the major advantages of HBDS is the generalization of graph theory[ Rongxing LI,1995]. The vertices may be complicated objects themselves (they may even be graph), and the edges of a hypergraph represent relationship among subsets of vertices. Therefore, in a HBDS the connections between objects in the same set and between classes of objects are allowed with both hierarchical and nonhierarchical relationship. When used for modeling, a hypergraph usually has objects with common attributes in the same substructures. Objects in a substructure might have relationship among themselves and relationships with objects outside. At one level, for example, internal relationships are not visible. Relationships with outside objects appear as hyperlinks. Basically, relationships between any objects at any levels can be expressed. Whether an object should be placed at a higher level or a lower level depends on significant factors to be considered, such as efficiency of data retrieval. All of these are only spatial data organizations. 4.HOOM[Jin ZHANG,1998a,1998b] HOOM stands for Hypergraphbased GIS spatial data model(in Fig.1). HOOM has similar semantics with ObjectOriented model. To define hypergraph spatial data model, first, we must define the class and object of hypergraph spatial data model. According to Objectoriented model and the characteristics of hypergraph, complex and composite spatial world can be defined as follow: 4.1 Geometrical object model Geometrical object model only describes the geometrical characteristics of spatial entity and feature. It describes the shape of feature, spatial location relation, spatial topologic relation, and geometrical measure information. Geometrical object can be divided to node, arc, polygon or pixel, and voxel. GIS spatial model Geometrical object model Feature Object model Represent model Temporal model Point Line polygon complex Point Arc segment Polygon Raster coding geometrical object Quadrtree polygon Arc Line Polyline Triangle Quadrangle Quadrtree node quadrtree Arc Fig. 1 hypergraph Object spatial data model 4.2 Feature object model Feature object model is used to explain the geometrical object model. In other words, Feature object model is defined by adding attributive values to geometrical object. So the same geometrical object may have different geographical attribution because different attributive value is added to the geometrical object. Feature object class is divided into point feature, line feature, polygon feature, and complex feature. The spatial relation of feature object is derived from its relevant geometrical object. 4.3 Spatial representative object model GIS spatial representative object model is divided to physical and logical representation. Physical representative model represents GIS distributed characteristics and operating, and physical storage. GIS distributed operating may produce many problems, such as concurrence control and consistence handle. To solve GIS distributed operating, we must add distributed ID label to geometrical and geographical object. GIS logic representation means that we usually need to calculate and draw thematic map from GIS spatial database and attributive database according to the certain conditions and formats. Also we need to manage and query GIS spatial data and attributive data according to the demands of applications. The association functions are used to associate the graphic object and geographical object. The main goal that we abstract the graphic class is facility in multiscale map generalization. Main methods are: Define dynamic association: The simplest rule that defines dynamic association is that from small to great for a given group discrete scales, scale_{1}, scale_{2},..., scale_{n} defining follow scale rules, when scale pertains to the scale extend (scale_{i},scale_{j}), geographical objects are associated with the graphical objects according to the association attributes and association functions. It is not displayed when the association graphics are null. The more complex rules that define dynamic association are establishing map generalization rules and multiscale and multiresolution rules on feature objects. Define the display rules: (1) define the display order. Such as first display polygon feature, then line feature, finally point feature, etc. (2) When the extend of graphics is smaller than the given extend, the graphics are not displayed. (3) Symbolization rules. (4) Map generalization rules. 4.4 Temporal object model Both GIS spatial data and attributive data have temporal characteristics. Without time stamping GIS data cannot be used efficiently. Stamping version information in a feature object is a good method. The typical data abstract technology of Objectoriented is classification, generalization, association, and aggregation. The characteristics of Objectoriented are that they have abstraction, inheritance, and polymorphism. We can use these characteristics to realize our goal [Alfons Kemper, 1994 and R. J. A. Buhr, 1996]. The typical relationship of objects or classes in Objectoriented model are 'is a' , 'part of' , 'member of' and 'instance of'. Also based on feature GIS Objectoriented model we can model the feature relationship, such as: is a ,a kind of, a instance of ,a member of , a part of , composed of, inflow from, outflow to, connected to, vertically related to, bounded by, bounds, within, contains etc; temporal relationship： before , after, at, between etc. The spatial data in the hypergraphbased ObjectOriented model can link an attributive class of hypergraph, such as, geometrical object links feature object model. This is a very important character for modeling GIS spatial phenomena. We can label hypergraph class according to the feature of class, such as road, road segment, the grade of road, etc. 5. Hypergrpah theory Hypergraph [ C. Berge,1989] are the theoretical basis of hypergraph spatial data model. Hypergraph expands the graph theory. In general graph, edge set is defined duality elements of vertex set. But in hypergraph, edge set is defined any of elements of vertex set and is closed by Jordan curve. Let X={x_{1}, x_{2}, …, x_{n}} be a finite set, and let =(E_{i} / iI) be a family of subsets of X. The family is said a hypergraph on X if E_{i } ( represents null set) and E_{i}=X, iI. The couple H=(X, ) is called a hypergraph. X=n is called the order of this hypergraph. The elements x_{1}, x_{2}, …, x_{n} are called the vertices and the sets E_{1}, E_{2}, …, E_{m} are called the edges. In a hypergraph, an edge E_{i} with E_{i}>2 is drawn as a curve encircling all the vertices of E_{i}. An edge E_{i} with E_{i}=2 is drawn as a curve connecting its two vertices. An edge E_{i }with E_{i}=1 is drawn as a loop in a graph. Two vertices are said to be adjacent if there is an edge E_{i }that contains both of these vertices. Two edges are said to be adjacent if their intersection is not empty. The incidence matrix of hypergraph H=(X, ) is a matrix ((a_{j}^{i })) with m rows that represent the edges of H and n columns that represent the vertices of H, such that a_{j}^{i}=1 if x_{j} E_{i} a_{j}^{i}=0 if x_{j} E_{i} Each (0,1)matrix is the incidence matrix of hypergraph if no row or column contains only zeros. E_{1} x4 x_{6} x_{1} E_{4} E_{3} x_{5} x_{2} E_{2} x_{3} E_{5} x_{7} Fig.2 A hypergraph with 7 vertices and 5 edges To each hypergraph H=(X; E_{1}, E_{2}, ..., E_{m}) there corresponds a hypergraph H*=(E;X_{1}, X_{2},..., X_{n}) whose vertices are points e_{1},e_{2},...,e_{m} ( that respectively represent E_{1}, E_{2}, ..., E_{m}) and whose edges are sets X_{1}, X_{2},..., X_{n} (that respectively represent x_{1}, x_{2}, ..., x_{n}) where, for all j, X_{j}={e_{i }/ im, E_{i} x_{j}}. Hypergraph H* is called the dual hypergraph of H.The incidence matrix of hypergraph H* is the transpose of the incidence matrix ((a_{i}^{j})) of hypergraph H. Hypergraph generates relevant concepts and algorithms, such as Ksection, transversal of a hypergraph, representative graph of a hypergraph. 5.1. Ksection of hypergraph Given an integer k>0, the Ksection of hypergraph H=(X, ) is defined to be the couple H_{k }=(X,_{k}), formed by X and the set: _{k} ={F / F X; 1Fk; F E_{i}, for some E_{i}} H_{k }is still a hypergraph. Its vertex set is X, but its edge set changes to not exceed number of k point. The 2section H_{2} of a hypergraph H is a graph with the same vertices as H and with a loop attached to each vertex. The 2section without loops is useful for GIS automatic generalization GIS spatial object. Fig3 is the 2section without loops of Fig.2 x_{1} E_{1} x4 E_{7} x_{6} E_{2} E_{4} x_{2 } E_{6} _{ } E_{3} x_{3 } x5 E_{5} x_{7} Fig.3 2section without loops of Fig.2 E_{8} 5.2 Transversal of hypergraph It defined as: For known H_{k }=(X,_{k}), Let TX, X is original vertex set of hypergraph. If T has TE_{i}(At least it include one point to each edge) to all im, here T is called the transversal of hypergraph. In fact, the transversal of hypergraph is part of vertex set. This represents a spatial transverse relation in GIS model. 5.3 Representative graph of hypergraph Let H=(E; X_{1}, X_{2}, ...,X_{n}), be a hypergraph with n edges. The representative graph H is defined to be the simple graph G=L(H) of order n whose vertices x_{1}, x_{2},... x_{n} respectively represent the edges X_{1}, X_{2}, ...,X_{n} of H and with vertices x_{i} and x_{j} joined by an edge if, and only if, X_{i} X_{j} . This new graph G is called representative graph of hypergraph H. The graph G represents the edge relationships of H. In GIS model, representative graph of hypergraph gives us good ability to analyze complex spatial relations. G=L(H) means that vertices x_{i} and x_{j }are adjacent if , and only if, there exists in H, a vertex e_{k}x_{i}x_{j}. This is also equivalent to saying that there exists an edge E_{k} in H* that contains both x_{i} and x_{j}, or to saying that G=(H*)_{2}. According to basic research we can get following conclusions. To analyze and simplify the basic relationships we can use Ksection and representative graph of hypergraph. Representative graph of hypergraph represent major dependent relationship between edges of hypergraph. Ksection make us analyzing the relationships hierarchically. The dual hypergraph algorithm is important for analyzing dependent relationships between the vertices and edges. That is if in hypergraph vertices represent spatial geometrical objects and attributes and edges represent the relationship between objects, then the hypergraph represents the objects and attributes of the relationship dependence and association. But the dual hypergrpah reverses these associations. It represents the relationships of objects and attributes of dependence and association. In whether or not display spatial object depending on constrain conditions we can fully utilize this dual hypergraph algorithm. 6. Applying Hypergraph Theory in HOOM No references introduced how to transform between hypergraph and HBDS or HOOM. Ostensibly, Hypergraph is different from HOOM in visualizing. But it is only different in vision. In Fig.2, if we take E_{3} as the root of HOOM, then in HOOM visualizing mode, Fig.2 can visualize as Fig.4 (Hypergraph edge as class of HOOM, vertices as member of class. Link relationship exists among vertices. Hypergraph E_{3} ^{x3} ^{x4} ^{x5} link relationship Hypergraph E_{2} Hypergraph E_{4} Hypergraph E_{5} ^{x1} Constrained Relationship between Vertices Hypergraph E_{1} Fig.4 The HOOM mode of Hypergraph Also we can take the vertices of hypergraph as the class of HOOM and edges as constrained relationship. Once we established the transformation relationship between hypergraph and HBDS or HOOM, we can use the algorithm of hypergraph simplify or analyze the feature relationship. We think it is important for GIS spatial calculation. 7. Attributed Hypergraph(AHG) The AHG is a representation which groups model components into hyperedges based on various structural or relational properties. The resulting model is flexible and can be easily modified. It can be used to facilitate the interpretation and the search procedures associated with knowledge synthesis^{[12]}. The AHG knowledge representation has several important advantages. While being a local representation, it handles various levels of relationships and abstractions. Definition 1: An attributed graph (AG) is a graph G_{a} = (V_{a};A_{a}) where V_{a} ={ v_{1}; …; v_{p};… ; v_{q};…; v_{m}} is an attributed vertex set and A_{a} = {…; a_{pq};…} is an attributed edge set. The edge apq connects vertices v_{p} and v_{q}. Directed edges are called arcs. Definition 2: An attributed hypergraph (AHG) H_{a} = (X_{a};E_{a}) consists of a set of attributed vertices X_{a} and a set of attributed hyperedges E_{a}. The attributes of the vertices are similar to those of attributed graphs. The attributes of a hyperedge are mappings from its set of vertices into a range which provides a description of the set. The range can be (i) an AG defined on the vertex set, (ii) a set of nominal or ordinal values or (iii) a geometrical configuration of that set. Definition 3: An edge in an attributed hypergraph is called an attributed hyperedge. The attributes of the hyperedge are mappings that maps the set of vertices of the hyperedge into a range which provides a description of the set. The range can be: (i) an attributed graph defined on the vertex set (ii) a set of nominal or ordinal values (iii) a geometrical configuration of the set or (iv) any other desirable representation. A AHG can be efficiently used to find a subgraph of all traversable regions. Fig5 to Fig.7 represents the traversable of DEM. This feature may not be represented in other models. The terrain features, such as, peak, pit, saddle etc. are very important for constructing the DEM. But when we use DEM, terrain feature relation, such as, traversable and connection are also important. We use AHG represent these relations.. 8.An example Here give an example of using hypergraph to describe the terrain feature. Fig.5 DEM and its Contour Map[Fayek and Wong,1996] Fig.6 Terrain Feature Fig.7 Hypergraph Representation of Terrain Feature 8. Conclusion and suggestion Using hypergraph model people can design many GIS application systems such as, Urban integrated information system, Decision support system of region sustainable development [Weihong CUI, 1995]; etc. But we didn’t pay enough attention to hypergraph theory. Hypergraph theory can be used in data organization of multiscale or multiresolutions. Because the lack of studying hypergraph theory, we only used the characteristics of ObjectOriented. Of course this is one of our primary studying direction next step. 9. Acknowledgements This paper is Funded By WKL(98)0301 Open Research Fund Program of LIESMARS and Shanxi Nature Science Foundation under the grant No. 991027. 10. Reference
