MODELING THE TOPOLOGICAL RELATIONSHIP OF SPATIAL OBJECTS USING EGENHOFER MATRICES

ABSTRACT

The analytical needs in geographic information systems (GIS) have led to the interpretation of formal methods of modeling the topological relationship of spatial objects using Egenhofer-matrices. As a result, we investigate the algebraic approach for the structural analysis of a spatial topology- Simplices, The Order of Simplices, Faces of Simplices, Simplicial Complex, Skeletons of  Simplicial Complex. Oriented Simplex, Connectedness of Spatial Objects. The matrix interpretation of the eight spatial topological relations matrices of two Egenhofer 4-intersection models and that of the two Egenhofer 9-intersection models using matrix addition and multiplication modulo 2.  We  also  developed  the  8-intersection  and  The  2×4  Matrix  Representation  of Topological Relations of Three Objects A, B and C. 16- intersection models and  The 2×8 Matrix Representation Of Topological Relations Of Four Objects A, B, C And D. using the Egenhofer‟s 4 and 9- Intersections Models.

CHAPTER ONE

1.0       INTRODUCTION

1.1       Background to the Study

This work was motivated by the analytical need for a formal understanding of modeling the topological relationship of spatial objects using Egenhofer-matrices within the realm of geographic information systems. To display, process or analyze spatial information, users  select  data  from  a  Geographic  Information  System  (GIS)  by  asking  queries. Almost any GIS query is based on spatial concepts. Many queries explicitly incorporate spatial relations to describe constraints about spatial objects to be analyzed or displayed. The lack of comprehensive theory of spatial relations has been a major impediment to any GIS implementation. The development of a theory of spatial relations is expected to provide answers to the following questions (Abler, 1987):

(i)         What are the fundamental geometric properties of geographic objects needed to describe their relations?

(ii)        How can these relations be defined formally in terms of fundamental geometric properties?

(iii)      What is a minimal set of spatial relations?

In addition to the purely mathematical aspects, cognitive, linguistic and psychological considerations must also be included if a theory about spatial relations applicable to the real world problems is to be developed (Talmy, 1983 and Herskovits,1986). Within the scope of this thesis, only the formal, mathematical concepts which have been partially provided from point-set topology will be considered.

The variety of spatial relations can be grouped into three different categories as follows:

(i)        Topological relations which are invariant under topological transformations of the reference objects (Egenhofer, 1989; Egenhofe and Herring, 1990)

(ii)        Metric  relations  in  terms  of  distances  and  directions,  (Peuquet  and  Ci- Xiang,1986) and

(iii)       Relations concerning the partial and total order of spatial objects (Kainz ,1990) as described by prepositions such as in front of, behind, above and below(Freeman 1975; Chang et al., 1989; Hernamdez, 1991)Within the scope of this study, only topological spatial relations are discussed.

1.1.2    Object and object identity

Formally, an object can be defined as an identifiable entity that has a precise role for an application  domain    (Roy  and  Clement,  1994;  Blaha  and  Premerlani,  1998).  To constitute an entity, something must be identifiable (have identity), relevant (be of interest to the application domain) and describable (have characteristics) (Chen, 1976); cited in (Mattos et al,  1993). By means of the modeling process, each entity relevant to an application domain is represented by a corresponding object in the data model. The object in the model should have properties that describe the characteristics of the corresponding entity in the universe of discussion.

In an object-oriented system, each object is unique. This uniqueness of an object is achieved by means of the object identity. Object identity is that property of an object that uniquely distinguishes it from all other objects (Khoshafian and Abnous, 1995). By introducing a unique identity for each object, different objects can be distinguished from each other without the need to compare their attributes and behavior (Ellmer, 1993). The object identity is usually system generated, unique to that object and invariant for the object lifetime (Cooper, 1997).

1.1.3    Spatial relationships

Spatial relationships describe the relationships between spatial objects and geometric elements (Raza, 2001). In spatial databases, spatial relationships are needed for two main purposes as follows:

(a) For performing spatial queries: Queries in spatial databases or GIS are often based on the relationships among spatial objects. For example, “Retrieve all parcels that are adjacent to parcel A”. Such queries involve spatial conditions which standard query definition languages like Standard Query Language (SQL) do not adequately support.  Spatial  relationships  are  needed  at  both  the  query  formulation  and processing levels (Clementini et al, 1993).

(b) For enforcing consistency of the database. Spatial relationships are also used to formulate consistency constraints in spatial databases. For example, a violation of the constraint that two parcels should not overlap in a cadastral database can be detected by checking the spatial relationship that exists between the two parcels (Kufoniyi et al.,1994). The spatial relationships provide the means for defining and monitoring these constraints in the database. Hence the formalization of the basic spatial relationships is an essential component in GIS development.

1.1.4    Topological relationships

Topology is that branch of mathematics that studies the characteristics of geometry that remain  invariant  under  certain  transformations  (topological  mapping  or homeomorphism) (Kainz,  1995).  A topological  property is  that  which  is  preserved under topological transformations such as scaling, translation and rotation. Examples of topological properties are connectivity, adjacency and so on. There are two general branches of topology, both of which are applied in spatial data handling   (Kainz and Worboys1995).

These are:

(a) Point-set (or analytic) topology: This focuses on set of points and is based on real analysis, using concepts such as open sets, neighborhood and convergence.

(b) Algebraic (or combinatorial) topology: This uses algebraic means to describe the spatial relationships and is based on such concepts as simplified and cell complex and graph theory.

The point-set approach is the most general model for topological relationships (Raza, 2001). Using the point-set approach, topological relationships are defined in terms of three  fundamental  primitives  of  object  parts,  which  are  interior  denoted  as  (   ), boundary denoted as and exterior or closure denoted as (-), which themselves are defined based on neighborhood concepts (Egenhofer and Herring,1991). Topological models include:

(i)        The 4-Intersection model.

(ii)       The 9-Intersection model.

(iii)      The dimension extended model.

1.2    Significance of the Study

The significance of this study, modeling the topological relationship between spatial objects using Egenhofer-matrices, cannot be over emphasized due to it applications in the following important areas of the real world:

(a)   Natural resource-based like:

(i)        Management  of  areas:  agricultural  lands,  forest,  recreation  resources, wildlife habitat analysis, migration routes planning.

(ii)       Environmental impact analysis.

(iii)      Toxic facility sitting.

(iv)      Groundwater modeling. (b)  Land parcel-based like:

(i)        Zoning, subdivision plan review.

(ii)       Environmental impact statements.

(iii)      Water quality management.

(iv)      Facility management electricity, gaze, clean water, used water and so on.

1.3    Scope and limitation of the Study

The essence of this research is to analytically investigate the topological relationship between spatial objects using Egenhofer-matrices. The study is however, limited to mathematical modeling, sets and matrices.

1.4    Aim and Objectives of the Study

The aim of this study is to analytically model the topological relationship between spatial objects using Egenhofer-matrices.

The objectives of this study are to understand and apply;

(i)        The algebraic approach for structural analysis of a spatial topology.

(ii)        The  matrix  interpretation  of  the  spatial  topological  relations  of  two Egenhofer 4-Intersection models using matrix addition and multiplication modulo 2.

(iii)       The  matrix  interpretation  of  the  spatial  topological  relations  of  two Egenhofer. 9-Intersection models using matrix addition and multiplication modulo 2 .

(iv)       Derivation of the 8-intersection and the 16-intersection models and their corresponding eight spatial topological relations using Egenhofer matrices.

1.5.1    Geometry

This  is  a  branch  of  mathematics  concerned  with  questions  of  shape,  size,  relative position of Figs, and the properties of space. A mathematician who works in the field of geometry is called a Geometer (Encyclopedia of Science Clarified, 2013).

1.5.2    Spatial

This is related to space and the position, size, shape etc of things in it, (Encyclopedia of Science Clarified, 2013).

1.5.3          Topological Constraints: These are constraints that satisfy topological conditions. Constraint is a thing that limits or restricts something, (Encyclopedia of science clarified, 2013).

1.5.4      Sets

Cantor (1895) defined a set as any collection M of certain distinct objects of our thought or intuition (called elements of M) into a whole. It is a collection of objects, called the elements or member of the set. The objects could be anything (planets, squirrel, characters in Shakespeare‟s play, or others) but for us they will be mathematical objects such as numbers, or sets of numbers. We write x  X if x is an element of the set X and x  X if x is not an element of X. Sets are determined entirely by their elements. Thus the sets X, Y are equal written X = Y, if x  X if and only if x  Y. An empty set (   ) is a set without an element. If X , meaning that X has atleast one element, then we say that X is non-empty.

1.5.5       Set operations

The intersection A   B of two sets, A, B is the set of all elements that belong to both A and B; that is x  A  B if and only if x  A and x  B. Two sets A, B are said to be disjoint if A  B =   ; that is, if A and B have no elements in common.

The union A    B is the set of all elements that belong to A or B; that is x  B if and only if x  A or x  B.

Note that we always use “or” in an inclusive sense, so that x  B if x is an element of A or B, or both A and B.

The difference of two sets A and B is the set of elements of B that do not belong to A, that is B \ A x B : x A.

1.5.6   Relations

According to (Science Encyclopedia Clarified, 2013), a binary relation R on set X and Y is a definite relation between elements of X and elements of Y. We write xRy if x  X and y  Y are related. One can also define relations on more than two sets but we shall consider only binary relations and refer to them simply as relations. If X = Y then we call R a relation on X. The set of all x-values is called the domain and the set of all y-values is called the range. Relations could be the following:

(a) Equivalence  relations:  The  equivalence  relation  is  a  binary  relation  that  is reflexive, symmetric and transitive. For example, for any objects a, b and ca = a (reflexive property), if a = b then b = a (symmetric property) and if a = b and b = c then a = c (transitive property).

(b) Transitive relations: A relation in a set A is called transitive if and only if (a,b) R and (b,c)    R then (a,c)    R for all a, b, c   A.

(c) Void relations: A relation R in a set A is called void relation or empty relation, if no element of set A is related to any element of A. Hence R =    which is a subset of A x A.

(d) Symmetric relations: A relation R in set A is said to be symmetric if and only if aRb implies bRa for all a,b    A.

(e) Identity relations: For a given set A, I = {(a,a), a     A} is called the identity relation in A. In identity relation every element of A is related to itself only.

(f)  Reflexive relations: A relation is said to be reflexive if and only if aRa, for all a

A. It means every element of A is related to itself.

1.5.7   Matrices

(Kreyszig, 2004) defines a matrix (plural: matrices) as a rectangular array of numbers, symbols or expressions, arranged in rows and columns enclosed in brackets: There are m rows which are horizontal and the n columns are vertical. Each element of a matrix is often denoted by a variable with two subscripts. For example, a2,1 represents the element at the second row and first column of a matrix A. In mathematics a matrix is a rectangular array of numbers, symbols or expressions, arranged in rows and columns. The size of a matrix is defined by the number of rows and columns. A matrix with m rows and n columns is called m x n matrix or m by n matrix, while m and n are called its dimensions.

1.5.8         Mathematical modelling

(Bellomo et al, 1995),  defines mathematical modeling as the process of using various mathematical structures such as graphs, equations and diagrams to represent real world situations. The process of developing a mathematical model is termed mathematical modeling. A mathematical model may help to study the effects of different components and to make a prediction about a behavior.

1.5.9        Simplex

According to (Giblin 1977), a simplex is a minimal object that exists for each dimension in the spatial dimensions in which spatial objects are classified.

1.5.10        Simplicial Complex

A simplicial complex is a finite collection of simplices and their faces. Simplices is the plural of simplex.

₦8,000.00 – DOWNLOAD FULL PROJECT DOWNLOAD FULL PROJECT Added to cart

---

---

---

---

Related Project Topics :