空間矢量數(shù)據(jù)的疊置算法研究.pdf

1、空間分析是空間信息系統(tǒng)的核心和關(guān)鍵功能之一，也是評(píng)價(jià)一個(gè)空間信息系統(tǒng)功能強(qiáng)弱的重要指標(biāo)。疊置分析是空間分析的基本功能之一，也是眾多空間分析方法的基礎(chǔ)。根據(jù)不同的數(shù)據(jù)模型可將疊置分析分為柵格疊置分析和矢量疊置分析兩種。柵格疊置分析較容易實(shí)現(xiàn)，但其精度往往不能滿(mǎn)足用戶(hù)的要求；與其相反，矢量疊置能達(dá)到很高的精度，但需要處理大量的矢量空間數(shù)據(jù)。由于空間數(shù)據(jù)量較大，常規(guī)算法難以滿(mǎn)足用戶(hù)對(duì)于時(shí)間的要求。因此，如何快速準(zhǔn)確地完成矢量疊置運(yùn)算是空間分析

2、中的關(guān)鍵技術(shù)之一。
　　 本文的主要工作如下：
　　 1、線(xiàn)與多邊形疊置，其核心算法是多邊形對(duì)線(xiàn)的裁剪，即線(xiàn)裁剪。本文提出一種適用于一般多邊形的快速的線(xiàn)裁剪算法，該算法先利用快速排斥試驗(yàn)排除了大量與被裁剪線(xiàn)段明顯不相交的多邊形窗口的邊，然后利用多邊形的邊對(duì)被裁剪線(xiàn)段的跨立試驗(yàn)進(jìn)一步排除了不跨立被裁剪線(xiàn)段的邊。從而減少了大量的不必要的求交運(yùn)算，提高了裁剪的速度。
　　 2、多邊形與多邊形疊置，其核心算法是多邊形裁剪

3、。Weiler-Atherton算法是經(jīng)典的多邊形裁剪算法，本文對(duì)之進(jìn)行了改進(jìn)。改進(jìn)后的算法采用數(shù)組存儲(chǔ)被裁剪多邊形和結(jié)果多邊形的頂點(diǎn)，采用單鏈表存儲(chǔ)裁剪多邊形的頂點(diǎn)，簡(jiǎn)化了數(shù)據(jù)結(jié)構(gòu)，進(jìn)而使得算法易于實(shí)現(xiàn)，并且具有更高的效率。
　　 在多邊形求交的過(guò)程中，引用本文提出的新的線(xiàn)裁剪算法，加快了多邊形求交速度，另外，在求得交點(diǎn)的同時(shí)獲取了被裁剪多邊形上構(gòu)成結(jié)果多邊形的邊，提高了結(jié)果多邊形的生成速度。
　　 3、作為對(duì)所研究算