資源描述：
《基于全面預(yù)算管理視角下的企業(yè)內(nèi)部控制研究》由會(huì)員上傳分享，免費(fèi)在線(xiàn)閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。
1、基于三角網(wǎng)生長(zhǎng)法的Delaunay三角網(wǎng)生成算法***************【摘要】論文簡(jiǎn)要介紹了Delaunay三角網(wǎng)的性質(zhì)以及基本生成算法，并重點(diǎn)介紹了三角網(wǎng)生長(zhǎng)法的基本原理和算法步驟，并通過(guò)設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu)，對(duì)算法進(jìn)行實(shí)現(xiàn)。對(duì)算法進(jìn)行分析并提出通過(guò)構(gòu)建格網(wǎng)索引，進(jìn)一步提高三角網(wǎng)生成效率。【關(guān)鍵詞】三角網(wǎng)生長(zhǎng)法擴(kuò)展TIN格網(wǎng)索引1.引言數(shù)字地形模型DTM（DigitalTerrainModel）是指對(duì)地形表面形態(tài)屬性信息的數(shù)字表達(dá)，是帶有空間位置特征和地形屬性特征的數(shù)字描述[1]。DTM是GIS的基礎(chǔ)數(shù)據(jù)來(lái)源，可用于土地利用現(xiàn)狀的分析、合理規(guī)劃及洪水險(xiǎn)情預(yù)報(bào)等。D
2、TM地形屬性為高程時(shí)稱(chēng)為數(shù)字高程模型(DEM)。DEM主要的三種表示模型為規(guī)則格網(wǎng)模型、等高線(xiàn)模型、不規(guī)則三角網(wǎng)模型（TriangularIrregularNetwork簡(jiǎn)稱(chēng)TIN）。數(shù)字化等高線(xiàn)模型不適合計(jì)算坡度或制作地貌渲染圖等地形分析，規(guī)則格網(wǎng)數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單，計(jì)算方便；但存在數(shù)據(jù)冗余，數(shù)據(jù)采集較麻煩，難以表達(dá)復(fù)雜地形等缺陷。TIN即能夠避免平坦地形時(shí)數(shù)據(jù)冗余，也能表達(dá)復(fù)雜地形，可以根據(jù)任意地形特征點(diǎn)表示DEM，因此被廣泛應(yīng)用。Delaunay三角剖分能最大程度的接近等邊三角形，避免狹長(zhǎng)三角形，并且能保持三角網(wǎng)的唯一性，使其成為生成TIN的最佳選擇。本論文將簡(jiǎn)要介紹和比
3、較幾種常用的Delaunay三角網(wǎng)生成算法（逐點(diǎn)插入法，三角網(wǎng)生長(zhǎng)法，分割合并算法等），并且對(duì)三角網(wǎng)生長(zhǎng)法算法原理進(jìn)行研究分析和程序?qū)崿F(xiàn)。2.Delaunay三角網(wǎng)的性質(zhì)Delaunay三角網(wǎng)中的三角形必須滿(mǎn)足以下幾個(gè)性質(zhì)：（1）空?qǐng)A特性每一個(gè)Delaunay三角形的外接圓不包括Delaunay三角網(wǎng)中的任何其他點(diǎn)。（1）最大最小角特性在三角剖分中，Delaunay三角網(wǎng)的所有三角形的最小角之和最大。即使得Delaunay三角形最大程度接近等邊三角形。（2）唯一性對(duì)于一組離散點(diǎn)，若不存在四點(diǎn)共圓的情況，離散點(diǎn)構(gòu)成的Delaunay三角網(wǎng)是唯一的。1.Delaunay三角網(wǎng)
4、生成算法介紹Delaunay三角網(wǎng)的生成常用算法有逐點(diǎn)插入法，分割合并算法，三角網(wǎng)生長(zhǎng)法。生成三角網(wǎng)的算法不同在于初始三角網(wǎng)的生成以及三角網(wǎng)的擴(kuò)展方法。3.1逐點(diǎn)插入法逐點(diǎn)插入算法的基本思想是，在包含所有數(shù)據(jù)點(diǎn)的多邊形中建立初始三角形，然后將余下的點(diǎn)進(jìn)行逐一插入，查找該點(diǎn)所在的三角形，將該點(diǎn)與三角形的三頂點(diǎn)進(jìn)行連接，生成三個(gè)新的三角形，用LOP算法優(yōu)化三角網(wǎng)確保其成為Delaunay三角網(wǎng)。所謂LOP優(yōu)化算法是為了生成的三角形符合Delaunay三角形的空?qǐng)A特性，最大最小角性，唯一性。其主要做法為：（1）將兩個(gè)具有公共邊的三角形合并成一個(gè)四邊形（2）用空?qǐng)A特性檢查三角形，
5、若四邊形的第四點(diǎn)（除檢查三角形的三點(diǎn)外）若在三角形的外接圓之內(nèi)，就對(duì)四邊形對(duì)角線(xiàn)進(jìn)行對(duì)調(diào)處理。若不在，則不做處理。3.2分割合并算法分割合并算法的基本思想是把點(diǎn)集進(jìn)行劃分到足夠小，使其易于生成三角網(wǎng)，用LOP算法對(duì)子集進(jìn)行優(yōu)化，保證其成為Delaunay三角網(wǎng)，最后合并子集生成最終的三角網(wǎng)。3.3三角網(wǎng)生長(zhǎng)法三角網(wǎng)生長(zhǎng)法的基本思想是先建立初始三角形，然后以初始三角形的三條邊作為種子，分別“生長(zhǎng)”出新的三角形，將新的三角形的三邊又作為種子，依次生長(zhǎng)新三角形。生長(zhǎng)的新三角形必須是Delaunay三角形，故得滿(mǎn)足空?qǐng)A特性和最大最小角特性，因此按照這兩個(gè)特性來(lái)生長(zhǎng)Delaunay
6、三角形。具體算法原理，算法步驟，算法實(shí)現(xiàn)以及改進(jìn)將在后續(xù)詳細(xì)講述。3.4幾種算法的比較逐點(diǎn)插入算法和分割合并算法都較之三角網(wǎng)生長(zhǎng)法，效率高。三角網(wǎng)生長(zhǎng)法，雖每次都是生成Delaunay三角形，但是每次都得遍歷剩余的所有點(diǎn)，搜索到符合條件的第三點(diǎn)。因此效率不高，故可以通過(guò)改進(jìn)其點(diǎn)的搜索策略來(lái)提高其生成效率。逐點(diǎn)插入法，在三角網(wǎng)生成后期，隨著點(diǎn)數(shù)的增多，其會(huì)使得三角形生成速率大大降低。分割合并思想較之前面兩種算法最好，但是其精髓在于如何合理分塊，如何快速有效得進(jìn)行子網(wǎng)合并和優(yōu)化。除了上述三種生成算法，還有凸包法，分治算法等，具體可以參照相關(guān)文獻(xiàn)。1.三角網(wǎng)生成算法4.1算法原
7、理三角網(wǎng)生長(zhǎng)算法是在生成的初始三角形的基礎(chǔ)上擴(kuò)展三角網(wǎng)，初始三角形通過(guò)選擇最短邊和與最短邊構(gòu)成最大角的點(diǎn)構(gòu)成第一個(gè)三角形，然后取第一個(gè)三角形的三條邊按照Delaunay三角網(wǎng)的特性進(jìn)行擴(kuò)展三角網(wǎng)。4.2算法實(shí)現(xiàn)對(duì)于算法的程序?qū)崿F(xiàn)，主要需要考慮如何設(shè)計(jì)合理的數(shù)據(jù)結(jié)構(gòu)，算理清法步驟，掌握程序語(yǔ)言。以下將從數(shù)據(jù)結(jié)構(gòu)，算法步驟以及程序問(wèn)題逐一進(jìn)行闡述。4.2.1數(shù)據(jù)結(jié)構(gòu)算法的實(shí)現(xiàn)以及算法的執(zhí)行效率與設(shè)計(jì)的數(shù)據(jù)結(jié)構(gòu)有密切的關(guān)系，一個(gè)良好的數(shù)據(jù)結(jié)構(gòu)有利于對(duì)數(shù)據(jù)進(jìn)行高效的管理（存儲(chǔ)和檢索），從而提高算法的執(zhí)行效率。（1）離散點(diǎn)結(jié)構(gòu)離散點(diǎn)主要
