[發(fā)明專利]一種單機(jī)多核環(huán)境下約束地形并行構(gòu)建方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201510299433.6
• 申請(qǐng)日: 2015-06-03
• 公開（公告）號(hào): CN105160706B
• 公開（公告）日: 2017-12-19
• 發(fā)明（設(shè)計(jì)）人: 劉德兒;熊證
• 申請(qǐng)（專利權(quán)）人: 江西理工大學(xué)
• 主分類號(hào): G06T17/05
• 分類號(hào): G06T17/05
• 代理公司: 四川君士達(dá)律師事務(wù)所51216
• 代理人: 芶忠義

技術(shù)領(lǐng)域

本發(fā)明屬于測(cè)繪、地理信息技術(shù)領(lǐng)域，涉及一種單機(jī)多核環(huán)境下約束地形并行構(gòu)建方法。

背景技術(shù)

三角剖分可追溯到二十世紀(jì)三十年代，于1934年由俄國著名數(shù)學(xué)家Delaunay在解決數(shù)值分析問題提出的，然而當(dāng)時(shí)的生成算法并不成熟，后經(jīng)過學(xué)者們的努力探索研究，在七十年代后期得到了較大的發(fā)展和應(yīng)用，如今已有多種Delaunay三角剖分算法被人們接受和采用。Tsai根據(jù)實(shí)現(xiàn)過程將剖分算法分成了三類，即分治算法、逐點(diǎn)插入法和三角網(wǎng)生長法。除此之外，此后的研究大多是基于這三類算法在兩種方式上進(jìn)行改進(jìn)，一是對(duì)算法實(shí)現(xiàn)過程的某方面繼續(xù)改進(jìn)和完善，二是研究兩種算法同時(shí)參與D-TIN構(gòu)建的合成算法，當(dāng)然還有學(xué)者提出了新的算法如：基于掃描線的剖分法、基于凸殼的剖分法、基于遺傳算法的剖分法等。

Shamos和Hoey在1975首次提出了分治算法，算法設(shè)計(jì)的目的主要是為了生成Voronoi圖，而Lewis和Robinson首次將分治思想應(yīng)用于D-TIN構(gòu)建中。Lawson在1977年首次提出了逐點(diǎn)插入法及其改進(jìn)算法，Lee和schachter等人先后進(jìn)行了改進(jìn)和完善，這些改進(jìn)的用于實(shí)現(xiàn)D-TIN構(gòu)建的逐點(diǎn)插入法中，主要差別在于設(shè)置初始多邊形和建立初始三角網(wǎng)的方法不同。Green和Sibson在1978年首次提出了三角網(wǎng)生長算法，并實(shí)現(xiàn)了一個(gè)生成Dirichlet多邊形圖的生長算法，McCullagh和Ross為了減少搜索第三點(diǎn)的時(shí)間，將點(diǎn)集進(jìn)行了分塊和排序從而達(dá)到縮短時(shí)間目的。Brassel,Reif,Maus等人進(jìn)行了類似的改進(jìn)，主要在改進(jìn)搜尋“第三點(diǎn)”上入手。A.Mirante和N.Weingarten在1982年提出了輻射掃描法，然而這種方法產(chǎn)生的三角網(wǎng)并不是真正的D-TIN，主要因其不一定能滿足外接圓性質(zhì)。Steven Fortune于1987年在Algorithmica上提出了V-圖生成的平面掃描算法思想。J.R.Shewchuk等人應(yīng)用掃描線算法實(shí)現(xiàn)了D-TIN構(gòu)建。Marcelo Kallmann和Hanspeter Bieri等提出了在約束Delaunay三角網(wǎng)中進(jìn)行約束點(diǎn)和線的插入和刪除算法，并解決了自相交或重復(fù)的點(diǎn)自動(dòng)檢測(cè)，得到一個(gè)完全動(dòng)態(tài)的約束Delaunay三角剖分，同時(shí)，在可視化、重構(gòu)、地理信息系統(tǒng)等應(yīng)用方面進(jìn)行了討論。