tx087车载GPS导航系统中地图匹配算法的研究
收藏
资源目录
压缩包内文档预览：(预览前20页/共23页)
编号：149922544
类型：共享资源
大小：245.38KB
格式：RAR
上传时间：2021-10-10
上传人：好资料QQ****51605
认证信息
个人认证
孙**（实名认证）
江苏
IP属地：江苏
20
积分
- 关 键 词：
-
tx087
车载
GPS
导航系统
地图
匹配
算法
研究
- 资源描述：
-
tx087车载GPS导航系统中地图匹配算法的研究,tx087,车载,GPS,导航系统,地图,匹配,算法,研究
- 内容简介：
-
Chapter 2: Fundamentals of 3D modeling and visualizationThis chapter presents of an overview of the basic concepts in data modeling, computer graphics and Web techniques, and aims to familiarize the reader with the fundamental concepts and principles used in the thesis and now widely agreed on throughout the GIS and CG society. The chapter can be divided into four sections. First, the chapter clarifies the term model, refines its components and discusses the design phases leading to a functional system. Second, the basic principles are discussed in a GIS context. Existing definitions, characteristics and spatial relationships of real objects are commented on. Common object-oriented principles are briefly reviewed in support of the object-oriented concepts used in several chapters of the thesis. Basic set theory and topology notations are mentioned as an introduction to the definition of the spatial model and spatial relationships in Chapter 5 and Chapter 6. The third part is devoted to Visualization techniques and aims to clarify the terminology, basic Visualization mechanism and components to create realistic scenes. This section provides the basis for Chapter 4 and Chapter 5. The last part discusses common methods to assess, visualize and interact with data on the Web. At the end, the design criteria of VRML and its role in the Visualization process are briefly discussed. The issues are closely related to the system architecture presented in Chapter 4 and the conceptual design given in Chapter 5.2.1 Models and modelingThe term model is one of the most frequently used words in many disciplines. Scientists build and prove hypotheses, make predictions, exchange ideas and gain knowledge on the basis of models. The model is extensively used to represent certain phenomena in a way readable for others. Hence, the meaning of the term, as well as the principles on which to build models, have to be understandable for everyone. Many different models exist about various aspects of the world. One categorisation of models can be made regarding the phenomenon to be described, i.e. real or imaginary. In the first case, some properties of the real object have to be selected (measured, investigated, observed) and utilised to create the model. In the second case, the properties have to be designed (planned, computed, decided) by the user and assembled to form the model. A clear boundary between the two models is sometimes difficult to establish. The deficiency of real measurements might be so high that human design is necessary to represent the phenomenon. In both cases, the process of model production is called modeling. Another categorisation of models addresses their form, i.e. digital and non-digital (e.g. paper maps). Although sometimes better understood by humans, non-digital models cannot be managed by computers. The benefit of using computers for modeling needs no explanation. Models that are intended to interpret the world in a certain way understandable to the computers are called data models (Vossen 1991). In general, data models are simpler than most of the scientific models.2.1.1 Objects, attributes, relationships, operationsA strict definition of a data model can be found in any book about databases. Here, we adopt the one presented in Tsichritzis and Lochovsky 1982. A data model denoted by M is a tool that provides an interpretation of the world and consist of generating rules denoted by G and operations denoted by O, i.e. M(G,O) (see Figure 2-1). The generating rules reflect two aspects of the model: 1) structure specifications (Gs) and 2) constraint specifications (Gc), i.e. G(Gs, Gc). Structure specifications establish the type and Organization of data, while constraint specifications impose any compulsory model limitations. For example, a real building might be represented in a model as a set of planar, rectangular faces (due to the structure specifications); however, the faces must intersect only along their boundaries (due to constraint specifications). The generating rules operate on data, which are commonly understood as a tuple of objects (categories), their properties and mutual relationships captured in a certain time moment.Figure 2-1: A model as an abstraction of realityThe operations describe all the actions that can be performed on the data as some data models allow standard languages for data manipulation to be established (e.g. SQL). Traditionally, five generic operations are distinguished: set currency (establish a logical position in the model representation), retrieve (make available some data to the user), insert (add new data), delete (remove data from the database) and update (change existing data). Common supporting operations are selection, navigation and specialisation. Selection is an operation that allows a number of data to be identified on the basis of three properties, i.e. logical position (first, last, prior), value of the content or relationship. For example, the user may want to see the first 10 (with respect to the identification number) buildings. Navigation is an operation that permits a logical path on the basis of a selection to be followed. Specialisation is a complex operation that allows a new object (category) to be created on the basis of existing ones. For example, the user may need to provoke the creation of a conglomerate called shopping centre of several existing buildings. In some spatial models, the operation will be completed by the Eulers operators for adding and removing elements from a spatial database, in such a way that the structure remains manifold (see Mntyl 1988). A typical example, which is related to the relational data model, is the creation of a new table on the basis of existing ones. The operation specialisation is then realised by the operations of set theory union, intersection and deletion. Indeed, the user of the model can define as many operations as needed for the specific application. The possibility for the model to provide users with different, independent subsets of data (called views) is considered an essential characteristic of certain classes of models. More details about views can be found in Vossen 1991. Many models have been developed of varying scope in terms of world representations and generating rules and operations. Some models handle very abstract notions (i.e. database models) and aim at accommodating any type of data; others are more application-oriented and operate with specific types of data (e.g. points, lines, faces in spatial data models). The apparent advantage of the common data models is that the structure and operations are independent of the application and hence the management system built around the model in practice serves any application. The application model is described according to the rules of the common model in a schema (see Figure 2-2). The term mapping is frequently used to describe this process, e.g. our application model is mapped onto the relational data model. Among the common models only three have become widely used and implemented, i.e. relational, network and hierarchical data models (see Date 1981, Martin 1977, Tsichritzis and Lochovsky 1982). The three models are products of the logical design (see Section 2.1.2) and are sometimes referred to as logical models. Since the relational data model is used later in the thesis, the basis principles of only this model are mentioned here (see Section 2.1.4). Figure 2-2: An abstraction of the world in a data model2.1.2 Design phases in modelingIn obtaining a model, three phases can be distinguished: conceptual, logical and physical (see Martin 1977, Tsichritzis and Lochovsky 1982, Vossen 1991). Although the phases refer all kinds of models, the terminology is established by research on models of common purpose. Therefore, exhaustive discussions on the design phases can be found in the literature for database management systems.Conceptual design clarifies which items have to be included in the model: types of objects, their characteristics and relationships. The resulting product of the conceptual design is a conceptual model or schema. The Organization of all the information that the user wants to store permanently on the disk, i.e. creating views of reality, seems to be a tedious task and requires appropriate abstractions and rules. The research on conceptual (semantic) models, which aims at providing tools to describe real phenomena, is quite extensive and has resulted in a number of more or less sophisticated models. One of the most popular, the Entity-Relationship (ER) model (see Chen 1976) operates with entities, which have attributes and relationships among them. An entity can be anything that has some meaning, e.g. a person, a building, a car, a process. Specific characteristics of entities such as names, colour, address, etc., are referred to as attributes. Since the entities are not isolated in the real worldinstead they interact or are associated with each otherthe notation about relationship is introduced. The relationship can be one-to-one, one-to-many, many-to-one, many-to-many or IS_A. The last relationship represents specialisation (to be discussed later in the text). These notations and the graphical representation called ER-diagram complete the ER-model. As it can be realised, the model does not support an aggregation mechanism; instead it offers an easy way to derive relational tables for the relational data model. The IFO conceptual model, based on an object oriented-approach and having notations for aggregation, is presented in Chapter 7. Logical design specifies the elements of the logical model, according to the schema obtained from the first stage. If the data model is a relational data model, the logical design clarifies the tables, columns per table and keys. The identification of the objects has to be ensured by introducing a unique ID. If ordering is needed, e.g. clockwise orientation of faces, it has to be indicated explicitly since the relational model inherits non-ordering properties from sets. Often the logical model is associated with the term data structure, since the structure (i.e. tables, tree or network) of the data is already established. Physical design is the last phase, establishing the way of communication with the hardware with respect to the logical model, i.e. set of files stored on the disk. The physical design has to enable the operations for manipulating the model. These three stages of design complete the design phase of the model, which is still not sufficient for a system to become managable. Yet, user interface for the interaction and manipulation of the model has to be provided to enable utilisation by the user. 2.1.3 Object-oriented principles The modeling process requires many assumptions, classifications, abstractions, selections, generalisations, etc., about real objects and their attributes to be performed. Among the variety of different principles, we concentrate on common object-oriented principles, since they are applied in several parts of the thesis. The object-oriented approach emerged in early 1970 when the first object programming languages (Simula, Smalltalk) were developed. Since that time, the approach has found applications in different areas of human science. The advantage of the approach is the problem-solving strategy encapsulating information, functions and behaviour per object. Thus any problem to be solved is approached from an object (e.g. person, building, street) perspective rather than from a function (what kind of functions does the system have to perform) or information (what kind of information has to be supplied) perspective. The approach is built on a number of principles that provide a mechanism to model real objects in more natural way. The common methods facilitate the organization of objects characteristics and their relationships with other objects. Objects and attributes: An object can be anything, i.e. person, action, process and the attributes represent all the characteristics. Methods, processes and functions denoting behaviour aim to represent the dynamics of objects. For example, an object can be a building with attributes colour and height. Its behaviour can be the ability to be created, edited, selected, etc. Wholes and parts: The method has at least three variants: assembly and parts, container and contents and group and members. The first relation represents the obvious link that exists in manufacturing parts. The door is a part of a car, the window is a part of a wall, etc. The second variant helps in cases when the things are not really designed for each other. A typical example is an office, which consists of a desk, a computer, a chair, and bookshelves. The third expression comprises relations that may appear in formations like faculties and courses, groups and subgroups. The members of a subgroup are considered members of the group as well. For example, the group of ITC students consists of the students of courses GFM, GIC, GIR, etc. The principle behind the whole-part method is aggregation. Each whole aggregates a given number of parts, i.e. the cardinality (object connection constraint) of relationships has to be indicated. The relationship is usually read from top to bottom, i.e. consist of. Classes and instances: Each object has to be organized in a class as the classes are formed with respect to common attributes and behaviour. Each object of a class is an instance of that class. For example, the ITC building is an instance of class Buildings in Enschede. The mechanism to form classes or specify new objects is known as generalisation-specialisation. The generalisation part is applied when a class has to build, i.e. the new class accepts (some of) common characteristics of objects and thus creates a more general view about a certain group of objects. The new class becomes their parent and the objects are its children. The children inherit the common properties from the class and contain only the ones specific to them. The specialisation part of the mechanism is used to create children. The number of classes and, respectively, children is not limited. Thus a hierarchy is built as the generalisation mechanism extends the hierarchy upwards and the specialisation mechanism downwards. In through contrast to wholes-parts, the classes-instances relation is read from bottom to top, i.e. is a. Abstraction is a principle considering the characteristics of an object that are important for the problem or application. Some details quite important for one application might be irrelevant for other. Abstraction is the first principle, which has to be thought for object identification. The characteristics of the objects can be clarified only after an accepted level of abstraction. Encapsulation is an object-oriented programming mechanism to combine an object characteristic and a corresponding behaviour. Furthermore, the particular software design unit (subroutine, method) could be hidden from the user. For example, a click with the mouse on a building (on a monitor) may visualise the owner of the building. The event click detected by the system activates the retrieval of a particular objects characteristic. In this example, the user action OnClick and the operation retrieve owner are encapsulated in one single method (behaviour). The encapsulation principle applied to the Organization of data can be understood as providing (or not) access to parts of the data and operations. Certain responsibilities can be assigned to parts of the information to restrict operations on data. For example, a common user of a municipality GIS may not be aware of actual geometric representation of a building and consequently not allowed to change the geometry. Inheritance is the mechanism to express similarities (common characteristics) between objects. As mentioned above, it is the basic mechanism for building classes and thus helps in propagating properties from parent to child. In general, all the attributes and behaviour of a parent are inherited by the children and grandchildren and so forth. The overriding and expending of parent attributes and behaviours is allowed as well. The case where a child has only one parent is known as single inheritance, while multiple parents invoke multiple inheritance. These supplementary techniques are useful for creating composite classes. Opponents of overriding and extending, and multiple inheritance say that the simplicity of the model is lost and that operation with overridden attributes is more complicated. An alternative is introduction of local and inherited properties. Polymorphism is the ability of objects to have different forms. For example, an object changing its geometry from very detailed to a simple cube is a morphing object. A bank transfer may settle a tax payment by filling out a form or by e-mail. All the operations are valid, therefore the tax payment is considered polymorphic. Polymorphism is a widely used mechanism to speed up real-time navigation inside 3D models. Each object or groups of objects have several geometric representations and the Visualization software decides which of them has to be used. Attributes of objects can be polymorphic as well. For example, an attribute document number can be associated with a parcel as a property document and a person as a document for ownership. Association is a mechanism to establish a connection between the objects in two classes. The relationship is not typical for the entire class and in this sense can not be resolved by aggregation. For example, class Building and Street can have a connection concerning the relation building on a street. This leads to the construction of a new class Building-on-Street. Either of the two classes Building and Street is a part of the new class, therefore no aggregation can be applied. However, the cardinality must be known. The similarity between the aggregation and association mechanisms is quite high and sometimes it is hard to decide which mechanism to apply. The basic rule is that aggregation is a class connection pattern, while association is object connection one. Several associations have become well known and used, and have their own name, i.e. participant-transaction, place-transaction, participant-place, transaction-transaction, peer-peer (object connection between objects in he same class). 2.1.4 Relational data model The relational data model based on relations and their representation as tables was introduced first by Codd (see Codd 1970). The basic category relation is defined as follows: R is a relation on given sets D1, D2,Dn if it is a set of n-tuples, each of which has its first element from D1, second element from D2 and so on. The sets D1, D2,Dn are called the domains of R. The number of the domains is the degree of the relation and the number of the tuples in R is its cardinality. A table represents each relation, and each column of a table is called attribute. One or more relations, then, can define an object type. Thus the database is specified by a relational schema, which consists of one or more relations R. Since the relational schema consists of separate tables, the relationships between the tables are established by a propagation of keys. The key can be composed by one or more attributes. Two constraints must be satisfied: the key must be unique and the key must be minimal. For example, the identification number (ID) of a building can be used as a key. Since representation by tables may easily lead to repetition of information, the optimisation of the model is critical. Normalisation is a procedure to eliminate different types of dependencies among the relations and attributes. Theoretically, five normal forms are defined, however, three of them are commonly considered sufficient (see Smith 1985). The basic concept that the relational data model misses is the existence of constraints on and among the relations. For example, it is impossible to specify that certain types of buildings (e.g. residential) cannot be higher than four floors. Among the many different languages for data definition and the manipulation of relational data models, the Structured Query Language (SQL) enjoys the greatest popularity. SQL is an English-keyword set-oriented language. The basic concept is that each operation is mapped onto the relation. The effect is similar to scanning the columns of a table and checking for a value or a set of values. For example, for the operation retrieval, all the rows of the table are scanned and the ones where the sought value is found are returned as results. The fundamental set of key words SELECTFROMWHERE allows a large number of mappings to be performed. Furthermore, several mappings can be combined to ensure the basic set operations union, intersection and difference. Attempts to extend SQL toward an ad hoc language for a GIS have been made without a significant success. Egenhofer 1992 argues that SQL cannot become a GIS language due to a number of impossible operations: identity queries, metadata queries, knowledge queries (explaining the reasoning), qualitative queries (e.g. which road is wider), display of query (the result is always a new table), modifying the database content from the graphics and modifying the graphical presentation. The inadequacy of SQL is currently overcome by utilising embedded SQL queries. The outcomes of SQL queries are further processed by operators written in standard programming languages (C, Pascal, Perl) called host languages. Despite all the deficiencies of the relational data model and thanks to the simple concepts and the standard query language, many commercial Database Management Systems (DBMS) have adopted the model that contributed to its successful integration in commercial and administrative applications. 2.2 GIS models Geo-science specialists are busy with the modeling of real phenomena. A universal model to comprise all the aspects of reality is not practically realisable due to the high complexity of the real world. Different disciplines emphasise different aspects and only these aspects are included in the model. Thus a model considered good for the description of particular phenomena might be hardly appropriate for anothers. Different aspects and characteristics of real objects have led to the existence of several variations in object definition. The term GIS model is utilised here to denote a data model of the real world. Being a data model for representing real-world objects, the GIS models have the components defined above, i.e. object types, relationships and attributes with corresponding generation rules, constraints and operations defined with them. A GIS model with the corresponding user interface constitutes a 3D GIS. Often the GIS content is specified as data about geometric (shape, size, location) and semantic characteristics (called attributes), spatial relationships and time (see Aronoff 1995, Maguire et al 1991, Molenaar 1998). The functionality of GIS is then said to be the possibility to perform operations on data in order to analyse them. The following sections present the necessary fundamental concepts related to the representation of objects, attributes and relationships in a GIS context. 2.2.1 Types of objects Since the interest in geo-sciences has traditionally been directed toward real objects with spatial extent, the differentiation between spatial and non-spatial objects is widely accepted. A spatial object stands for a real object having geometric and thematic (semantic) characteristics (see Aronoff 1995, Maguire 1991, Molenaar 1989, Pilouk 1996). Tempfli 1998c draws attention to a third group, i.e. radiometric characteristics of spatial objects. Current GIS models maintain only spatial objects. Non-spatial objects (Organizations, departments, people, goods, etc.) either are the concern of Database Management Systems (DBMS) or are integrated in GIS as semantic characteristics of spatial objects (see Chapter 3). For example, the person, who owns a building (spatial) exists in a GIS as a semantic characteristics owner of the building. As will be discussed in this thesis, dealing with only non-spatial objects may be a drawback for some applications. A further distinction is made between real objects with respect to distinctness of properties, i.e. objects with well defined spatial extent and properties and objects with unknown or non-well defined spatial extent and properties, i.e. objects with discernible (determined) and indiscernible (undetermined) boundaries (see Cheng 1999, Molenaar 1994, Raper 1998). Usually, quite independent research is conducted in both areas. This may cause problems in the case of analysis where objects from the two groups are needed. Pilouk 1996 discusses the subject in details and advocates an integrated approach while modeling spatial objects.Many real objects need the monitoring of some of their characteristics with respect to time. For example, growth of population may cause the fast conversion of land from rural to urban use, which can have an impact on the entire urban development. The geo-science specialist might need to store and analyse the changes in order to be able to predict and control the process. Similar problems have created the branch of temporal definitions of an object, according to which objects are subdivided into spatio-temporal and non-spatio-temporal (see Pequet 1995, Worboys 1992). Raza et al 1998 present spatio-temporal-attribute objects (STAO) with three fundamental components, i.e. location (spatial), attribute (aspatial) and time (temporal). Cheng 1999 defines a real object by its three aspects geometry, theme and time. More general definitions of real objects, regardless of the nature of the objects can be found in the object-oriented literature (see Coad and Yourdon 1991, Hudhes 1992, Norman 1996). Coad and Yourdon 1991 denote as an object every item of interest (real object, feature, process) and present a framework to investigate and classify the characteristics of the different objects. Since this framework is used as a starting point for the object definition introduced in this thesis, more details are presented in Chapter 5. 2.2.2 AttributesAttributes stand for the characteristics of real objects, which are important for the GIS model. The term attribute is frequently used to denote only semantic characteristics of objects (see Aronoff 1995, Goodchild 1987, Peuquet 1988). This thesis considers a wider meaning for attributes, i.e. they compile semantic, geometric and radiometric characteristics of objects. The geometric characteristics refer to position (and orientation), shape and size of real objects. The radiometric characteristics regard material, colour or reflectance. The semantic characteristics specify status, functionality, meaning, usage, etc., of the real objects. This thesis concentrates on geometric characteristics and therefore some basic principles for representing them will be mentioned. Some examples for the Organization of semantic properties are given in Molenaar 1998, Peng 1997, Pilouk 1996. The description of geometric characteristics requires a priori clarification of the abstraction of space, the dimension of space and objects, and the method for representation. Conventionally, two approaches to space abstraction are utilised in modeling processes, i.e. field-oriented and object-oriented (see Worboys 1995). The field-oriented approach assumes complete subdivision of the space into smaller, regular partitions, e.g. pixel. In the object-oriented, the space is empty and all the objects are places (embedded) in it, i.e. a lake in a 2D map. Both approaches have advantages and disadvantages and are appropriate for different applications. While the field-oriented approach better suits the representation of continuous phenomena, e.g. height fields, rainfalls, the object-oriented approach represents better discrete phenomena, e.g. buildings, roads. The dimension of space is defined in mathematics as the number n of a sequence of n -real numbers (a1, a2,an), called an ordered n-tuple. All the ordered tuples are called n-space and are denoted by Rn (see Anton 1994). The basic idea is using a tuple of points to define a position in the space, e.g. a pair of points (x and y co-ordinates in Euclidean space) define a position in a plane, i.e. 2D space. The real world is usually represented as a 2D or 3D space. Within the space, the objects have their own dimensionality, i.e. they can be represented by one of the following generic types: 0D (points), 1D (lines), 2D (surfaces) and 3D (bodies) objects. The decision as to the representation of real objects (i.e. point, line, surface or body), is highly influenced by the purpose of the model. The possible geometric representations are split into three large groups: i.e. raster, vector and constructive primitives. The building blocks(named constructive objects in this thesis) in the raster method are regular cells, e.g. pixels (in 2D space), voxels (in 3D space), which fill in the entire object. The representation is simple and easy to maintain, but produces a lot of data for storage, and the overall precision is low (see Aronof 1995). The vector method is based on irregular n-cells, where n=1,2,3 composed of points with co-ordinates. In contrast to the raster method, the cells represent the boundaries of the objects. The last representation, known as Constructive Solid Geometry (CSG), uses irregular 3-cells. An object is represented by a CSG-tree, which holds information about the CSG primitives and the operations gluing them (i.e. Boolean operations). The approach is widely implemented in the manufacturing industry. In general, the irregular cells describing the boundaries of the objects allow more precise descriptions of shapes and spatial relationships compared to the raster cells and CSG primitives. Moreover, the Visualization algorithms operate with the boundaries of objects, i.e. CSG and raster representations have to be further processed to determine the boundary. Therefore many applications give preference to the vector approach of description. This thesis is based on a vector representation too. The vector representations are often referred to as boundary representations (B-rep) or surface representations (see Mntyl 1988, Worboys 1995). A large number of spatial models are developed and implemented in GIS, CG and CAD systems based on irregular multidimensional cells. The names and construction rules of the cells in the different models usually vary. The simplest set of cells is the set of simplexes, i.e. 0-simplex (node), 1-simplex (arc), 2-simplex (triangle) and 3-simplex (tetrahedron). Composing simplexes, one can obtain more complex objects, i.e. simplicial complexes (see Egenhofer 1989, Moise 1977, Pilouk 1996). Most of the models allow 1,2,3-cells with an arbitrary shape that imposes some supplementary constraints, e.g. planarity of faces, convex shape. The names vertex (point), edge, face (polygon) and solid (polyhedron) are then used in the literature to denote 0,1,2,3-cell. Further details and a discussion on vector models and cell utilisation in 3D GIS are provided in Chapter 5. 2.2.3 Spatial relationshipsThe particularity of GIS compared with other information systems is the maintenance of spatial relationships, i.e. the connections or interrelations between real objects in the geometric domain. The aspects of the spatial relationships are currently under investigations, i.e. approaches to representation, naming and equivalence (see Egenhofer et al 1994, Egenhoher and Sharif 1998, Kainz et al 1993, Molenaar 1998). Three different approaches to encoding spatial relationships are discussed in the literature, i.e. metric, topology and order. The metric is a pure computational approach, based on the comparison of numerical values related to the location of the objects in the space (i.e. the Euclidean space). For example, the spatial relationship between a house and a parcel (e.g. inside, outside, to the south) can be clarified by a metric operation point-in-polygon performed for each point constituting the footprint of the building. Since the metric is built on the notion of the distance function (see the next section), which is dependent on the internal (finite) representation of numbers in the computers, the approach is computational expensive. The order establishes a preference based on the mathematical relation (strict order) or (partial order), which allows an Organization of objects similar to a tree. For example, if a building is inside a parcel, the spatial relationship is represented as building parcel. The applicability to representing spatial relationships is investigated by Kainz 1989 who argues that it has advantages in expressions of inside/outside relationships. Topology allows the encoding of spatial relationships based on the neighbourhoods of objects regardless of the distance between them. The main property of topology, i.e. the invariance under topological transformations (i.e. rotation, scaling and translation) makes it appropriate for computer maintenance of spatial relationships. The following section discusses some basic topological issues that the thesis utilises. 2.2.3.1 Set theory and topologySeveral popular definitions of topology can be found in the literature (see Viskers 1996), i.e. l rubber sheet geometry l a study of boundaries l an abstract study of open and closed sets l that try to exhibit its most valuable property. Topology has been introduced as a discipline of mathematics and the foundations are set theory and metric spaces. Prior to the mathematical definition of topology, we will introduce some basic notations from set theory and linear algebra. Set: A set is an aggregate of things, e.g. numbers, people, buildings, points. The things are elements of the set. Indexed sets: Consider setsand the set, where to each element corresponds a set AI, then I is called index and the setsare called indexed sets. Moreover such an indexed family of sets can be denoted by. Function: A function (or map) f from set A to set B, written, is a subset ofwith the properties: for each, there is somesuch that, written also as ifand, then. Ifandthen each function has corresponding induced functions (on sets)and (usually the same notation of functions is used for elements and sets). In general, when the function(on elements) is performed, then induced function is true butis not necessarily true. Whenis true, then f is onto B. One-one is the function, which obeys the rule:. Relation: A relation R on a set A is any subset of. Thus every function from A to A is a relation but not all relations have the properties of functions. If R is a relation on A and then the relationship between the two elements is denoted by. Historically, topology was introduced as an alternative to represent continuity of a space more general than the Euclidean space. The Euclidean n-space is defined as an n-space with operations of addition, scalar multiplication and Euclidean inner product (for complete definition see Anton 1994). On the basis of the inner product, a metric can be defined, e.g. length, distance, angle. The Euclidean space is used as a fundament by Frechet (in 1906) to introduce a metric space, denoted by, whereis the distance function. Ifis a metric space for eachthe following is true: , ifthen The functionis called the metric on M. Inside the metric space the open sets are defined to be: A set E in a metric spaceis open iff (if and only if) for eachthere is an e-diskabout x contained in E. The e-disk about x is also defined on the metric spaceforto be: . The e-disks and open sets can be used to define continuity of metric space without referring to the distance. Topology is the next step to deal with continuity without mentioning the distance (see Hausdorff 1914). Topology is derived from the metric space by using the open sets. The definition of a topology is then given as (see Willard 1970): A topology on a set X is a collection tof subsets of X called the open sets, satisfying: any union of elements of t belong to t any finite intersection of elements of tbelongs to t the empty set and X belong to t . Inside a topological space, the topological primitives, i.e. closure, interior and boundary of a set can be defined. If X is a topological space and, then: closure is the setis closed and interior is the set is open and boundary is the set which is a closed set. Closure, interior and boundary of a set have a number of important properties (the proof can be found in Willard 1970) i.e.: is closed in X iff is open in X iff The basic topological definition given above, however, is not convenient for particular use (e.g. representation of geometric properties) due to the regularity of open sets in the Euclidean space, i.e. each open set of one point has the same properties as any other set. Then it is wiser to investigate the space first around a point (or several points) and conclude that around other points it is the same. Thus the notation about a neighbourhood is introduced, i.e.: If X is a topological space and, a neighbourhood of x is a set U, which contains an open set containing x, i.e., whereis the interior of U. Chapter 5 utilises the properties to derive the topological primitives for geometric and constructive objects. Three more definitions that will be used in this thesis are listed below, i.e.: Connected space: A set X is disconnected iff there are disjoint non-empty open sets H and K in X such thatThen X is disconnected by H and K. If no such disconnection exists, X is connected. For example the Euclidean space IR n is a connected space. Connectivity is an important property of topological primitives and hence plays an important role in derivation of spatial relationships between objects (see Chapter 6 for more details). Homeomorphism: If X and Y are topological spaces, a function f from X to Y is a homeomorphism iff f is one-one, onto and continuous and f-1 is also continuous. In this case X and Y are homeomorphic. The homeomorphism ensures the invariance under transformations.第 2 章: 3D模型及可视化原则本章主要讲述了数据模型的基本概念，以及计算机图形和网络技术的概观, 目的是使读者熟悉基本的概念、应用和目前广泛应用在 GIS 和 CG 领域的原则。本章可分为四个部分。第一，本章澄清了术语模型, 简单说明了它的成份并且讨论此功能系统的设计阶段。第二，讨论了GIS 上下文中的基本原则。提出对实体的现存定义，特征和空间关系的看法。简要回顾了用于一些论文章节的支持面向对象概念的普通面向对象原则。提到了基本的集合论和拓扑符号，如对第 5 章和第 6 章的空间模型和空间关系定义的介绍。第三部份致力于可视化技术术语的阐明, 基础可视化机制和产生现实成分的现场研究。这部分是第 4 章和第 5 章的基础。最后一部份讨论了网络上的数据估定, 想象和相互影响的通常方法。最后，简要讨论了虚拟现实造型语言的设计标准和它在可视化过程所处角色。该论题讲述了第 4 章的系统体系结构和第 5 章的概念设计。2.1 模型和建模术语模型是许多学科最常用的模型之一。科学家在模型的基础上建立并且证实假定，产生预言，交换想法，增进知识。此模型广泛地应用于描绘确定现象，在某种程度上易读。因此，术语的意义及建模，每个人的理解都是一样的。许多不同的模型存在于关于世界不同的方面。模型的一个分类方法也就是关于现象真正的或想像的描述。在第一个情形中，实体的一些道具必须被选择 (标准的,调查过的,观察的) 并且建模。在第二个情形中，道具须被使用者设计 (计划了的,估算过的,确定的) 而且装配形成模型。在二个模型之间有时很难建立清楚的边界。由于缺乏真实有效的测量法，人类在设计中不得不将现象表现出来。在这两个情形中，模型生产的过程就是建模。 模型地址的另外一个分类方法是按他们的形式分, 也就是说分为数字的或非数字的（举例来说，如纸地图）。虽然人们更容易理解,但非数字模型不能够用计算机管理。使用计算机建模的好处不需要再解释了。用计算机理解的某种方法解释世界叫做数据模型 (Vossen 1991)。大体上，数据模型比大部份科学模型更简单。2.1.1 对象，属性，关系，操作数据模型在任何书上都没有精确的定义。在这里，我们采用的是 Tsichritzis 和 Lochovsky 于1982 提出的介绍。一个被 M 表示的数据模型是一个对世界的解释，而且由产生被 G 和O 指示的操作指示的规则所组成的工具,也就是M(G,O)。(见图 2-1)这个产生规则反映模型的二个方面: 1) 结构规范 (Gs) 2)约束规范 (Gc),即 G(Gs, Gc)。结构规范建立数据的类型和组织, 而约束规范利用任何的必须限制模型。举例来说，一座真正的建筑物可能由一组平面, 矩形面 (由于结构规范)的模型来表示 ；然而，其外观一定顺着她们的边界相交。 (预定约束规范)产生规则被普遍认为是种类的数据操作，他们的道具和相互关系在特定的时间内被捕获。图 2-1:由实体提取模型提取一般性的特征等等模 型G：对象属性关系O：操作真 实 世 界视图1视图2视图3这项操作在数据上描述所有的动作，像一些数据模型允许标准语言确定数据处理,(举例来说 SQL)。从传统意义上说，五类操作要被区别开来:设定流通 (建立样板表现合理的位置) ，取回 (为用户制造可利用的数据), 插入物 ( 增加新的数据), 删除 ( 从数据库删除数据) 和更新( 变化现有的数据) 。通常支持的操作是选择，领航和专门化。选择是允许许多的数据以三个道具为基础被识别的操作,即合理的位置 (第一,最后,优先的)内容或关系的价值。举例来说，使用者想看第一个 10(有关于确认数字)的 建筑物。领航是以选择为基础跟随的一条合理的路径操作。专门化是允许在现有的基础上产生一个新的对象 (种类)的合成操作。举例来说，使用者可能激发一些现有建筑物被称为 购物中心 的集成物的创造。在一些空间的模型中，将元素从一个空间数据库移开的 Eulers 操作员来完善操作, 用这样的方法使结构残余复印本中 (见 Mntyl 1988)。典型的例子是关系数据模型的表述，即在现有的基础上创建新的表格。专门化操作是集合论，交集和删除的操作。的确，模型的使用者像许多操作一样定义细节应用。提供给用户的不同的独立的数据子集（称为视图）模型的可能性被认为是某种特定种类模型的本质特征。视图的很多细节可在 Vossen 1991 中找到。 根据世界表示、产生规则和操作的变化范围，发展了许多模型。一些模型处理非常抽象的概念 (即数据库模型)，它们的目标是适用于任何类型的数据； 其它模型面向应用程序，适用于精确类型的数据操作(举例来说点,线,面向空间的数据模型)。普通数据模型的明显优势是应用程序在结构和操作上独立，因此系统管理建立在实践服务应用程序的模型之上。应用模型依照普通模型在计划上的规则来描述。 (见图 2-2)术语映射常用来描述这个过程,举例来说 我们的应用模型被映射在关系数据模型之上 。在通常的模型之中只有三个已得到广泛应用并且被实现，即关系模型， 网络和分层数据模型(见Date 1981 ，Martin 1977 ， Tsichritzis 和 Lochovsky 1982)这三个模型是合理的设计 (见第 2.1.2 节) 产品，有时被称为逻辑模型。关系数据模型应用于稍后的论题，这里提到的只是这个模型的基本原则 (见第 2.1.4 节) 。图 2-2: 用数据模型抽象世界真 实 世 界提取一般特性篇1篇2篇3数 据模 型G：对象属性关系O：操作视图1视图2视图32.1.2 设计模型的阶段获得一个模型，可分为三个阶段: 概念上的，逻辑上的和实际的 (见Martin 1977 ， Tsichritzis 和 Lochovsky 1982 ， Vossen 1991)。虽然这些阶段涉及所有类型的模型，但研究模型的共同目的是确定的。 因此，关于设计阶段的详细讨论在数据库管理系统的文献中讲述。概念设计阐明了哪些项目必须被包含在模型中: 物体的类型,他们的特性和关系。概念设计产生的是一个概念上的模型或轮廓。用户希望长期储存在磁盘片上的所有信息的组织,即创造真实的视图,这是一件沉闷的工作而且需要适当的抽象化和规则。提供工具以描述真实现象的在概念(与语意有关的) 模型上的研究相当广泛并且已经造成许多的或多或少复杂的模型。最流行的模型之一,实体- 关系 (ER) 模型 (见 chen 1976) 由于实体操作,有在他们之中的属性和关系。一个实体可能是有某种意义的任何事,举例来说一个人,一栋建筑物,一辆汽车,一个程序。实体的特性,像是名字,颜色,住址,等等,被称为属性。实体在现实世界没被孤立（改为彼此之间互相作用互相影响）提出了关系的符号。关系可能是一对一,一对多，多对一，多对多或 IS_A。最后关系表现为专门化( 在本文中稍后讨论) 。这些记号和被称为 ER- 图的图形表示法完善了 ER-模型。模型不支持集合机制；但它提供一个简易的方法为关系数据模型提供关系表。 IFO 概念模型,基于面向对象的方法及集合持有的符号，在第 7 章中讨论。逻辑设计详细说明了逻辑模型的原理,依照轮廓从第一个阶段获得。如果数据模型是关系数据模型,那么逻辑设计则阐明了表格、每个表格专栏及其关键。对象的确认必须保证其有一个唯一身份证明。如果排序是必须的,举例来说地形的顺时针方向的定位，它必须明确地指出在关系模型继承之后非排序的趋势。通常逻辑模型和术语数据结构相关联, 自结构以后 (即表格，树或网络)数据已经建立。 物理设计是最后阶段,主要是建立硬件与逻辑模型方式的沟通,即设定文件在磁盘上的存储。物理设计必须使操作模型能够操作。 设计的这三个阶段完成模型的设计时期,但仍不是整个系统的完整时期。然而,用于交互作用和模型处理的用户接口必须有利于用户的使用。 2.1.3 面向对象原则 模型的加工过程需要许多假定，分类，提取，选择，归纳，等等。运行实体及其属性，在不同的多样性原则之中，我们专注于普通面向对象原则,应用于论题的几个使用部分。 面向对象方式形成于 1970初期，第一个对象设计语言(Simula,Smalltalk)发展的时候。从那时开始，这种方式就在人类科学的不同领域建立了应用软件。这种方式的优点是解决问题策略压缩到每个对象的数据，功能和行为。因而解决任何问题应从一个对象入手(举例来说人，建筑物,街道)， 胜于从功能(“系统必须执行的功能”) 或数据 (“必须被提供的信息”) 观点入手。这种方式建立在许多提供以更自然的方式模仿实体的机制的原则之上。这种普通的方法使对象的特征和他们同其他对象的关系的组织更便利。 对象和属性: 一个对象可以是任何事,即人，行动，程序和属性表现所有的特性。方法，程序和功能用以表现物体动力学。举例来说，一个对象可以是一幢有属性颜色和高度的建筑物。它的行为可能是创建,编辑,选择,及其他能力。 整体和部份: 这种方法至少有三个变量: “集合和部份”， “容器和内容” 和 “团体和成员”。第一个关系表现在制造部份存在明显关联。门是汽车的一部份,窗户是墙壁的一部份，等等。第二个变量有助于当 “事物” 不为彼此为真的设计的时候。一个典型的例子是一个办公室,由一张书桌,一部计算机，一张椅子和书架组成。第三个的表达包含关系以像全体教员和课程，团体和子群一样的形成方面出现。子群的成员也是团体的考虑过的成员。举例来说，步兵训练中心学生由修课程 GFM ， GIC ， GIR 等的学生所组成。在整体- 部份方法之后的原则是集合。必须指出每个整体集合给定部分的数量,即关系的基数 (对象关系限制)。这种关系通常完全被读,也就是由其组成。 类和实例:当类被有关于共同属性和行为形成的时候，必须在一类里组织每个对象。一类的每个物体是那类的一个实例。举例来说，ITC 建筑物是 Enschede 类建筑物的一个实例。要形成类或叙述新的对象机制被认为是一般化-专门化。当一个类必须建立的时候，一般化部份被应用,即新的类“接受” （某一个）物体的共同特性并且由此产生更全面的视图。新的类成为他们的父母，而对象是它的孩子。孩子继承类的共同属性并且只包含一些特性。机制的专门化部份用来产生孩子。如此建造一个层次，如向上扩充一般化机制，向下扩充专门化机制。经过整体-部份, 类- 实例和完全被读关系形成对比。抽象性是考虑重要问题或者应用的对象特性的原则。对一个应用来说一些细节很重要，尽管跟其他的可能不相关。抽象化是第一项原则,必须为对象确认。对象的特性阐明可能只在抽象化的公认水平后。封装性是联合某个对象特性和某个对应行为的面向对象设计机制。此外，特殊软件设计单位 (子程序,方法) 可能对用户隐藏。举例来说，通过点击鼠标（在监视器）可使建筑物的业主显现出来。被系统发现的“点击”事件 刺激特殊对象特性的恢复。在这一个例子中, 使用者行动 “点击鼠标” 和操作 “取回拥有者” 在一个单一方法（行为）中被封装.数据组织的实用封装原则提供部分数据和操作的存取。它的职责是限制部分数据操作。举例来说，一个自治市的普通用户不可能知道一幢建筑物的真实几何学表示，而且他也没有改变几何学的权限。继承性是描述在物体之间的类似 (共同特性) 的机制。依照上面提到的，它是建筑物的基本机制类并且在从父母到孩子繁殖财产方面十分有益。大体上，父母的所有属性和行为被孩子和孙子等等遗传。双亲的花费和也是最重要的。一个孩子只有一个双亲的情形是即是单一遗传,当多重的双亲调用多样的遗传时候。这些辅助技术对创造合成类是很有用的。最重要的和扩充的反面,多重继承性假定单一模型最重要的属性是很复杂的。选择性是介绍局部的而且继承财产。多样性是有不同的表格的对象能力。举例来说, 从非常详细的简单立方体变化它的几何学的对象是一个变体对象。移动银行可以通过电子邮件外部供应支付税款。所有的操作是有效的,因此税款支付被认为是多种形式的。多样性是在三维立体模型之内加快即时航行一个广泛应用机制。每个对象或群体的物体有一些几何学的表现，而且可视化软件决定他们必须被使用。物体的属性也可能是多种形式的。举例来说，一个属性文件数字可以由文件所有权和文件所有者相关联。联合性是建立在两个类之间的对象间的连接机制。这种关系对整个类和集合解决不了的这个意义上是不典型的。举例来说,类建筑和街道有一个关于关系 “街上的建筑”连接 。这样就产生了一个新的类建筑-街道。两个类建筑和街道的任何一个都是新类一部份,因此没有集合可以被应用。然而，基数一定是知道的。集合和联合机制之间的类似相当高而且有时决定应用哪一机制是难的。基本的规则是集合是一个班级连接式样,而联合是物体连接的时候。一些联合性已经变得广为人知的并且已使用过, 而且有他们自己的名字,也就是叁加者-交易，地方-交易，叁加者-地方，交易-交易，同僚-同僚(在相同类对象之间的对象关系) 。2.1.4关系数据模型 基于关系和他们表示的关系数据模型如表格是Codd 第一个介绍的(见Codd 1970) 。基本类关系的定义如下: 如果它是一组 n-tuples,R 是在给定规定 D1 ， D2 ，,Dn上的关系，每个有来自 D1第一种元素,来自 D2 的第二个元素，依次类推。组合 D1 ， D2,Dn 叫做 R 的域。域的数字是 R 的关系的度而 tuples 的数字是它的基数。一个表格表示每个关系，一个表格的每列叫做属性。一个或多个的关系,能定义一个对象的类型。因而数据库由一或较多的关系 R 所组成关系的轮廓叙述。独立的表格组成相关的计划，而关系在由关键制定的表格之间。关键可能由一个或多个属性组成。必须满足二个限制: 关键一定是独特的，而一定是最小的。举例来说，建筑物的确认数字 (身份证) 可能被当作一支钥匙使用。既然表格的表示极易导致数据的重复，因次模型的最佳化是最重要的。标准化是除去在关系和属性之中的不同类型的一个程序。理论上，定义了五种正常的表格, 他们中的三个被普遍认为充份的(见Smith 1985) 。关系数据模型遗漏的基本概念是关系的限制。举例来说,详细说明某类建筑物是不可能的 (如住宅)不能比四楼更高。在许多不同的语言之中，处理数据定义和关系数据模型最流行的语言是结构化处理语言 (SQL)。SQL 是一种面向英语的- 关键字组合的语言。基本的概念是每个操作映射在关系之上。效果与扫描表格的列以及检查一类属性的价值类似。举例来说，为恢复操作表格的所有排被扫描，需要寻找返回的价值。关键字组合的基本原理是SELECTFROMWHERE，它允许很多的映射被运行。此外，一些映射可以被基本的操作、交叉点和差别合并。尝试向一种特别语言的扩充 SQL 是因为 地理信息系统已经成功。Egenhofer 1992 SQL 不可能成为地理信息系统语言是由一部分不可能的操作决定的：一致性、元数据、 知识（解释推理）及性质上的疑问 (如哪一道路是比较宽的), 还有显示上的疑问 (结果总是一张新表格),它修正图形数据库内容及图形介绍。当前SQL 的缺点利用深层SQL询问语句来克服。SQL 查询的结果由标准设计语言（C, Pascal, Perl）的操作员进行深加工称为主机语言。尽管所有的关系数据模型缺乏简单概念和标准查询语言，许多商业数据库管理系统 (DBMS) 已经采用有助于成功综合商业和管理的应用软件模型。 2.2 GIS 模型 地理科学专家忙于寻找真正的现象模型。由于真实世界的高度复杂，要找出包含实体的所有方面的通用模型是不现实的。不同的学科强调不同的方面，而且只有这些方面包含在模型中。因此一个描述了特殊现象的模型对其他现象几乎不适用。实体的不同方面和特性已经导致了对象定义上的许多变化。术语 GIS 模型是在这里是利用数据模型表示真实世界。表现实体对象的数据模型,GIS 模型有上
- 温馨提示:
1: 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
2: 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
3.本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
人人文库网所有资源均是用户自行上传分享，仅供网友学习交流，未经上传用户书面授权，请勿作他用。
川公网安备: 51019002004831号