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