期刊名称：ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences
印刷版ISSN：2194-9042
电子版ISSN：2194-9050
出版年度：2002
卷号：XXXIV Part 4
出版社：Copernicus Publications
摘要：To efficiently store and analyse spatial data at a global scale, the digital expression of the Earth's data must be global, continuous and conjugate, i.e., a spherical dynamic data model is needed. The Voronoi data structure is the only published attempt and only solution (which is currently available) for dynamic GIS. The complexity of the Voronoi algorithms for line and area data sets in a vector-based context limits its application in dynamic GISs. As yet, there is no raster-based Voronoi algorithm for objects (including points, arcs and regions). To overcome this deficiency, an algorithm for generating a spherical Voronoi diagram, that is a Voronoi diagram on a spherical surface, is presented based on O-QTM (Octahedral Quaternary Triangular Mesh). The basic idea is to apply the dilation operation developed in mathematical morphology to objects on the sphere in an effort to produce the effect of distance transformation. The distance contours of objects will form the Voronoi boundaries of the spherical objects. The algorithm presented in this paper can handle point, line and area objects. Additionally, it has been tested and concluded that the processing time required for this algorithm with point, arc and region data is proportional to the levels of complexity of the spherical surface tessellation. The difference (error) between the great circle distance and the QTM cells distance is related to the spherical distance
关键词：O-QTM; neighbour triangular; Voronoi diagram on sphere; recursive ; dilation ; Symposium on Geospatial Theory; Processing and Applications; ; Symposium sur la théorie; les traitements et les applications des données Géospatiales; Ottawa 2002 ; var currentpos;timer; function initialize() { timer=setInterval("scrollwindow()";10);} function sc(){clearInterval(timer); }function scrollwindow() { currentpos=document.body.scrollTop; window.scroll(0;++currentpos); if (currentpos != document.body.scrollTop) sc();} document.onmousedown=scdocument.ondblclick=initialize 1 Introduction ; It is been argued b y Li et al (1999) that the Voronoi data structure is the only ; possible solution (which is currently available) for dynamic GISs. This view is ; also similar to that suggested by Wright and Goodchild (1997); who point out that ; the Voronoi methods are the only published attempts of which we are aware that ; are well suited to achieving a dynamic GIS. This is because Voronoi diagrams ; (VD) have many excellent properties in spatial analysis (Gold 1992; Edwards ; 1993); dynamic operation (e.g. to add or delete objects without destroying the ; bubble structure of the cells) (Gold and Condal 1995; Gold and Mostafavi 2000); ; and co mputational geometry (Aurenhammer 1991; Okabe et al. 2000); etc. ; So far; the Voronoi diagram on a spherical surface has been applied to some ; areas; such as global spatial indexing (Lukatela 1987; 2000); interpolation on a ; sphere (Watson 1988;1998) and dynamic operations (Gold 1997; Gold and ; Mostafavi 2000); etc. For example; Lukatela (1987) sets up a digital geo- ; positioning model and develops an operational software package that provides ; geometrical and geo-relational functions to applications that manipulate spatial ; objects. A Voronoi tessellation is used as a base for a highly efficient indexing ; system to increase the speed of data manipulation (Lukatela 1987) (Fig. 1a). ; Watson (1988;1998) develops the MODEMAP system and uses a point-set ; Voronoi diagram for interpolation on a spherical surface (Fig. 1b). Gold and ; Mostafavi (2000) attempt to develop a global dynamic data structure with the ; Voronoi diagram. In this type of structure; the Voronoi diagram is a basic data ; model that dynamically maintains spatial relationships. ; ; ; (a) ; (b) ; Fig. 1. The Voronoi diagram of spherical objects; (a) as a spatial index (Lukatela 1987); ; and (b) for interpolation (Watson 1989) ; It is evident that the Voronoi diagram is a spatial data structure; which has ; become increasingly important. Considerable efforts have been spent on the ; development of the algorithms; ho wever; most of them are applicable for vector ; data and are based on point sets in a planar surface. The algorithms for ; generating the Voronoi diagrams of line and area sets in vector data are very ; complex. This complexity has greatly limited the application of the Voronoi data ; model and only limited advances have been achieved. On the other hand; only a ; few algorithms are available for generating Voronoi diagrams for point-sets; but
