（5）空間分析--TIN.ppt

第四章泰森多邊形分析 授課單位 天津師范大學(xué)城市與環(huán)境科學(xué)學(xué)院授課人 崔鐵軍 空間分析 4 1概念4 2基于矢量方式構(gòu)建TIN4 3基于柵格方式構(gòu)建TIN4 4約束條件的TIN生成 授課內(nèi)容 1 Voronoi圖給定一個(gè)二維Euclidean空間E和一個(gè)n點(diǎn)mi集M 那么 關(guān)聯(lián)的Voronoi圖為覆蓋的一個(gè)凸多邊形序列 V m1 V m2 V mn 其中 V mi 包括E中所有以M為中心的mi為近點(diǎn)的點(diǎn) 即 4 1泰森多邊形概念 V mi p E Vj 1 j n d p mi d p mj 其中 d表示Euclidean距離 2 Thissen多邊形1911年 荷蘭氣候?qū)W家A H Thissen應(yīng)用V 圖進(jìn)行了大區(qū)域內(nèi)的平均降水量研究 提出了一種根據(jù)離散分布的氣象站的降雨量來(lái)計(jì)算平均降雨量的方法 即將所有相鄰氣象站連成三角形 作這些三角形各邊的垂直平分線 于是每個(gè)氣象站周圍的若干垂直平分線便圍成一個(gè)多邊形 并稱這個(gè)多邊形為Thissen多邊形 4 1泰森多邊形概念 根據(jù)上述定義可得到Thissen多邊形的如下性質(zhì) 1 在空間E上給定的n個(gè)離散點(diǎn) 將空間E分成n個(gè)Thissen多邊形的分法是惟一的 2 Thissen多邊形是凸多邊形 位于Thissen多邊形邊上的點(diǎn)到其兩邊的離散點(diǎn)的距離相等 Thissen多邊形內(nèi)的點(diǎn)到相應(yīng)離散點(diǎn)的距離最近 3 Thissen多邊形的每個(gè)頂點(diǎn)是每個(gè)三角形的外接圓圓心 4 任意兩個(gè)Thissen多邊形不存在公共區(qū)域 5 由Thissen多邊形獲得的三角形在數(shù)據(jù)點(diǎn)均勻分布的情況下 可以避免產(chǎn)生狹長(zhǎng)和小角度三角形 4 1泰森多邊形概念 3 Delaunay三角網(wǎng)1934年 俄國(guó)數(shù)學(xué)家B Delaunay由V 圖演化出了更易于分析應(yīng)用的DelaunayTriangulation 簡(jiǎn)稱Delaunay三角形 4 1泰森多邊形概念 給定一個(gè)d維Euclidean空間和一個(gè)點(diǎn)集 那么 關(guān)聯(lián)的Voronoi圖 又稱Thissen多邊形 為覆蓋的一個(gè)凸多邊形序列 其中 包括中所有以中的為最近點(diǎn)的點(diǎn) 即 表示Euclidean距離 Voronoi圖的幾何對(duì)偶即把點(diǎn)聯(lián)結(jié)起來(lái)而得到的鄰接格網(wǎng)稱為的Delaunay三角網(wǎng) 從此 V 圖和Delaunay三角形就成了被普遍接受和廣泛采用的分析研究區(qū)域離散數(shù)據(jù)的有力工具 4 1泰森多邊形概念 Delaunay三角形具有以下性質(zhì) 1 惟一性 UniqueProperty 即不論從何處開始聯(lián)網(wǎng) 最終將得到一致的結(jié)果 2 空?qǐng)A性質(zhì) EmptyCircleProperty 任何一個(gè)Delaunay三角形的外接圓內(nèi)不能包含任何其他離散點(diǎn) Delaunay三角形外接圓內(nèi)不包含其他點(diǎn)的特性被用作一系列不重合的平面點(diǎn)建立Delaunay三角網(wǎng)的基本法則 稱作空?qǐng)A法則 它選擇最鄰近的點(diǎn)形成三角形 并使得特征線段均成為三角形的邊 3 最大最小角性質(zhì) Max MinAngleProperty 即任意兩個(gè)相鄰的Delaunay三角形組成的凸四邊形在交換對(duì)角線之后 六個(gè)內(nèi)角的最小值不再增大 該性質(zhì)說明三角形具有最佳形狀特征 4 1泰森多邊形概念 Voronoi圖與Delaunay三角形相互間的幾何對(duì)偶關(guān)系 Delaunay三角形與V 圖以幾何對(duì)偶形式而出現(xiàn) 其中虛線構(gòu)成的多邊形就是Thissen多邊形 4 1泰森多邊形概念 狄洛尼三角形外接圓內(nèi)不包含其它的點(diǎn) 建立狄洛尼三角網(wǎng)的基本法則 稱為空?qǐng)A法則 狄洛尼法則 1 在三角形內(nèi) 2 在三角形外 3 在三角形外接圓上 4 在外接圓外 4 1泰森多邊形概念 根據(jù)隨機(jī)分布的原始高程點(diǎn)建立連續(xù)的覆蓋整個(gè)研究地區(qū)的不規(guī)則三角網(wǎng) TIN 需要解決的最根本的問題就是如何確定哪三個(gè)數(shù)據(jù)點(diǎn)構(gòu)成一個(gè)三角形 也稱為自動(dòng)聯(lián)結(jié)三角網(wǎng) 對(duì)于平面上的離散數(shù)據(jù)點(diǎn) 將其中相近的三點(diǎn)構(gòu)成最佳三角形 使每個(gè)數(shù)據(jù)點(diǎn)都成為三角形頂點(diǎn) 4 2基于矢量方式構(gòu)建TIN 1 三角網(wǎng)生長(zhǎng)法Green和Sibson 1978 首次實(shí)現(xiàn)了一個(gè)生成Dirichlet多邊形的生長(zhǎng)算法 Brassel和Reif 1979 稍后也發(fā)表了類似的算法 McCullagh和Ross通過把點(diǎn)集分塊和排序改進(jìn)了點(diǎn)搜索方法 減少了搜索時(shí)間 Maus也給出了一個(gè)非常相似的算法 三角網(wǎng)生長(zhǎng)算法的基本思路是 首先找出點(diǎn)集中相距最短的兩點(diǎn)連線成為一條Delaunay三角網(wǎng)的邊 然后按Delaunay三角網(wǎng)的判斷法則找出包含此邊的Delaunay三角網(wǎng)的另一端點(diǎn) 依次處理所有新生成的邊 直至最終完成 各種不同的實(shí)現(xiàn)方法多表現(xiàn)在搜尋 第三點(diǎn) 的方法不同 4 2基于矢量方式構(gòu)建TIN 三角網(wǎng)生長(zhǎng)算法的基本步驟是 1 以任一點(diǎn)為起始點(diǎn) 找出與起始點(diǎn)最近的數(shù)據(jù)點(diǎn)相互連接形成Delaunay三角形的一條邊作為基線 按Delaunay三角網(wǎng)的判別法則 即它的兩個(gè)基本性質(zhì) 找出與基線構(gòu)成Delaunay三角網(wǎng)的第三點(diǎn) 2 基線的兩個(gè)端點(diǎn)與第三點(diǎn)相連 成為新的基線 3 迭代以上兩步直至所有基線都被處理 a 形成第一個(gè)三角形 b 擴(kuò)展生成第二個(gè)和第三個(gè)三角形 4 2基于矢量方式構(gòu)建TIN 2逐點(diǎn)插入法Lawson提出用逐點(diǎn)插入法建立Delaunay三角網(wǎng)的算法思想 Lee和Schachter Bowyer Watson Sloan Macedonio和Pareschi Floriani和Puppo Tsai等人先后改進(jìn)和完善了這一算法 逐點(diǎn)插入算法的思路非常簡(jiǎn)單 先在包含所有數(shù)據(jù)點(diǎn)的一個(gè)多邊形中建立初始三角網(wǎng) 然后將余下的點(diǎn)逐一插入 用LOP算法確保其成為Delaunay三角網(wǎng) 各種實(shí)現(xiàn)方法的差別在于其初始多邊形的不同以及建立初始三角網(wǎng)的方法的不同 逐點(diǎn)插入算法的基本步驟是 1 定義一個(gè)包含所有數(shù)據(jù)點(diǎn)的初始多邊形 2 在初始多邊形中建立初始三角網(wǎng) 然后按以下步驟迭代計(jì)算 直至所有數(shù)據(jù)點(diǎn)都被處理 第一步 插入一個(gè)數(shù)據(jù)點(diǎn)P 在三角網(wǎng)中找出包含P的三角形t 把P與t的三個(gè)頂點(diǎn)相連 生成三個(gè)新的三角形 第二步 用LOP算法優(yōu)化三角網(wǎng) 4 2基于矢量方式構(gòu)建TIN 3分治算法Shamos和Hoey提出了分治算法思想 并給出了一個(gè)生成V 圖的分治算法 Lewis和Robinson將分治算法思想應(yīng)用于生成Delaunay三角網(wǎng) 他們給出了一個(gè) 問題簡(jiǎn)化 算法 遞歸地分割點(diǎn)集 直至子集中只包含三個(gè)點(diǎn)而形成三角形 然后自下而上地逐級(jí)合并生成最終的三角網(wǎng) 以后Lee和Schachter又改進(jìn)和完善了Lewis和Robinson的算法 分治算法的基本思路是使問題簡(jiǎn)化 把點(diǎn)集劃分到足夠小 使其易于生成三角網(wǎng) 然后把子集中的三角網(wǎng)合并生成最終的三角網(wǎng) 用LOP算法保證其成為Delaunay三角網(wǎng) 不同的實(shí)現(xiàn)方法可有不同的點(diǎn)集劃分法 子三角網(wǎng)生成法及合并法 4 2基于矢量方式構(gòu)建TIN Lee和Schachter算法的基本步驟是 把點(diǎn)集 以橫坐標(biāo)為主 縱坐標(biāo)為輔按升序排序 然后遞歸地執(zhí)行以下步驟 1 把點(diǎn)集分成近似相等的兩個(gè)子集VL和VR 2 在VL和VR中生成三角網(wǎng) 3 用Lawson提出的局部?jī)?yōu)化算法LOP優(yōu)化所生成的三角網(wǎng) 使之成為Delaunay三角網(wǎng) 4 找出連接VL和VR中兩個(gè)凸殼的底線和頂線 5 由底線至頂線合并VL和VR中的兩個(gè)三角形 4 2基于矢量方式構(gòu)建TIN Lawson提出的局部?jī)?yōu)化算法LOP LocalOptimizationProcedure 即交換凸四邊形的對(duì)角線 可獲得等角性最好的三角網(wǎng) 它是所有生成Delaunay三角網(wǎng)算法都要用到的關(guān)鍵過程 理論上說 不論用何種方法生成的三角網(wǎng) 只要用LOP過程進(jìn)行處理 就能使它變?yōu)镈elaunay三角網(wǎng) 這樣的一個(gè)過程其實(shí)很簡(jiǎn)單 它就是運(yùn)用Delaunay三角網(wǎng)的性質(zhì)對(duì)由兩個(gè)有公共邊三角形組成的四邊形進(jìn)行判斷 如果其中一個(gè)三角形的外接圓包含第四個(gè)頂點(diǎn) 則將這個(gè)四邊形的對(duì)角線交換 4 2基于矢量方式構(gòu)建TIN 局部形狀最優(yōu)的三角網(wǎng)可根據(jù)最大最小角度法則建立 Lawson 1977 在由相鄰三角形構(gòu)成的凸四邊形中 交換四邊形的兩條對(duì)角線 不會(huì)增加這兩個(gè)三角形六個(gè)內(nèi)角的最小值 六個(gè)內(nèi)角中最小的最大 最優(yōu) 局部最優(yōu)方法 LOP 交換凸四邊形的對(duì)角線 六個(gè)內(nèi)角中最小的最大 得到更接近等邊的三角形 等角性更好 a 新點(diǎn)插入 b 對(duì)角線交換 c 三角網(wǎng)LawsonLOP交換的完成 4 2基于矢量方式構(gòu)建TIN 隨著近幾年計(jì)算機(jī)的存儲(chǔ)和計(jì)算能力的提高 人們把在矢量環(huán)境中難以解決的問題轉(zhuǎn)化到柵格環(huán)境中來(lái)解決 基于柵格方式的Delaunay三角形算法是嚴(yán)格按照Voronoi圖和Thissen多邊形定義來(lái)實(shí)現(xiàn)的 首先 根據(jù)Voronoi圖的定義求取Thissen多邊形 在Thissen多邊形基礎(chǔ)上構(gòu)建Delaunay三角形 基本思路 首先進(jìn)行矢量 柵格轉(zhuǎn)換 在柵格距陣中求取Voronoi圖 最后從Voronoi圖中提取Delaunay三角形 4 3基于柵格方式構(gòu)建TIN 1 矢量 柵格轉(zhuǎn)換 4 3基于柵格方式構(gòu)建TIN 2 計(jì)算Voronoi圖在二值圖象環(huán)境中 Voronoi圖可以采用圖像減薄 侵蝕 變換獲取 以圖2中 b 圖像為例 圖像取補(bǔ)后進(jìn)行減薄運(yùn)算 圖3 a 直到求出Voronoi圖 然后再進(jìn)行柵格矢量變換 獲取矢量的Voronoi圖 圖3 b 4 3基于柵格方式構(gòu)建TIN 3 由Voronoi多邊形求取Delaunay三角形根據(jù)Voronoi圖與Delaunay三角形相互間的幾何對(duì)偶關(guān)系 建立鄰近多邊形間的點(diǎn)的Delaunay三角形 圖4求取Delaunay三角形 4 3基于柵格方式構(gòu)建TIN 給定的各種點(diǎn)線 由離散點(diǎn)生成的泰森多邊形 由離散點(diǎn)生成的Delaunay三角形 等高線補(bǔ)影象的骨架化 4 3基于柵格方式構(gòu)建TIN 1基于矢量方式約束條件下TIN的構(gòu)建Delaunay三角網(wǎng)建立起來(lái) 便可加入預(yù)先給定的約束線段以完成帶約束條件的Delaunay三角網(wǎng)的構(gòu)建 當(dāng)新的約束線段加入時(shí) 通過搜索約束線段的相交三角網(wǎng)及相交點(diǎn) 現(xiàn)有的Delaunay三角網(wǎng)在局部范圍內(nèi)被更新與加密 4 4約束條件的TIN生成 多對(duì)角線交換循環(huán)算法對(duì)每一條地性線或其它約束線段檢測(cè)其在基本網(wǎng)中是否存在 如果不存在 則使用 多對(duì)角線交換循環(huán)算法 加入網(wǎng)中 如果存在 則不須加入 多對(duì)角線交換循環(huán)算法 的基本思想是從起始點(diǎn)出發(fā) 對(duì)遇到的每條對(duì)角線的可交換性進(jìn)行判斷 可交換就交換 不可交換就判斷下一條 到達(dá)最后一條對(duì)角線后 第一輪交換結(jié)束 然后從頭再來(lái) 開始下一輪 直到將約束邊嵌入為止 4 4約束條件的TIN生成 4 4約束條件的TIN生成 2基于柵格方式約束條件下TIN的構(gòu)建與在矢量環(huán)境中明顯不同 在柵格環(huán)境構(gòu)建約束條件的TIN主要是考慮的約束條件次序 基于矢量方式約束條件下構(gòu)建TIN 是先建立離散點(diǎn)Delaunay三角形 然后再考慮約束條件 與此相反 在柵格環(huán)境中是先考慮約束條件 然后建立三角網(wǎng) 核心問題是在柵格環(huán)境中如何對(duì)約束邊編碼 如何柵格化 矢量數(shù)據(jù)柵格化所遵循的原則與基