基于二叉樹的幾何圖形拓撲運算

蔡琪

摘要：該文提出了一種基于二叉樹的幾何圖形拓撲處理算法，實現幾何圖形間的精確處理。并能有效解決大多數邊界問題，同時可以按需求設定不同的精度。

關鍵詞：二叉樹；拓撲運算；邊界問題

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）34-8191-03

隨著Web技術的發展，越來越多的應用被從傳統的PC端移植到Web端，用戶只需要通過Web瀏覽器就可以得到所需要的服務。這些Web上的應用不僅方便了用戶，也使得自身變得越來越普及。例如百度地圖每天的定位請求數就達20億以上，可見其用戶規模。而百度地圖這類應用僅僅是WebGis中的一項小功能，而WebGis同樣在在城市規劃，交通規劃提供許多功能支持。

WebGis是Web上的地理信息系統，其功能主要是對空間上采集的地理信息進行分析與處理，例如通過人口統計所得的數據得到的城市人口密度分布圖，通過道路車輛統計所得的道路交通流量圖。這類信息通常需要通過對采集信息進行精確的拓撲計算得出，例如要計算一個下圖紅線劃定范圍內的建筑面積，就需要拿紅色區域和A，B，C，D四塊區域進行邏輯判斷，同時計算相交區域面積。而當前一些開源的拓撲運算庫如Dotspatial等，存在著邊界問題處理不好，精度值無法確定，效率不高等一些問題。

1 關鍵技術

1） 多邊形的二叉樹分割

對平面任意閉合多邊形，若指定其包圍區域為內側，則邊界與內側相對的另外一側為外側，若要判斷內外側，一般通過多邊形的方向進行判斷。通常多邊形的方向分為順時針與逆時針，沿多邊形方向，一般定義左側為內側，右側為外側，所以若指定包圍的閉合區域為內側，則多邊形為逆時針。……