本文選題：矢量數(shù)據(jù)壓縮　切入點(diǎn)：Douglas-Peucker算法　出處：《四川師范大學(xué)》2017年碩士論文　論文類型：學(xué)位論文

【摘要】：矢量數(shù)據(jù)壓縮一直以來(lái)都是GIS領(lǐng)域的一個(gè)研究熱點(diǎn)。通過(guò)減少矢量圖形的數(shù)據(jù)量,來(lái)滿足不同層次和尺度的應(yīng)用需求,達(dá)到降低數(shù)據(jù)傳輸、處理時(shí)間和存儲(chǔ)開(kāi)銷,提高圖形的分析、渲染效果的目的。矢量數(shù)據(jù)壓縮算法的研究歷史可追溯至四十多年前。目前已出現(xiàn)了許多壓縮算法,如Douglas-Peucker算法(DP算法)、Lang法、Li-Openshaw算法、基于小波分析的壓縮算法,以及一些結(jié)合智能算法(例如遺傳算法、動(dòng)態(tài)規(guī)劃算法、粒子群算法)的壓縮算法。對(duì)該問(wèn)題的研究雖然已有一些成果,但隨著技術(shù)的進(jìn)步,以及不斷衍生的新需求,矢量數(shù)據(jù)壓縮領(lǐng)域仍有一些問(wèn)題未得到良好的解決。本文針對(duì)DP算法可能存在的問(wèn)題進(jìn)行了分析和優(yōu)化,針對(duì)算法在處理多矢量數(shù)據(jù)時(shí)可能導(dǎo)致的兩類拓?fù)洚惢瘑?wèn)題進(jìn)行分析研究并給出有效可行的解決方案,保證了多矢量圖形壓縮時(shí)的拓?fù)湟恢滦�。論文主要工作如�?(1)提出了一種基于節(jié)點(diǎn)重要性的分段DP算法,并對(duì)其進(jìn)行了大量的實(shí)驗(yàn)驗(yàn)證。實(shí)驗(yàn)結(jié)果表明,與經(jīng)典DP算法相比,本文算法在圖形形狀保持度和時(shí)間效率上都有所提高。(2)針對(duì)相鄰圖形公共邊在化簡(jiǎn)時(shí)容易發(fā)生的裂縫問(wèn)題,本文提出了一種基于掃描線和Geohash索引的公共邊提取算法。首先利用單調(diào)鏈掃描線算法確定每個(gè)圖形的相交圖形;其次對(duì)于外接矩形相交的兩圖形,利用圖形的Geohash索引快速查找兩圖形的公共點(diǎn),提取公共邊和非公共邊,并標(biāo)記公共邊的頂點(diǎn)順序;最后對(duì)于壓縮過(guò)的公共邊進(jìn)行標(biāo)記,保證公共邊只處理一次。實(shí)驗(yàn)結(jié)果表明,該算法不僅可解決公共邊裂縫問(wèn)題,在時(shí)間效率上也具有較大優(yōu)越性。(3)針對(duì)化簡(jiǎn)時(shí)存在的自相交或相交拓?fù)洚惢瘑?wèn)題,本文提出了一種基于Geohash索引的相交拓?fù)洚惢焖偬幚硭惴�。首先將化�?jiǎn)前、后曲線圍城的多邊形區(qū)域轉(zhuǎn)化為Geohash編碼,以得到的Geohash編碼集合作為查詢條件在自身圖形以及相關(guān)圖形中檢索編碼對(duì)應(yīng)的點(diǎn),再通過(guò)射線法精確判斷這些點(diǎn)是否位于化簡(jiǎn)前、后曲線圍城的多邊形區(qū)域內(nèi)。若存在點(diǎn)位于該多邊形區(qū)域內(nèi),則說(shuō)明可能會(huì)發(fā)生自相交或相交,進(jìn)行校正處理。實(shí)驗(yàn)結(jié)果表明,該算法能夠保證壓縮時(shí)無(wú)自相交或相交拓?fù)洚惢陌l(fā)生,時(shí)間效率也較高。(4)在Microsoft Visual Studio 2010開(kāi)發(fā)環(huán)境下使用C#編程語(yǔ)言,采用面向?qū)ο笏枷朐O(shè)計(jì)并開(kāi)發(fā)了一個(gè)小型軟件系統(tǒng)作為測(cè)試平臺(tái),并對(duì)測(cè)試平臺(tái)進(jìn)行了測(cè)試。
[Abstract]:Vector data compression has always been a research hotspot in the field of GIS. By reducing the data volume of vector graphics, it can meet the application requirements of different levels and scales, and reduce the data transmission, processing time and storage overhead. The research history of vector data compression algorithm can be traced back to more than 40 years ago. At present, many compression algorithms have appeared, such as Douglas-Peucker algorithm, DP algorithm, Li-Openshaw algorithm, wavelet analysis based compression algorithm, etc. And some compression algorithms combining intelligent algorithms (such as genetic algorithm, dynamic programming algorithm, particle swarm optimization algorithm). There are still some problems in the field of vector data compression which have not been solved well. This paper analyzes and optimizes the possible problems in DP algorithm. In this paper, two kinds of topology alienation problems caused by the algorithm in dealing with multi-vector data are analyzed and studied, and an effective and feasible solution is given. The main work of this paper is as follows: 1) A piecewise DP algorithm based on node importance is proposed, and a large number of experiments are carried out to verify it. The experimental results show that compared with the classical DP algorithm, the proposed algorithm is more efficient than the classical DP algorithm. In this paper, the shape preserving degree and time efficiency are improved. In this paper, a common edge extraction algorithm based on scan line and Geohash index is proposed. Firstly, the monotone chain scan line algorithm is used to determine the intersection of each graph. The Geohash index of graphics is used to quickly find the common points of the two graphics, to extract the common edges and non-common edges, and to mark the vertex order of the common edges. Finally, the compressed common edges are marked to ensure that the common edges are processed only once. The experimental results show that, This algorithm can not only solve the problem of common edge crack, but also has great superiority in time efficiency. In this paper, a fast algorithm of intersecting topological dissimilation based on Geohash index is proposed. Firstly, the polygon region of the curve besieged before and after the simplification is transformed into Geohash coding. The obtained Geohash coding set is used as the query condition to retrieve the corresponding points in their own graphics and related graphics, and then the ray method is used to determine precisely whether these points are located before the simplification. If the point of existence is in the polygon region, the self-intersection or intersecting may occur, and the experimental results show that, The algorithm can ensure that there is no self-intersection or intersecting topology dissimilation in compression, and the time efficiency is also high. The algorithm uses C # programming language in Microsoft Visual Studio 2010 development environment. In this paper, a small software system is designed and developed with the object oriented idea as the test platform, and the test platform is tested.
【學(xué)位授予單位】：四川師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2017
【分類號(hào)】：P208

【參考文獻(xiàn)】

相關(guān)期刊論文 前10條

1 邵奇峰;李楓;;一種基于HBase的空間關(guān)鍵字查詢算法[J];計(jì)算機(jī)工程與科學(xué);2015年11期

2 李朝奎;駱文芳;陳果;嚴(yán)雯英;;漸進(jìn)式改進(jìn)的線要素簡(jiǎn)化算法探討[J];測(cè)繪科學(xué);2015年11期

3 于靖;陳剛;張笑;陳文龍;;面向自然岸線抽稀的改進(jìn)道格拉斯—普克算法[J];測(cè)繪科學(xué);2015年04期

4 賀曉暉;陳楠;;等高線自動(dòng)綜合方法的研究進(jìn)展[J];遙感信息;2014年05期

5 朱強(qiáng);武芳;錢(qián)海忠;李靖涵;;采用剖分思想的谷地彎曲識(shí)別及結(jié)構(gòu)化方法[J];測(cè)繪科學(xué)技術(shù)學(xué)報(bào);2014年04期

6 操震洲;李滿春;程亮;陳振杰;;適用于網(wǎng)絡(luò)漸進(jìn)傳輸?shù)亩喾直媛是�生成算法[J];計(jì)算機(jī)應(yīng)用;2013年03期

7 張棟海;黃麗娜;劉暉;唐健;;基于MapReduce的多機(jī)并行DP算法與實(shí)驗(yàn)分析[J];地球信息科學(xué)學(xué)報(bào);2013年01期

8 盧銀宏;岳東杰;宋飛鳳;;基于總體最小二乘的Douglas-Peucker算法在多波束測(cè)深數(shù)據(jù)抽稀中的應(yīng)用[J];水利與建筑工程學(xué)報(bào);2012年02期

9 任海艷;陳飛翔;;自適應(yīng)遺傳算法的改進(jìn)及在曲線化簡(jiǎn)中的應(yīng)用[J];計(jì)算機(jī)工程與應(yīng)用;2012年11期

10 黃志堅(jiān);張金芳;徐帆江;;關(guān)鍵點(diǎn)檢測(cè)的線要素綜合算法[J];中國(guó)圖象圖形學(xué)報(bào);2012年02期

相關(guān)博士學(xué)位論文 前3條

1 操震洲;矢量數(shù)據(jù)動(dòng)態(tài)多尺度網(wǎng)絡(luò)傳輸研究[D];南京大學(xué);2015年

2 劉慧敏;地圖空間信息量的度量方法研究[D];中南大學(xué);2012年

3 陳飛翔;移動(dòng)空間信息服務(wù)關(guān)鍵技術(shù)研究[D];中國(guó)科學(xué)院研究生院（遙感應(yīng)用研究所）;2006年

，

本文編號(hào)：1594826