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