計算幾何：空間數據處理算法（簡體書）

計算幾何是研究幾何圖形的計算機存儲、表達、處理和分析等的理論與技術。而地理信息系統（GIS）處理的主要對象是空間數據（圖形數據）。因此，如何運用計算幾何的基本理論、方法、算法等為空間數據處理服務，已成為近年來GIS領域研究的焦點問題之一。《計算幾何：空間數據處理算法》首先介紹計算幾何基元及算法，然後依據計算幾何在空問數據處理中的不同作用，分別論述空間分析算法、空間查詢算法、空間數據可視化算法、空間關係表達算法及地圖自動綜合算法。本書注重介紹算法的基本原理與具體的實現過程。其論述深入淺出、圖文並茂，便於讀者理解與掌握。本書適合於地理、地圖、測量、城建等領域的廣大研究人員和技術工作者閱讀參考，也可作為地理學科、測繪學科及其他相關學科本科生、研究生的教學用書。．

《計算幾何:空間數據處理算法》適合于地理、地圖、測量、城建等領域的廣大研究人員和技術工作者閱讀參考，也可作為地理學科、測繪學科及其他相關學科本科生、研究生的教學用書。

前言
第1章 緒論
1.1 計算幾何的概念
1.2 計算幾何的緣起與發展
1.3 從空間數據處理到計算幾何算法
1.4 本書的組織和約定
主要參考文獻
第2章 計算幾何基元及算法
2.1 多邊形
2.2 凸殼
2.3 Voronoi圖和Delaunay三角網
2.4 曲線擬合
2.5 圖論
主要參考文獻
第3章 空間分析與空間查詢算法
3.1 空間目標捕捉算法
3.2 疊置分析算法
3.3 緩衝區分析算法
3.4 空間網絡分析算法
3.5 空間查詢算法
主要參考文獻
第4章 空間數據可視化算法
4.1 等值線引繪算法
4.2 圖形開窗算法
4.3 地圖矢量符號（庫）算法
4.4 地圖注記自動配置算法
4.5 曲線光滑算法
主要參考文獻
第5章 空間關係表達算法
5.1 空間距離關係計算
5.2 空間拓撲關係計算
5.3 拓撲多邊形自動生成算法
5.4 空間方向關係計算
5.5 多尺度地圖空間相似關係
主要參考文獻
第6章 地圖自動綜合算法
6.1 點群綜合算法
6.2 等高線綜合算法
6.3 道路網綜合算法
6.4 居民地綜合算法
主要參考文獻
第7章 結束語
．

等高線樹具有許多方面的應用。如在數字高程模型（Digital Elevation Model，DEM）的生成中顧及地性線（山脊線、山谷線）時，等高線樹可以提供等高線之間的關系信息，由此能夠建立相鄰等高線之間的坡降線，使得以隱含的方式顧及地性結構成為可能。平面上利用一組等高線的有機聯系來表達地貌的立體形態，包括組成地貌基本形態的山頂、山脊、斜坡、鞍部和谷地等。同樣，通過分析等高線本身組成地貌結構的基本點和線，如山頂、山脊線、斜坡變換線和谷地線等地貌結構點和結構線，對實施等高線圖形綜合具有實際意義。
要推導出等高線之間的拓撲關系，目前較好的有兩種方法。第一種方法是毋河海（1995）提出的，基本思想是：建立等高線樹的實質是確定父層等高線對子層等高線的包含關系；因此，可以建立自上而下的、樹根朝上的自然狀等高線樹。包含是相對于封閉區域而言的。所以，為了確定等高線的包含關系，關鍵是如何形成父層等高線的封閉多邊形圖形，由此可以導出它們所包含的子層等高線多邊形。基本實現手段是：采用等高線圖形設色分類的方法，將同一高程的等高線圖形進行分類，進而用“分而治之”的方法逐一解決，由此建立等高線樹。第二種方法是張琳琳等（2005）在第一種方法基礎上的發展，她們吸取了前者計算圖廓距的方法，不同的是沒有進行圖形分類，而是利用相鄰3個高程的拓撲關系來消除閉合方向的二義性。
下面結合文獻成果（毋河海，1995；張琳琳等，2005）討論等高線樹生成的方法。
1.等高線樹構造問題的分析
二維平面上兩物體之間的空間關系一般有3種：拓撲關系、度量關系和順序關系。等高線的空間關系主要指其拓撲關系。閉合的等高線可以看作面；面與面之間的拓撲關系有包含和相離兩種。只要確定了閉合等高線之間的這種拓撲關系，就會形成如圖6.13（a）所示的相同高程的等高線相離、不同高程的等高線相嵌套的形式。人們往往憑經驗就可從等高線的圖形上看出它所要表述的空間關系；而計算機語言的表達是盲視的，它在計算機中表現為數據的存儲與組織方式，并且蘊含了屬性信息，如高程、首曲線、計曲線等，因此等高線的空間關系最好通過建立等高線樹來實現[圖6.13（b）]。
既然閉合的等高線可以看作一個面，由此，線與線的關系就可轉換為面與面的關系；面與面關系的判斷在計算機中容易實現。因此圖幅中各種類型的等高線如何形成多邊形（即面）成為問題的關鍵。