欒磊洋 徐鯤 符季穎

（北京建筑大學(xué)測繪與城市空間信息學(xué)院，北京 100044）

線化簡是有選擇性地去掉曲線上的點(diǎn)，并對(duì)其它點(diǎn)進(jìn)行合理位移，在化簡點(diǎn)要素的條件下很好地保持線要素的形態(tài)，最終實(shí)現(xiàn)要素在客戶端高效的多尺度漸進(jìn)式可視化。本文提出一種顧及節(jié)點(diǎn)約束的境界線與道路拓?fù)錄_突處理方法，通過幾何重構(gòu)、建立多尺度層次結(jié)構(gòu)判斷不同類型線要素產(chǎn)生沖突未顧及的偽節(jié)點(diǎn)與特殊節(jié)點(diǎn)，通過得到的約束節(jié)點(diǎn)集合對(duì)Douglas-Pecker 與Li-Openshaw 結(jié)合算法進(jìn)行改進(jìn)，試驗(yàn)結(jié)果表明，該方法能夠在避免拓?fù)錄_突的情況下實(shí)現(xiàn)境界線要素的化簡。

1 境界線要素?cái)?shù)據(jù)概況

境界線數(shù)據(jù)形態(tài)表達(dá)有以下特征，如圖1 所示。

第一，國界線與省界線、省界線與市界線不存在重疊關(guān)系。

第二，省界、市界間重疊部分均有2 條重合且方向相反的境界線。

圖1 數(shù)據(jù)形態(tài)表達(dá)

2 境界線要素拓?fù)錄_突處理方案設(shè)計(jì)

2.1 拓?fù)錄_突產(chǎn)生原因

拓?fù)潢P(guān)系沖突指空間對(duì)象間的拓?fù)潢P(guān)系存在不合理性，常見的拓?fù)潢P(guān)系沖突包括存在懸點(diǎn)、多次相交以及部分重疊等情況。在境界線要素化簡過程中，其位置和形態(tài)可能會(huì)產(chǎn)生拉伸、扭曲等狀況，從而導(dǎo)致化簡后境界線要素與其他類型線要素產(chǎn)生拓?fù)錄_突。

2.2 拓?fù)錄_突類型

境界線與道路的交叉點(diǎn)（以下簡稱偽節(jié)點(diǎn)）與特殊節(jié)點(diǎn)在線要素化簡過程中存在重要的意義，偽節(jié)點(diǎn)、特殊節(jié)點(diǎn)的位置是需要重點(diǎn)考慮的問題，通過對(duì)比分析，總結(jié)得到以下4 種拓?fù)潢P(guān)系變化類型：（1）線線相交于一點(diǎn)化簡后變?yōu)榫€線相離。（2）線線相交于多點(diǎn)化簡后變?yōu)榫€線相交于一點(diǎn)。（3）線線相離化簡后變?yōu)榫€線相交于一點(diǎn)。（4）線線相離化簡后變?yōu)榫€線相較于多點(diǎn)。

2.3 拓?fù)錄_突判別方法

2.3.1 偽節(jié)點(diǎn)的判別

根據(jù)圖2(a)可知，道路線與境界線相交處并無可選點(diǎn)，可以通過打斷重構(gòu)的方法，在相交處打斷形成新的交點(diǎn)(“偽節(jié)點(diǎn)”)坐標(biāo)，如圖2(b)所示，重構(gòu)公式（1）如下。

圖2 偽節(jié)點(diǎn)判別

2.3.2 特殊節(jié)點(diǎn)的判別

由于道路經(jīng)過多個(gè)省、市、縣，以道路與市界線的交點(diǎn)將道路分段，以化簡前分段道路與對(duì)應(yīng)市界線這一尺度的拓?fù)潢P(guān)系為第一狀態(tài)，化簡后分段道路與對(duì)應(yīng)市界線的尺度的拓?fù)潢P(guān)系為第二狀態(tài)。以2 個(gè)或2 個(gè)以上狀態(tài)建立多尺度層次結(jié)構(gòu)，檢測某一路段2 個(gè)或者2 個(gè)以上狀態(tài)空間關(guān)系的一致性即可判斷哪一路段存在化簡沖突。其中以道路與市級(jí)境界線的交點(diǎn)為分段點(diǎn)建立多尺度層次結(jié)構(gòu)，如表1 所示。

2.4 融合Douglas-Pecker 和Li-Openshaw 的改進(jìn)算法

融合Douglas-Pecker 和Li-Openshaw 的改進(jìn)算法的計(jì)算流程如下：

2.4.1 以境界線要素某一節(jié)點(diǎn)為起始點(diǎn)，采用Douglas-Pecker 算法開始化簡，根據(jù)設(shè)定的綜合閾值D，根據(jù)下式逐一判斷線要素節(jié)點(diǎn)的距離值d，將滿足閾值條件的節(jié)點(diǎn)進(jìn)行保留，不滿足閾值D 的節(jié)點(diǎn)在刪除前要考慮前文提及的約束節(jié)點(diǎn)的情況，根據(jù)增加的屬性信息判斷是否屬于約束節(jié)點(diǎn)，若為約束節(jié)點(diǎn)，則進(jìn)行保留，若為待簡化節(jié)點(diǎn)，根據(jù)化簡策略，不同時(shí)、連續(xù)化簡兩個(gè)相鄰點(diǎn)，考慮該節(jié)點(diǎn)的前一個(gè)節(jié)點(diǎn)是否被化簡，若前一個(gè)節(jié)點(diǎn)被保留，則可刪除該節(jié)點(diǎn)，若前一個(gè)節(jié)點(diǎn)被刪除，則該節(jié)點(diǎn)應(yīng)繼續(xù)保留，依次循環(huán)視域范圍內(nèi)所有的節(jié)點(diǎn)，直到最后一個(gè)節(jié)點(diǎn)。

表1 多尺度層次結(jié)構(gòu)

2.4.2 根據(jù)下式（2）計(jì)算出圓形最小可視目標(biāo)SVO（smallest visual object）的尺寸R。

圖3 改進(jìn)算法

2.4.3 對(duì)于采用D-P 算法化簡后的境界線要素的節(jié)點(diǎn)生成的新的曲線，以任意一段曲線的起始端點(diǎn)為圓心，R 為直徑，應(yīng)用Li-Openshaw 算法進(jìn)行境界線要素的化簡，以某一段線段為例，首先根據(jù)約束節(jié)點(diǎn)的屬性信息判斷該線段上屬于分界點(diǎn)類型約束節(jié)點(diǎn)，以分界點(diǎn)前后兩個(gè)節(jié)點(diǎn)為基礎(chǔ)，對(duì)曲線進(jìn)行分段處理，逐次對(duì)分段曲線進(jìn)行化簡；其次，當(dāng)以R 為半徑交曲線線段于某一點(diǎn)時(shí)，首先判斷園內(nèi)是否存在約束節(jié)點(diǎn)，若存在，則跳過Li-Openshaw 算法對(duì)該點(diǎn)的化簡，接下來以約束節(jié)點(diǎn)作為圓心，以R 為直徑，繼續(xù)對(duì)境界線進(jìn)行化簡；若不存在，應(yīng)用Li-Openshaw 算法取圓心與相交點(diǎn)的中心作為新的節(jié)點(diǎn)，以相交點(diǎn)為圓心，R 為半徑繼續(xù)進(jìn)行曲線的化簡，循環(huán)化簡直至最后一段曲線被化簡完成。

2.4.4 對(duì)于曲線上節(jié)點(diǎn)分布較為密集的區(qū)域，以二分之一R或者三分之一R 對(duì)境界線要素進(jìn)行化簡；對(duì)于曲線上節(jié)點(diǎn)分布較為稀疏的區(qū)域，以2R 或者3R 對(duì)境界線要素進(jìn)行化簡，甚至直接跳過該區(qū)域。

2.4.5 至此，化簡完成。

如圖3 所示，其中R 為圓形最小可視目標(biāo)SVO 的尺寸，R1代表節(jié)點(diǎn)到前后節(jié)點(diǎn)連線的最短距離，i，j 為計(jì)數(shù)單位。

采用改進(jìn)算法對(duì)境界線要素進(jìn)行化簡后，與Douglas-Pecker算法、Li-Openshaw 算法進(jìn)行比較。如圖4 所示，采用傳統(tǒng)化簡方法導(dǎo)致化簡后境界線與道路線拓?fù)潢P(guān)系發(fā)生變化，采用本文方法可避免產(chǎn)生拓?fù)溴e(cuò)誤。

圖4 改進(jìn)算法化簡效果

3 結(jié)論

本文提出一種顧及節(jié)點(diǎn)約束的境界線要素化簡方法，設(shè)計(jì)了針對(duì)境界線要素化簡后與其它類型線要素存在拓?fù)錄_突的化簡方案，該方案首先分析拓?fù)錄_突的產(chǎn)生原因以及判別方法；其次，對(duì)視域內(nèi)線要素節(jié)點(diǎn)采用幾何重構(gòu)、多尺度層次結(jié)構(gòu)等方法進(jìn)行判別；最后，采用融合Douglas-Pecker 和Li-Openshaw 的改進(jìn)算法對(duì)視域內(nèi)線要素進(jìn)行化簡。結(jié)果表明，該方案很好地避免了境界線與道路線化簡后存在的拓?fù)錄_突，并且在拓?fù)潢P(guān)系一致性的條件下，保證化簡前后線狀要素的整體形態(tài)。