Voronoi圖細(xì)分算法研究.pdf

1、Voronoi圖在計(jì)算幾何中是一個(gè)重要的概念，它在地質(zhì)、機(jī)器人軌跡控制、氣象學(xué)等方面都得到廣泛的應(yīng)用，因此構(gòu)建Voronoi圖就顯得十分重要。已有的Voronoi圖算法大致上可以分為矢量法和柵格法兩類，矢量法的優(yōu)勢(shì)是生成的圖形精度較高，但在高維空間上就要將面或更復(fù)雜的圖形分解為點(diǎn)和線后處理，會(huì)破壞生成元的完整性，而且矢量法的存儲(chǔ)結(jié)構(gòu)比較復(fù)雜;柵格法對(duì)于生成元與空間沒有限制，但是生成的圖形精度低，算法過程耗時(shí)長(zhǎng)。
　　本文在緒論部分

2、介紹了Voronoi圖的研究背景和研究現(xiàn)狀，在第二章中主要總結(jié)歸納了Voronoi圖的相關(guān)理論。借助于四叉樹數(shù)據(jù)結(jié)構(gòu)和區(qū)間運(yùn)算技術(shù)，本文重點(diǎn)在第三章提出了一種新的計(jì)算平面點(diǎn)集Voronoi圖的細(xì)分算法，并推算出了此算法的時(shí)間復(fù)雜度。且與增量算法和柵格擴(kuò)張法進(jìn)行了對(duì)比分析，顯示了這個(gè)新算法的有效性。本文第四章首先提出了一種新的計(jì)算平面多邊形內(nèi)部Voronoi圖的一般細(xì)分算法，然后對(duì)此算法作了進(jìn)一步的改進(jìn)，對(duì)比得出改進(jìn)后的算法能極大地提高計(jì)