球面全要素Voronoi圖構(gòu)建算法
發(fā)布時(shí)間：2018-08-01 19:10
【摘要】：作為地理信息系統(tǒng)發(fā)展的最高目標(biāo),數(shù)字地球的誕生與研究向傳統(tǒng)的空間數(shù)據(jù)表達(dá)、檢索、分析和建模等方面提出了新的挑戰(zhàn),引導(dǎo)他們由原來基于二維平面向著更高的維度發(fā)展。地球空間地理數(shù)據(jù)的表達(dá)作為全球地理信息系統(tǒng)(GlobalGIS)的研究與發(fā)展的基礎(chǔ),吸引著越來越多研究者的目光。 Voronoi圖是一個經(jīng)典的數(shù)學(xué)對象,全要素Voronoi圖是在點(diǎn)生長源的基礎(chǔ)上定義生長源為點(diǎn)、線和面要素的Vororoi圖,以適應(yīng)實(shí)際空間目標(biāo)。Voronoi具有獨(dú)特的數(shù)學(xué)性質(zhì),是迄今為止動態(tài)GIS領(lǐng)域最有希望的解決方法,并且提供了一種新的空間鄰近認(rèn)知途徑,有望從根本上解決地理信息系統(tǒng)中的鄰近計(jì)算問題。所以,建立基于全要素Voronoi圖的球面表達(dá)對于管理全球空間數(shù)據(jù)和維護(hù)球面空間動態(tài)關(guān)系具有重大價(jià)值。 目前,國際上對于球面Voronoi圖生成算法的研究并不多且最新成果比較少。比較典型的是Augenbaum利用“插入法”給出的球面上n個點(diǎn)的、Voronoi圖生成算法,時(shí)間復(fù)雜度為O(n2)；Robert提出的“分治算法”,時(shí)間復(fù)雜度為O(nlogn);童曉沖等提出的不同集合的球面矢量Voronoi圖矢量生成算法；趙學(xué)勝提出的基于鋪蓋的球面柵格Voronoi圖生成算法。前兩種算法都是針對球面離散點(diǎn)集的矢量算法,目前難以應(yīng)用于線要素、面要素。第三種方法是基于偏置曲線的球面Voronoi生成方法,可對線集與面集進(jìn)行操作,概念直觀且易于擴(kuò)展,但是實(shí)現(xiàn)較為困難且隨著數(shù)據(jù)規(guī)模的擴(kuò)大算法時(shí)空復(fù)雜度呈高次冪增長。最后一種是針對球面各種集合的柵格方法。柵格方法具有高維擴(kuò)展性,全要素性和易實(shí)現(xiàn)性等優(yōu)點(diǎn),但是時(shí)空復(fù)雜度較大,制約了球面Voronoi的發(fā)展應(yīng)用。 針對球面、Voronoi圖算法的問題,作者提出了一種新的球面矢量數(shù)據(jù)全要素Voronoi圖構(gòu)建方法。利用特定的距離值將線狀、面狀要素離散為包含屬性的點(diǎn)集。首先,針對點(diǎn)集生成要素的Voronoi子圖；其次,根據(jù)點(diǎn)與要素的隸屬關(guān)系合并子圖來構(gòu)建平面的全要素Voronoi圖；最后,利用中心透視投影,將球面目標(biāo)一體化投影至平面,在平面上完成全要素Voronoi圖生成后再反向投影回球面, 實(shí)現(xiàn)問題的降維處理。實(shí)驗(yàn)驗(yàn)證本文算法的正確性,并針對算法的效率、全要素Voronoi圖的精度和投影算法合理性與適用性給予討論。
[Abstract]:As the highest goal of the development of GIS, the birth and research of digital earth presents new challenges to the traditional spatial data representation, retrieval, analysis and modeling. Guide them from the original two-dimensional plane to a higher dimension. As the basis of the research and development of global geographic information system (GlobalGIS), the expression of geospatial geographic data attracts more and more researchers' attention. Voronoi graph is a classical mathematical object. Based on the point growth source, the total element Voronoi diagram defines the growth source as the Vororoi diagram of the point, line and surface elements, which is the most promising solution in the field of dynamic GIS so far, in order to adapt to the actual spatial target. The Voronoi has unique mathematical properties, so it is the most promising solution in the field of dynamic GIS up to now. It also provides a new cognitive approach to spatial proximity, which is expected to fundamentally solve the problem of proximity computing in geographic information systems (GIS). Therefore, the establishment of spherical representation based on all-factor Voronoi graphs is of great value in managing global spatial data and maintaining the spatial dynamic relationship of the sphere. At present, there are few researches on the generation of spherical Voronoi diagrams in the world. Typically, Augenbaum uses the "interpolation method" to generate the Voronoi diagram of n points on the sphere. The time complexity of the algorithm is the divide-and-conquer algorithm proposed by O (N2) Robert. The time complexity is O (nlogn); Tong Xiaochong et al. The algorithm for generating spherical vector Voronoi graph with different sets and Zhao Xuesheng's algorithm for generating spherical grid Voronoi graph based on paving. The first two algorithms are vector algorithms for spherical discrete point sets, which are difficult to be applied to line elements and surface elements. The third method is spherical Voronoi generation method based on offset curve, which can operate line set and surface set. The concept is intuitionistic and easy to expand, but it is difficult to realize and the space-time complexity increases with the expansion of data scale. The last one is a grid method for various sets of spherical surfaces. The grid method has the advantages of high dimensional expansibility, full element and easy realization, but the complexity of time and space is large, which restricts the development and application of spherical Voronoi. To solve the problem of the algorithm of spherical Voronoi diagram, a new method of constructing full-element Voronoi diagram of spherical vector data is proposed. The linear and surface elements are discretized into a set of points containing attributes by using specific distance values. Firstly, the Voronoi subgraph of the elements is generated for the point set; secondly, the Voronoi graph of all elements of the plane is constructed according to the subgraph of the subordinate relation between the point and the element; finally, the spherical object is projected to the plane by using the central perspective projection. The whole factor Voronoi graph is generated on the plane and then projected back to the spherical surface to reduce the dimension of the problem. The correctness of the proposed algorithm is verified by experiments, and the efficiency of the algorithm, the accuracy of the full element Voronoi diagram and the rationality and applicability of the projection algorithm are discussed.
【學(xué)位授予單位】：昆明理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：P208
本文編號：2158554
[Abstract]:As the highest goal of the development of GIS, the birth and research of digital earth presents new challenges to the traditional spatial data representation, retrieval, analysis and modeling. Guide them from the original two-dimensional plane to a higher dimension. As the basis of the research and development of global geographic information system (GlobalGIS), the expression of geospatial geographic data attracts more and more researchers' attention. Voronoi graph is a classical mathematical object. Based on the point growth source, the total element Voronoi diagram defines the growth source as the Vororoi diagram of the point, line and surface elements, which is the most promising solution in the field of dynamic GIS so far, in order to adapt to the actual spatial target. The Voronoi has unique mathematical properties, so it is the most promising solution in the field of dynamic GIS up to now. It also provides a new cognitive approach to spatial proximity, which is expected to fundamentally solve the problem of proximity computing in geographic information systems (GIS). Therefore, the establishment of spherical representation based on all-factor Voronoi graphs is of great value in managing global spatial data and maintaining the spatial dynamic relationship of the sphere. At present, there are few researches on the generation of spherical Voronoi diagrams in the world. Typically, Augenbaum uses the "interpolation method" to generate the Voronoi diagram of n points on the sphere. The time complexity of the algorithm is the divide-and-conquer algorithm proposed by O (N2) Robert. The time complexity is O (nlogn); Tong Xiaochong et al. The algorithm for generating spherical vector Voronoi graph with different sets and Zhao Xuesheng's algorithm for generating spherical grid Voronoi graph based on paving. The first two algorithms are vector algorithms for spherical discrete point sets, which are difficult to be applied to line elements and surface elements. The third method is spherical Voronoi generation method based on offset curve, which can operate line set and surface set. The concept is intuitionistic and easy to expand, but it is difficult to realize and the space-time complexity increases with the expansion of data scale. The last one is a grid method for various sets of spherical surfaces. The grid method has the advantages of high dimensional expansibility, full element and easy realization, but the complexity of time and space is large, which restricts the development and application of spherical Voronoi. To solve the problem of the algorithm of spherical Voronoi diagram, a new method of constructing full-element Voronoi diagram of spherical vector data is proposed. The linear and surface elements are discretized into a set of points containing attributes by using specific distance values. Firstly, the Voronoi subgraph of the elements is generated for the point set; secondly, the Voronoi graph of all elements of the plane is constructed according to the subgraph of the subordinate relation between the point and the element; finally, the spherical object is projected to the plane by using the central perspective projection. The whole factor Voronoi graph is generated on the plane and then projected back to the spherical surface to reduce the dimension of the problem. The correctness of the proposed algorithm is verified by experiments, and the efficiency of the algorithm, the accuracy of the full element Voronoi diagram and the rationality and applicability of the projection algorithm are discussed.
【學(xué)位授予單位】：昆明理工大學(xué)
【學(xué)位級別】：碩士
【學(xué)位授予年份】：2014
【分類號】：P208
【參考文獻(xiàn)】
相關(guān)期刊論文 前10條
1 趙學(xué)勝,陳軍;基于球面四元三角網(wǎng)剖分的層次空間關(guān)系推理[J];測繪學(xué)報(bào);2001年04期
2 童曉沖;賁進(jìn);張永生;;不同集合的球面矢量VORONOI圖生成算法[J];測繪學(xué)報(bào);2006年01期
3 李佳田;陳軍;趙仁亮;陳浩;馬力;;基于線性四叉樹結(jié)構(gòu)的Voronoi圖反向膨脹生成方法[J];測繪學(xué)報(bào);2008年02期
4 紀(jì)鳳欣,歐宗瑛,秦緒佳,侯建華;基于Delaunay三角剖分的層析圖像離散數(shù)據(jù)表面重建算法[J];工程圖學(xué)學(xué)報(bào);2001年02期
5 賁進(jìn);童曉沖;張衡;江剛武;;基于六邊形網(wǎng)格的球面Voronoi圖生成算法[J];測繪科學(xué)技術(shù)學(xué)報(bào);2006年05期
6 孫繼忠;胡艷;馬永強(qiáng);;基于Delaunay三角剖分生成Voronoi圖算法[J];計(jì)算機(jī)應(yīng)用;2010年01期
7 趙曄,張有會,趙志輝,楊俊華;關(guān)于一般圖形Voronoi圖的離散構(gòu)造法的研究[J];計(jì)算機(jī)應(yīng)用與軟件;2004年06期
8 馮琰,施一民;基于區(qū)域性橢球面的三維GIS可視化模型[J];同濟(jì)大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年09期
9 童曉沖;賁進(jìn);張永生;;基于二十面體剖分格網(wǎng)的球面實(shí)體表達(dá)與Voronoi圖生成[J];武漢大學(xué)學(xué)報(bào)(信息科學(xué)版);2006年11期
10 李佳田;李佳;段平;余莉;;球面Delaunay三角網(wǎng)的透視投影算法[J];武漢大學(xué)學(xué)報(bào)(信息科學(xué)版);2011年09期
，本文編號：2158554
本文鏈接：http://sikaile.net/kejilunwen/dizhicehuilunwen/2158554.html
最近更新
教材專著
