多邊形-弧段拓撲數據結構

多邊形-弧段拓撲數據結構

本文討論如何從一系列按任意順序和任意方向數位化的鏈,組成完整拓撲多邊形網路結構的數據組織方法。這種數據結構能夠處理湖和島嶼在任何一級多邊形網路中的嵌套問題,能檢查奇異多邊形和“死點”,能自動或半自動地將非空間屬性數據與多邊形連線起來,並全面支持鄰域關係的搜尋等。

下面討論如何從一系列按任意順序和任意方向數位化的鏈,組成完整拓撲多邊形網路結構的數據組織方法(上圖)。這種數據結構能夠處理湖和島嶼在任何一級多邊形網路中的嵌套問題,能檢查奇異多邊形和“死點”,能自動或半自動地將非空間屬性數據與多邊形連線起來,並全面支持鄰域關係的搜尋等。

前面討論過的簡單多邊形數據結構經常要求數據輸入方法必須滿足數據結構要求,從而給數據輸入和數據結構最佳化處理帶來一些問題。因此,把數據輸入和數據結構分成兩個單獨的處理過程是更加有效的方法。為了建立這樣的數據結構,只需對數據輸入作兩種假設:

①多邊形邊界已按鏈或弧編碼;

⑦用以連線圖形數據與屬性數據的多邊形名稱則以每個多邊形內某處可識別的點實體的形式數位化。在這種假設條件下,組成完整拓撲多邊形數據結構的步驟如下:

1.將鏈連線成邊界網路:首先按鏈的尺度(最大最小x,y坐標)存儲多邊形的鏈,使各條能按拓撲關係彼此集中在一起,同時在數據檔案中存儲在一起,從而節省查找相鄰鏈的時間。然後對這些鏈進行檢查,看哪些其它鏈與它們相交,把各交點存儲在組成這些點的所有鏈的後面.並把鏈的數據記錄延長以包括指針和角度。如果鏈不是在端點相接而是在中間相交,就會自動切成新鏈和形成新節點.同時建立新的指針。有些地理信息系統不能自動形成節點,需用手工輸入。雖然手工輸入節點及指針可以減少計算處理時間,但會產生非標準的數據格式和資料庫中的多餘數據.同時輸入工作量也大。

2.檢查多邊形是否閉合:檢查多邊形閉合與否的方法很簡單,即掃描修改過的鏈記錄,看每條鍍是否有指向其它鏈和從其它鏈指向它。如果每條鏈都至少有一個指針指向其它鏈和一個從其它鏈指向它的指針,則說明多邊形網路中的各多邊形是閉合的。如果組成島的鏈只有一條,它的指針就指向它本身。某鏈經檢查不合要求時,系統會以特殊的方法顯示出來.讓操作員知道某些鏈有問題,並決定是否去除或修改。

3.連線各鏈組成多邊形:組成多邊形的第一步是建立多邊形網員外沿線組成的包絡多邊形(實體),這個包絡體由以下記錄內容組成:

①唯一標識;

①唯一的編碼,這個編碼說明該多邊形是包絡多邊形;

①環形指針;

①指向邊界鏈的指針列表

①包絡多邊形的面積;

①範圍(包圍包絡多邊形的矩形的最大最小x,y坐標值)。

此包絡多邊形用戶是看不見的,它的唯一作用是建立多邊形網路的拓撲結構。

包絡多邊形按如下方法建立:

在多邊形網的最外沿選擇一個點作為起始點,按順時針方向沿著邊界查找下一個節點。原則是選取每一個節點處的最左邊一條鏈,並以這條鏈的另一端作為起點查找最左邊的鏈,以此類推。選出的鏈的識別符和其它有關據需記錄和存儲,同時還要建立特殊標記來表明該鏈已被查找一次。第二步是一旦外沿線(包絡多邊形)建立起來以後,就建立其它多邊形。重新從建立包絡多邊形的起點開始,仍按順時針方向查找,但不是找最左邊的鏈而是有邊的鏈。查找的同時還要記錄各條鏈被查找的次數,如某條鏈已被查找兩次就不再查找,回到起點就表明一個多形查找結束。查找和記錄鏈的同時還要檢查角度的累積值,如果總和不等於360度,則說明該節點處數位化有錯誤,而且會形成奇異多邊形。雖然奇異多邊形在第一階段中已檢查並濾除。但如果一條錠必須連線到手工輸入的點上時,這一檢查還是必要的。與包絡多邊形一樣,每個多邊形實體也包括如下信息:

①唯一的標識符;

①多邊形編碼;

①包絡多邊形到該多邊形的環形指針針記錄中去;

①所有邊界鏈列表(同時,多邊形的識別符應寫入鏈的記錄中去);

①指向多邊形網中鄰接多邊形的指針;

①包絡多邊形的矩形的最大最小坐標值。

這些工作都完成後,用同樣的過程查找下一個多邊形,但下一個多邊形必須位於同一多邊形網中,且屬分級結構中的同一級。直到每個多邊形都生成後才結束查找工作。當最後一個多邊形查找完畢時,就將它的指針指回到包絡多邊形。這樣就能保證每一條鏈都與兩個多邊形有關。

相關詞條

熱門詞條

聯絡我們