發(fā)布時(shí)間：2021-03-25 23:39

　　近些年來,隨著GIS、計(jì)算機(jī)輔助設(shè)計(jì)、三維物體表面重建、醫(yī)學(xué)或衛(wèi)星圖像數(shù)據(jù)處理等領(lǐng)域的發(fā)展,多邊形的相關(guān)運(yùn)算越來越重要。多邊形的相關(guān)運(yùn)算可大致分為生成、合并及布爾運(yùn)算,是計(jì)算幾何中的幾個(gè)重要的問題。本文對(duì)多邊形相關(guān)的算法進(jìn)行了深入細(xì)致的研究。大致分為四個(gè)部分:多邊形合并算法、線段集生成簡單多邊形算法、多邊形的三角剖分以及多邊形布爾運(yùn)算算法。主要目的分為兩個(gè),一個(gè)是簡化算法過程,降低時(shí)間復(fù)雜度,另一個(gè)是縮短連接線長度,在實(shí)際應(yīng)用方面可降低成本。1.給出的多邊形合并算法是將兩個(gè)不相交多邊形連接成一條回路。該算法通過刪除多邊形兩側(cè)距離較短的點(diǎn),并將剩余頂點(diǎn)構(gòu)成一個(gè)新的多邊形,然后對(duì)新多邊形進(jìn)行Delaunay三角剖分,以Delaunay邊作為對(duì)角線構(gòu)成四邊形,找到四邊形的邊長增值最小的連接點(diǎn)與的對(duì)應(yīng)點(diǎn),刪除相應(yīng)邊,得到具有最小長度的回路,降低了算法的時(shí)間復(fù)雜度。2.給出了線段集生成簡單多邊形算法,首先逐層計(jì)算線段集的凸殼,為了縮短連接線段長度和將這些凸殼根據(jù)Delaunay三角剖分選取最近點(diǎn)或次最近點(diǎn)改變成簡單多邊形,然后計(jì)算多邊形之間的交點(diǎn)并刪除,最后將這些簡單多邊形合并成一個(gè)簡單多邊形。... 

【文章來源】：哈爾濱理工大學(xué)黑龍江省

【文章頁數(shù)】：53 頁

【學(xué)位級(jí)別】：碩士

【部分圖文】：

a1V(p)，2V(p)的圖示

第 2 章 基礎(chǔ)知識(shí)近些年來，多邊形的合并、線段集生成簡單多邊形、多邊形的三角剖分以及布爾運(yùn)算在實(shí)際中得到越來越多的應(yīng)用，接下來介紹本文的相關(guān)知識(shí)點(diǎn)。2.1 多邊形三角剖分2.1.1 Voronoi 圖的基本概念[31]設(shè)1p ,2p 是平面上的兩點(diǎn)，L是1 2p p 的垂直平分線，L將平面劃分成rL 、RL ，位于rL 內(nèi)的點(diǎn)具有特性： 1 2, ,l ld p p d p p，其中 , l id p p 表示lp 與ip之間的歐幾里得距離，i=1,2。這說明，位于rL 內(nèi)的點(diǎn)比平面中的其他點(diǎn)更加接近點(diǎn)1p ，也就是說，rL 內(nèi)的點(diǎn)是比平面上其他點(diǎn)更接近1p 的點(diǎn)的軌跡，記為1V ( p )，如圖 2-1a 所示。如果用1 2H ( p , p )表示半平面rL ，而2 1( , )RL H p p，則有1 1 2 2 2 1V ( p ) H ( p , p ), V ( p ) H ( p , p)。

哈爾濱理工大學(xué)理學(xué)碩士學(xué)位論文多邊形域，稱為關(guān)聯(lián)于ip 的 Voronoi 多邊形（-1b 表示關(guān)聯(lián)于1p 的 Voronoi 多邊形，是一個(gè)四于S 中的每個(gè)點(diǎn)都可以做一個(gè) Voronoi 多邊形onoi 多邊形構(gòu)成的圖，記為 Vor ( S )，如圖 2-2 中 Voronoi 頂點(diǎn)，邊稱為 Voronoi 邊。


本文編號(hào)：3100528