道路網(wǎng)絡(luò)示意圖的多邊形生長(zhǎng)算法

張 藍(lán)，李佳田，徐 珩，賀飛越，徐燕竹，王紅梅

昆明理工大學(xué)國(guó)土資源工程學(xué)院，云南 昆明650093

1 引 言

網(wǎng)絡(luò)示意性地圖（network schematic map）使用抽象的圖形符號(hào)來(lái)表示物體，著重展示網(wǎng)絡(luò)自身結(jié)構(gòu)，而忽略其他信息。在地圖服務(wù)領(lǐng)域，示意圖被廣泛應(yīng)用于公交線路、地鐵線路等公共交通系統(tǒng)。不同于一般地圖，示意性地圖模糊了地理精度，當(dāng)?shù)乩砭鹊闹匾缘陀谶B接、鄰接和相對(duì)位置關(guān)系時(shí)，這種靈活變通的制圖方法是可行且有效的［1］。

地圖示意化具有不同的幾何和美學(xué)準(zhǔn)則，其共同的目標(biāo)是簡(jiǎn)化圖形、保留網(wǎng)絡(luò)信息以及易于理解。繪制網(wǎng)絡(luò)示意圖不僅耗費(fèi)時(shí)間而且需要專業(yè)的制圖人員。當(dāng)網(wǎng)絡(luò)規(guī)模較大或是需要經(jīng)常更新時(shí)，手工繪制或者使用繪圖軟件就顯得不切實(shí)際。針對(duì)示意圖的自動(dòng)生成，存在相關(guān)研究工作，整體思路是“化簡(jiǎn)＋匹配”。文獻(xiàn)［2］使用迭代的方法簡(jiǎn)化路徑并將其離散為線段，根據(jù)線段轉(zhuǎn)角及相鄰線段長(zhǎng)度建立價(jià)值函數(shù)，以判定形狀的適度性；文獻(xiàn)［3—7］采用 Douglas－Peucher算法對(duì)路徑進(jìn)行化簡(jiǎn)，并通過(guò)基于梯度下降的優(yōu)化算法迭代移位約束網(wǎng)絡(luò)路徑線段的方位；近似的還有文獻(xiàn)［8—9］中的研究；文獻(xiàn)［10］基于動(dòng)態(tài)分段，將延續(xù)性好的道路合并為一條路徑，依據(jù)重要度由高到低以路徑為單元對(duì)道路網(wǎng)進(jìn)行示意化，生成圖形具有良好的路徑延續(xù)性且更加簡(jiǎn)化。以上算法以路徑為單位對(duì)網(wǎng)絡(luò)進(jìn)行示意化，提出一系列約束優(yōu)化路徑線段位置，并不能嚴(yán)格限定輸出路徑方向，同時(shí)在移動(dòng)頂點(diǎn)方位時(shí)要對(duì)相關(guān)路徑上所有頂點(diǎn)的坐標(biāo)值進(jìn)行修正，需進(jìn)行大量的計(jì)算來(lái)維持網(wǎng)絡(luò)拓?fù)湟恢滦?。文獻(xiàn)［11—12］提出了一種相對(duì)簡(jiǎn)單且有效的示意圖生成算法，將頂點(diǎn)定位在其原始位置，并以兩段或三段限制方向的線段替代輸入路段，然后依照連接順序自上而下依次排列各線段。然而其未提供處理路徑?jīng)_突的方法，如果輸入路徑不符合設(shè)定的示意化條件將不會(huì)被示意化，且生成圖形不夠簡(jiǎn)化。

路網(wǎng)規(guī)模較大情況之下，路徑的相互交錯(cuò)會(huì)形成諸多閉合多邊形（道路網(wǎng)眼）。從拓?fù)渖蟻?lái)講，閉合多邊形相較于非閉合的線段（懸垂路段）要重要得多，因?yàn)閼掖孤范尾⒉粫?huì)對(duì)網(wǎng)絡(luò)的連通性造成影響［13－14］。與此同時(shí)，閉合多邊形具有相對(duì)獨(dú)立性，以閉合多邊形為單位劃分網(wǎng)絡(luò)，那么對(duì)于單個(gè)多邊形來(lái)說(shuō)，其余多邊形均在其外部。鑒于此，本文以閉合多邊形為基本單位，通過(guò)依次將其示意化圖形映射至當(dāng)前映射圖形的外部空間，對(duì)網(wǎng)絡(luò)空間進(jìn)行再分配生成規(guī)范的網(wǎng)絡(luò)示意圖。本算法簡(jiǎn)化了拓?fù)錂z查過(guò)程，對(duì)于一般復(fù)雜道路網(wǎng)絡(luò)示意圖生成具有較強(qiáng)實(shí)用性。

2 理論基礎(chǔ)與約束過(guò)程

2.1 基本概念

多邊形［15］：平面上一條非自相交的有向封閉曲線形成的圖形為多邊形。將曲線分割成線段a1、a2、...、an，分割點(diǎn)位于多邊形的鄰接點(diǎn)。線段a＝（u，v）是頂點(diǎn)u與v的有序偶對(duì)，稱u與v是邊a的端點(diǎn)，u為起點(diǎn)，v為終點(diǎn)，a是u和v的關(guān)聯(lián)線段。

多邊形圖［15－16］：多邊形圖G由一系列簡(jiǎn)單多邊形路徑構(gòu)成，這些多邊形互不相交，除非享有共同邊。多邊形圖不包含任何未成回路線段，多邊形間具有鄰接、相離與內(nèi)含3種拓?fù)潢P(guān)系。

度［17］：圖G中與頂點(diǎn)v關(guān)聯(lián)的線段的數(shù)目稱為v在G中的度（degree），記作deg（v）。度為0的頂點(diǎn)為孤立點(diǎn)，度為1的頂點(diǎn)為懸掛點(diǎn)，與懸掛點(diǎn)關(guān)聯(lián)的線段為懸掛邊。

多邊形和：多邊形圖G1與多邊形圖G2的并集中去掉G1與G2的交集，所得到的圖稱作G1與G2的多邊形和，記作G1⊕G2，即

2.2 約束過(guò)程

參照建立網(wǎng)絡(luò)示意圖的一般約束［18－19］，建立本算法示意化的約束條件：①拓?fù)湟恢?，目?biāo)網(wǎng)絡(luò)應(yīng)與輸入網(wǎng)絡(luò)保持拓?fù)湟恢?；②方向?guī)范，示意化路徑方向應(yīng)僅包含水平、垂直或?qū)蔷€方向；③路徑長(zhǎng)度適宜，目標(biāo)網(wǎng)絡(luò)路徑長(zhǎng)度應(yīng)大于某個(gè)最小限制以使圖形清晰；④路徑無(wú)重疊，非相交路徑間距應(yīng)大于某個(gè)最小距離限制以使圖形清晰；⑤示意化后的路徑方向應(yīng)盡可能地接近其原始方向。

本文使用規(guī)則網(wǎng)格空間來(lái)存放目標(biāo)網(wǎng)絡(luò)示意圖，將示意化問(wèn)題描述為：如何滿足以上約束條件將原始網(wǎng)絡(luò)圖形映射至規(guī)則網(wǎng)格空間（R2→Z2）。定義頂點(diǎn)的位置為網(wǎng)格，每個(gè)頂點(diǎn)占據(jù)一個(gè)網(wǎng)格，同一網(wǎng)格只能被一個(gè)頂點(diǎn)占據(jù)；路徑為直線，且只能平行于網(wǎng)格線，即路徑方向固定為90°及其倍數(shù)（僅在處理重復(fù)路徑時(shí)使用45°線）；路徑之間不能出現(xiàn)交叉或重疊，間距最小為一個(gè)網(wǎng)格。

圖1展示了原始網(wǎng)絡(luò)向目標(biāo)網(wǎng)格空間映射的整個(gè)流程。其主要思路即分離原始網(wǎng)絡(luò)非閉合線段得到多邊形圖，通過(guò)多邊形生長(zhǎng)算法將多邊形圖映射至網(wǎng)格空間，然后恢復(fù)分離點(diǎn)線得到完整的網(wǎng)絡(luò)示意圖。上述過(guò)程中，重點(diǎn)在于如何將多邊形圖依照約束映射至規(guī)則網(wǎng)格空間。多邊形圖的映射過(guò)程就像起始多邊形這顆種子不斷地聚合相鄰的多邊形，因此，將這種算法稱為“多邊形生長(zhǎng)算法”。

圖1 網(wǎng)絡(luò)映射流程圖Fig.1 Flow chart of network mapping

3 多邊形生長(zhǎng)算法描述

3.1 多邊形圖提取

原始地理數(shù)據(jù)中不存在多邊形這種幾何類型，首先對(duì)數(shù)據(jù)進(jìn)行處理，提取得到多邊形圖。

（1）將網(wǎng)絡(luò)看作圖結(jié)構(gòu)G＝（V，E），建立頂點(diǎn)－頂點(diǎn)、頂點(diǎn)－線段、線段－線段關(guān)聯(lián)矩陣。

（2）簡(jiǎn)化對(duì)拓?fù)潢P(guān)系無(wú)影響的圖形結(jié)構(gòu)。若一對(duì)頂點(diǎn)連接幾條不同的線段則將其簡(jiǎn)化為一條，若線段的兩個(gè)端點(diǎn)是同一個(gè)頂點(diǎn)，則刪除此線段。

（3）分離懸掛點(diǎn)和線段。迭代分離圖中deg（v）＝1的點(diǎn)及其關(guān)聯(lián)線段分別記入鏈表結(jié)構(gòu)SprtPointList與SprtLineList。

（4）分離非相鄰多邊形組。若存在空間關(guān)系上分離或包含的多邊形（組），則需將其分離為獨(dú)立多邊形組分別進(jìn)行映射。通過(guò)查找無(wú)法構(gòu)成多邊形的線段來(lái)分離多邊形組，如圖2所示，若多邊形（組）A與B非相鄰，則連接線段序列（v1，v2）不存在于任何多邊形中。分離后的多邊形組去除連接線段序列后得到的圖形即為多邊形圖。

圖2 非相鄰多邊形組Fig.2 Non－adjacent polygons

（5）依次遍歷多邊形圖中的頂點(diǎn)提取圖中所有多邊形。使用左轉(zhuǎn)算法［20］提取多邊形，簡(jiǎn)單描述為以任意頂點(diǎn)o為坐標(biāo)原點(diǎn)，自o起，選擇與點(diǎn)相通的任意一條相鄰線段（o，a），然后，以a為原點(diǎn)，獲得a點(diǎn)所有關(guān)聯(lián)線段的方位角，記方位角的最大值為αmax，最小值為αmin。如果αao為最小方位角，則取αmax的邊為下一搜索線段；如果αao不是最小方位角，取次小于αao的邊為下一搜索線段。依次向下搜索直到回到o點(diǎn)，得到一個(gè)多邊形，這個(gè)構(gòu)成順序是逆時(shí)針的。剔除無(wú)效的多邊形（頂點(diǎn)構(gòu)成順序是順時(shí)針）、刪除重復(fù)多邊形，將無(wú)重復(fù)的多邊形組放入BaseDList鏈表。

3.2 多邊形閉合

記多邊形Dd中已映射頂點(diǎn)集為Vloc（v1，v2，…，vi），已 映 射 線 段 集 合 為Eloc（（v1，v2），…，（vi－1，vi）），Dd中未映射頂點(diǎn)集為Vunloc（vj，…，vm），未映射線段集合為Eunloc（（vi，vj），…，（vm，v1）），則Dd＝｛Eloc，Eunloc｝＝（（v1，v2），…，（vi，vj），…，（vm，v1））。Dd映射至目標(biāo)空間即調(diào)節(jié)Vunloc各點(diǎn)以使映射圖形滿足約束并閉合。定義規(guī)則網(wǎng)格空間Z2方向集合為O＝｛oi，i＝1，…，8｝，其中1—8分別表示右、右上、上、左上、左、左下、下、右下8個(gè)方向。若線段（u，v）的實(shí)際方向or為u指向v，則其在Z2的方向oz為與or偏差最小的規(guī)范方位，即oz＝｛oi，min｜or－oi｜｝。初始化線段（u，v）的長(zhǎng)度l（u，v）＝1。由于各線段的方向長(zhǎng)度在Z2中均發(fā)生了改變，初始化的映射圖形顯然不能閉合。為了使多邊形在Z2閉合同時(shí)滿足約束，須使各邊方向在順序上可行（如向上的線段后不能是向下的線段），同時(shí)對(duì)應(yīng)方向線段總長(zhǎng)度相等，即

式（2）中rem表示求余數(shù)，將式（3）展開(kāi)，得

Vloc中各點(diǎn)位置是不能改變的，因此需要調(diào)節(jié)Eunloc各線段長(zhǎng)度，以適應(yīng)Eloc。一般原則是擴(kuò)大總長(zhǎng)度較小方向各線段長(zhǎng)度使其與相對(duì)方向長(zhǎng)度相等，有兩種特例：

（1）由于s方向不具有未映射線段而導(dǎo)致其對(duì)應(yīng)t方向各待映射邊長(zhǎng)度均為初始值1時(shí)，總長(zhǎng)度仍大于s方向總長(zhǎng)度。采取整體放大Z2所有已定位點(diǎn)坐標(biāo)來(lái)使圖形滿足映射要求，即

（2）由于s方向上沒(méi)有線段而導(dǎo)致圖形無(wú)法閉合。通過(guò)自起始點(diǎn)（vi，vj）逐個(gè)檢索未映映射線的方式，依照逆時(shí)針順序（右－上－左－下），添加輔助線段。

自vi起，依次定位Vunloc各點(diǎn)

需要注意的是，若原始網(wǎng)絡(luò)拓?fù)涑霈F(xiàn)自交叉或者多邊形結(jié)構(gòu)過(guò)于復(fù)雜（如某條邊呈鋸齒狀）則無(wú)法得到正確的映射圖形。

3.3 網(wǎng)絡(luò)網(wǎng)格空間映射

選取BaseDList中任意多邊形作為起始多邊形Dstart。此時(shí)目標(biāo)空間為空，設(shè)置Dstart上一點(diǎn)v0位于坐標(biāo)原點(diǎn)，Dstart（v0，v1，…，vn）為頂點(diǎn)自v0逆時(shí)針順序組成矢量。依照3.2節(jié)所述映射Dstart中各點(diǎn)。矩陣NS記錄網(wǎng)格空間狀態(tài)，若網(wǎng)格（i，j）被占據(jù)則 NS（i，j）＝1，否則為0。記錄當(dāng)前網(wǎng)格空間映射圖形的外輪廓線，outline＝Dstart，逆時(shí)針順序。

圖3 相鄰多邊形映射順序（圖中數(shù)字）Fig.3 Adjacent polygons mapping order（the numbers in the figure）

在現(xiàn)有圖形的基礎(chǔ)上完成其余多邊形的映射。將BaseDList中所有與outline接壤且未被映射的多邊形記入AdjDList，依照其與outline最后交點(diǎn)的順序逆時(shí)針?lè)较颍▓D3）依次定位每個(gè)多邊形Dd。Dd與outline的交集（已確定位置頂點(diǎn)集）為Vloc，Dd中未確定位置頂點(diǎn)集為Vunloc，在完成每個(gè)多邊形的映射后都需要更新outline，outline＝outline⊕Dd。直至AdjDList中所有多邊形都完成映射，清空 AdjDList，將此時(shí)BaseDList中所有與outline接壤且未被映射的多邊形記入AdjDList，重復(fù)上述過(guò)程直至BaseDL－ist中所有多邊形完成映射。

圖形自R2映射至Z2，線段方向固定為水平豎直必然會(huì)出現(xiàn)重疊。對(duì)映射后重疊的線段，通過(guò)平行偏移的方法來(lái)避免重疊。為了保證有足夠的空間進(jìn)行平移，首先將Z2進(jìn)行整體放大（式（4））。水平方向重疊：將a向上平移一格，若平移后與其他線段產(chǎn)生交叉，則恢復(fù)a原位置并將a向下平移一格。豎直方向重疊：將a向左平移一格，若平移后與其他線段產(chǎn)生交叉，則恢復(fù)a原位置并將a向右平移一格。如果重復(fù)線段a中含有已定位點(diǎn)（a＝（vi，vj）或a＝（vm，v1）），通過(guò)添加輔助點(diǎn)來(lái)避免移動(dòng)已定位點(diǎn)（圖4）。

圖4 線段重疊處理Fig.4 Segments overlapping

在處理重疊線段時(shí)添加的單位長(zhǎng)度45°線會(huì)隨目標(biāo)空間一同放大，為了維持目標(biāo)圖形的簡(jiǎn)化與美觀，嘗試將45°線轉(zhuǎn)化為90°線。45°線的產(chǎn)生是由于在處理線段重疊時(shí)添加了輔助頂點(diǎn)va，va有且僅有兩個(gè)相鄰頂點(diǎn)vb和vc。嘗試移動(dòng)va，使其與vb、vc的連線成水平豎直，若目標(biāo)網(wǎng)格未被占據(jù)則將va移動(dòng)至目標(biāo)點(diǎn)，見(jiàn)圖5（a）；若目標(biāo)網(wǎng)格被占據(jù)，直接移動(dòng)會(huì)產(chǎn)生重復(fù)，則依重復(fù)線段方法處理，處理后的45°線最多占用一個(gè)網(wǎng)格，見(jiàn)圖5（b）。

圖5 45°線轉(zhuǎn)化為90°線Fig.5 Convert 45°into 90°

為了滿足映射的需要對(duì)映射空間進(jìn)行整體放大會(huì)帶來(lái)空間浪費(fèi)，并影響圖形美觀。在不影響拓?fù)浣Y(jié)構(gòu)的情況下，以行、列為單位刪除未使用空間以收縮圖形，如圖6中同時(shí)向左平移節(jié)點(diǎn)C、D、E以避免AC、BE過(guò)長(zhǎng)。

分別對(duì)多邊形圖進(jìn)行映射后，組合各多邊形圖。選取復(fù)雜度（∑deg（v），v（G）最高的多邊形圖作為主圖Gmain，將其他多邊形圖G鑲嵌至Gmain。多邊形圖G鑲嵌過(guò)程如下：①映射連接線段，依照拓?fù)溥B接依次映射連接線段組A＝｛a1，a2，...，an｝中各線段至Gmain映射空間Z2main，線段方向?yàn)檎鎸?shí)的方向近似，長(zhǎng)度為1，線段映射空間被占用則放大Z2main；②鑲嵌多邊形圖，因?yàn)橐褜?duì)映射空間進(jìn)行優(yōu)化，所以此時(shí)G的映射空間即為放置其映射圖形的最小空間。將G的映射空間Z2G鑲嵌至連接線段an，若Z2main中空間不足以放置Z2G則放大Z2main（圖7）。依照原始方位將Sprt－LineList中分離的非閉合線段映射至目標(biāo)圖形，至此，得到完整的網(wǎng)絡(luò)示意圖表示。

圖6 收縮圖形優(yōu)化空間分布Fig.6 Shrinking graph to optimize spatial distribution

圖7 組合圖結(jié)構(gòu)Fig.7 Graph structure combination

4 算例與分析

開(kāi)發(fā)環(huán)境為Matlab2012b，試驗(yàn)數(shù)據(jù)為美國(guó)錫安國(guó)家公園部分道路數(shù)據(jù)（圖9（a）），共計(jì)239個(gè)頂點(diǎn)，309條邊。

經(jīng)分離懸掛點(diǎn)71個(gè)，得到圖8（b）所示結(jié)構(gòu)，圖中存在非相鄰的多邊形組（圖8（b）中灰色線條與黑色線條），故將其分離為兩個(gè)獨(dú)立的多邊形組。圖8（c）為主圖Gmain提取得到的多邊形圖，圖8（d）為經(jīng)生長(zhǎng)算法得到的主圖映射圖形。經(jīng)過(guò)組合圖及非閉合線段映射后的最終圖形如圖9（b）所示。

圖8 算法過(guò)程Fig.8 Algorithm process

圖9 試驗(yàn)結(jié)果Fig.9 Experiment result

圖9（b）中所有路段方向都被示意化為水平、垂直或?qū)蔷€方向，且與原始網(wǎng)絡(luò)保持拓?fù)湟恢隆D10展示了原始網(wǎng)絡(luò)以及映射圖形中路段長(zhǎng)度分布情況：①映射圖形路段長(zhǎng)度分布總體上與原始地圖呈現(xiàn)相似性；②原始地圖中相鄰頂點(diǎn)間最大最小距離（直線距離）相差249倍，而在映射圖形中路段長(zhǎng)度最大僅為13個(gè)單位網(wǎng)格；③相較于原始路段長(zhǎng)度，映射圖形路段長(zhǎng)度更加集中于較小長(zhǎng)度。示意化結(jié)果保持了網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，簡(jiǎn)化了圖形，使網(wǎng)絡(luò)表達(dá)清晰，提高了易讀性。

將網(wǎng)絡(luò)空間橫豎20等分，計(jì)算每部分節(jié)點(diǎn)個(gè)數(shù)，結(jié)果如圖11所示。原始網(wǎng)絡(luò)節(jié)點(diǎn)集中在中間，而在映射圖形中節(jié)點(diǎn)分布則較為均勻，可在一定程度上緩解局部節(jié)點(diǎn)集中趨勢(shì)，增加網(wǎng)絡(luò)的易讀性。

圖10 映射前后網(wǎng)絡(luò)路段長(zhǎng)度分布Fig.10 The distribution of network paths length before and after mapping

圖11 映射前后網(wǎng)絡(luò)節(jié)點(diǎn)分布Fig.11 The distribution of network nodes before and after mapping

將文獻(xiàn)［11］試驗(yàn)數(shù)據(jù)進(jìn)行矢量化，并使用本文算法進(jìn)行示意化，與文獻(xiàn)［11—12］提出的兩段替代路徑算法的對(duì)比試驗(yàn)見(jiàn)圖12。文獻(xiàn)［11—12］的算法以路段為單位進(jìn)行示意化，限定頂點(diǎn)位于其原始位置，本文以閉合多邊形為單位進(jìn)行示意化，使頂點(diǎn)位置自適應(yīng)，得到的示意化圖形更為簡(jiǎn)化，拓?fù)浣Y(jié)構(gòu)更加清晰；由于限定頂點(diǎn)位置，文獻(xiàn)［11—12］的算法在局部點(diǎn)線密集區(qū)域不能有效處理路徑?jīng)_突，如圖12（b）中灰色線段未能被示意化。而本文使用45°線及擴(kuò)大映射空間處理局部映射區(qū)域路徑重疊，使符合閉合規(guī)則的所有多邊形均能被有效示意化。

圖12 與Cabello的兩段替代路徑算法的對(duì)比Fig.12 The comparison of our algorithm and Cabello’s

5 結(jié) 論

針對(duì)附有地理信息的復(fù)雜網(wǎng)絡(luò)拓?fù)涫疽鈭D的生成，本文提出了一種基于多邊形生長(zhǎng)的算法。較之于以前的方法，本算法并非使用迭代移位的方法來(lái)優(yōu)化圖形而是基于拓?fù)潢P(guān)系直接定位點(diǎn)線，避免部分解決拓?fù)潢P(guān)系沖突的計(jì)算，同時(shí)這種定位（而非優(yōu)化）的規(guī)則嚴(yán)格地限定了示意圖的路徑方向。試驗(yàn)結(jié)果表明，本算法能夠均衡網(wǎng)絡(luò)路徑長(zhǎng)度及節(jié)點(diǎn)分布，對(duì)網(wǎng)絡(luò)空間分布進(jìn)行一定優(yōu)化，使生成的圖形更加清晰、易讀。

本算法仍有許多可改進(jìn)的地方。目前算法僅考慮了節(jié)點(diǎn)之間的部分方向信息，而沒(méi)有參考圖形的長(zhǎng)度信息，可以看出示意化圖形在形狀上存在較大變形，如何在盡量簡(jiǎn)化圖形的同時(shí)更好地維持圖形相似性，是下一步研究的重點(diǎn)。

［1］ MONMONIER M S.How to Lie with Maps［M］.Chicago：The University of Chicago Press，1996.

［2］ BARKOWSKY T，LATECKI L J，RICHTER K F.Schematizing Maps：Simplification of Geographic Shape by Discrete Curve Evolution［C］∥Proceedings of Spatial Cognition II.Berlin：Springer，2000：41－53.

［3］ AVELAR S，MüLLER M.Generating Topologically Correct Schematic Maps［C］∥Proceedings of the 9th International Symposium on Spatial Data Handling.［S.l.］：Springer，2000：28－35.

［4］ AVELAR S.Schematic Maps on Demand：Design，Modeling and Visualization［D］.Zurich：Swiss Federal Institute of Technology，2002.

［5］ AVELAR S.Convergence Analysis and Quality Criteria for a Iterative Schematization of Networks［J］.Geoinformatica，2007，11（4）：497－513.

［6］ AVELAR S，HURNI L.On the Design of Schematic Transport Maps［J］.Cartographica：The International Journal for Geographic Information and Geovisualization，2006，41（3）：217－228.

［7］ AVELAR S，HUBER R.Modeling a Public Transport Network for Generation of Schematic Maps and Location Queries［C］∥Proceedings of the 20th International Cartographic Conference.Beijing：Surveying and Mapping Press，2001：1472－1480.

［8］ STOTT J M，RODGERS P，MARTINEZ－OVANDO J C，et al.Automatic Metro Map Layout Using Multicriteria Optimization［J］.IEEE Transaction on Visualization and Computer Graphics，2011，17（1）：101－114.

［9］ STOTT J M.Automatic Layout of Metro Maps Using Multicriteria Optimisation［D］.Canterbury：University of Kent，2008.

［10］ DONG Weihua，LI Zhilin，GUO Qingsheng.Automated Model Generalization of Schematic Networl Maps Based on Dynamic Segmentation［J］.Geomatics and Information Science of Wuhan University，2010，35（8）：892－895.（董衛(wèi)華，李志林，郭慶勝.基于動(dòng)態(tài)分段的道路網(wǎng)示意性地圖模型綜合［J］.武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2010，35（8）：892－895.）

［11］ CABELLO S，DE BERG M，VAN KREVELD M.Schematization of Networks［J］.Computational Geometry，2005，30（3）：223－238.

［12］ CABELLO S，VAN KREVELD M.Schematic Networks：an Algorithm and Its Implementation［C］∥Proceedings of the 10th International Symposium on Spatial Data Handling.Ottawa：Springer，2002：475－486.

［13］ HU Yungang，CHEN Jun，LI Zhilin，et al.Selective Omission of Road Features Based on Mesh Density for Digital Map Generalization［J］.Acta Geodaetica et Cartographica Sinica，2007，36（3）：351－357.（胡云崗，陳軍，李志林，等.基于網(wǎng)眼密度的道路選取方法［J］.測(cè)繪學(xué)報(bào)，2007，36（3）：351－357.）

［14］ DENG Hongyan，WU Fang，WANG Huilian，et al.A Generalization of Road Networks Based on Topological Similarity［J］.Journal of Geomatics Science and Technology，2008，25（3）：183－187.（鄧紅艷，武芳，王輝連，等.基于拓?fù)湎嗨菩缘牡缆肪W(wǎng)綜合模型［J］.測(cè)繪科學(xué)技術(shù)學(xué)報(bào)，2008，25（3）：183－187.）

［15］ CHEN Chun，ZHANG Shuwen，XU Guifen.The Basis for Generation of Topologic Information of Polygons in GIS［J］.Acta Geodaetica et Cartographica Sinica，1996，25（4）：266－271.（陳春，張樹(shù)文，徐桂芬.GIS中多邊形圖拓?fù)湫畔⑸傻臄?shù)學(xué)基礎(chǔ)［J］.測(cè)繪學(xué)報(bào)，1996，25（4）：266－271.）

［16］ DU Qingyun.Automatic Organization of Polygon Data in Cartographic Database［J］.Acta Geodaetica et Cartographica Sinica，1989，18（3）：204－212.（杜清運(yùn).地圖數(shù)據(jù)庫(kù)中多邊形數(shù)據(jù)的自動(dòng)組織［J］.測(cè)繪學(xué)報(bào)，1989，18（3）：204－212.）

［17］ WANG Zhaorui.Graph Theory［M］.3rd Edition.Beijing：Beijing Institute of Technology Press，2001.（王朝瑞.圖論［M］.3版.北京：北京理工大學(xué)出版社，2005.）

［18］ AWARE J M，ANAND S，TAYLOR G E，et al.Automated Production of Schematic Maps for Mobile Applications［J］.Transactions in GIS，2006，10（1）：25－42.

［19］ DONG Weihua，GUO Qingsheng，LIU Jiping，et al.Progressive Generalization Research of Schematic Road Network Maps［J］.Geomatics and Information Science of Wuhan University，2007，32（9）：829－832.（董衛(wèi)華，郭慶勝，劉紀(jì)平，等.道路網(wǎng)示意性地圖的漸進(jìn)式綜合研究［J］.武漢大學(xué)學(xué)報(bào)：信息科學(xué)板，2007，32（9）：829－832.）

［20］ LIANG Xiaowen，LIU Zongqi，CHEN Yijin.An algorithm of Polygon Auto－Construction Based on Angle Changing Tendence［J］.Journal of Image and Graphics，2005，10（6）：785－789.（梁曉文，劉宗岐，陳宜金.基于夾角變化趨勢(shì)的多邊形自動(dòng)搜索和生成算法［J］.中國(guó)圖象圖形學(xué)報(bào)，2005，10（6）：785－789.）