劉萬(wàn)增，陳 軍，閆超德，趙仁亮，趙 勇，孫文彬

1.國(guó)家基礎(chǔ)地理信息中心，北京100830；2.中國(guó)礦業(yè)大學(xué)（北京）地球科學(xué)與測(cè)繪工程學(xué)院，北京100083；3.鄭州大學(xué)地理信息工程系，河南鄭州450001

1 引 言

鄰近關(guān)系是平面離散點(diǎn)集的重要拓?fù)涮匦?。在GIS中，點(diǎn)是構(gòu)成空間目標(biāo)的最簡(jiǎn)單元素，平面離散點(diǎn)集的Voronoi圖確定了其間的鄰近關(guān)系，構(gòu)成離散點(diǎn)間的拓?fù)浣Y(jié)構(gòu)［1－2］。GIS中點(diǎn)集鄰近關(guān)系的建立、維護(hù)與重構(gòu)對(duì)于GIS中數(shù)據(jù)綜合［3－6］、位置服務(wù)、數(shù)據(jù)庫(kù)更新以及人工智能領(lǐng)域等具有重要意義。一般認(rèn)為，隨著某一點(diǎn)的移動(dòng)，平面離散點(diǎn)集的Voronoi圖局部會(huì)發(fā)生變化，從而引起平面離散點(diǎn)集局部拓?fù)浣Y(jié)構(gòu)的改變［7－8］。其實(shí)，在點(diǎn)目標(biāo)周圍存在這樣一個(gè)區(qū)域，目標(biāo)在其內(nèi)移動(dòng)，不會(huì)引起其與周圍鄰近點(diǎn)的拓?fù)浣Y(jié)構(gòu)的變化，稱該區(qū)域?yàn)橥負(fù)溧徑€(wěn)定區(qū)域。拓?fù)溧徑€(wěn)定區(qū)域的確定是維護(hù)目標(biāo)間的拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)。目前關(guān)于這一問(wèn)題的研究較少，文獻(xiàn)［9—11］從不同角度研究點(diǎn)目標(biāo)移動(dòng)時(shí)，其與周圍點(diǎn)目標(biāo)鄰近關(guān)系的變化，并給出定性描述，但關(guān)于目標(biāo)拓?fù)溧徑€(wěn)定區(qū)域的定義及其定量計(jì)算或描述的研究目前尚未見(jiàn)到。本文對(duì)這一問(wèn)題進(jìn)行研究，證明點(diǎn)的拓?fù)溧徑€(wěn)定區(qū)域必須滿足的兩個(gè)條件，并給出其定量計(jì)算模型。

2 拓?fù)溧徑€(wěn)定區(qū)域的確定

如圖1為平面上的離散點(diǎn)集｛P0，P1，P2，…，P5｝的Voronoi圖及其對(duì)偶Delaunay三角網(wǎng)。如果平面上兩點(diǎn)連線為Delaunay三角網(wǎng)的一條邊，則稱該兩點(diǎn)一階鄰近（即如果Line（Pi，Pj）∈DT，則（Pi，Pj）＝true，其中，DT為Delaunay triangle的邊集合）。將圖1中點(diǎn)P0定義為活動(dòng)點(diǎn)，依次連接其一階鄰近點(diǎn)得到一個(gè)多邊形P1P2P3P4P5，稱之為移動(dòng)點(diǎn)P0的一階鄰近多邊形，用ADJpolygon（P0）表示。圖1中P0點(diǎn)在深色區(qū)域內(nèi)移動(dòng)，其與點(diǎn)P1、P2、P3、P4、P5的一階鄰近關(guān)系不會(huì)改變，同時(shí)，沒(méi)有新的一階鄰近點(diǎn)產(chǎn)生，即P0點(diǎn)與點(diǎn)P1、P2、P3、P4、P5組成的一階鄰近多邊形ADJpolygon（P0）不會(huì)發(fā)生變化。分析認(rèn)為，拓?fù)溧徑€(wěn)定區(qū)域也就是在保證一階鄰近多邊形不變的情況下活動(dòng)點(diǎn)P0的移動(dòng)區(qū)域。以下首先證明點(diǎn)的拓?fù)溧徑€(wěn)定區(qū)域必須滿足的兩個(gè)條件，以此為基礎(chǔ)研究活動(dòng)點(diǎn)拓?fù)溧徑€(wěn)定區(qū)域確定方法。

圖1 平面離散點(diǎn)集及其鄰近關(guān)系Fig.1 The neighboring relations between the plane discrete points

2.1 不改變?cè)浑A鄰近點(diǎn)的活動(dòng)點(diǎn)移動(dòng)區(qū)域

如圖1，在活動(dòng)點(diǎn)P0移動(dòng)過(guò)程中，要保持其一階鄰近多邊形不變，首先必須滿足其與點(diǎn)P1、P2、P3、P4、P5的一階鄰近關(guān)系不會(huì)改變。反過(guò)來(lái)，如果要滿足點(diǎn)P0與點(diǎn)P1、P2、P3、P4、P5一階鄰近關(guān)系不變，那么點(diǎn)P0的允許移動(dòng)區(qū)域需要確定。平面上任意3個(gè)非共線點(diǎn)可以確定一個(gè)外接圓，根據(jù)Delaunay三角網(wǎng)的空?qǐng)A規(guī)則可以判斷活動(dòng)點(diǎn)P0與任意3個(gè)非共線點(diǎn)的鄰近關(guān)系［12］。以上的例子中，若點(diǎn)P0與點(diǎn)P1、P2、P3、P4、P5一階鄰近關(guān)系不變，則P0與點(diǎn)P1、P2、P3、P4、P5中任意相鄰3點(diǎn)一階鄰近關(guān)系不變；反過(guò)來(lái)，若點(diǎn)P0同時(shí)與點(diǎn)P1、P2、P3、P4、P5中任意相鄰3點(diǎn)一階鄰近關(guān)系不變，則點(diǎn)P0與點(diǎn)P1、P2、P3、P4、P5中每一點(diǎn)一階鄰近關(guān)系不變。因此，研究不改變?cè)浑A鄰近點(diǎn)的活動(dòng)點(diǎn)移動(dòng)區(qū)域，首先研究在保持活動(dòng)點(diǎn)與任意3個(gè)非共線點(diǎn)的鄰近關(guān)系不變的情況下，活動(dòng)點(diǎn)P0的移動(dòng)范圍。

2.1.1 平面上活動(dòng)點(diǎn)與3點(diǎn)一階鄰近的定義

定義：如果活動(dòng)點(diǎn)與3個(gè)非共線點(diǎn)當(dāng)中的每一點(diǎn)一階鄰近，則稱該活動(dòng)點(diǎn)與該平面3點(diǎn)一階鄰近。

活動(dòng)點(diǎn)P0與平面3個(gè)非共線點(diǎn)Pi－1、Pi、 Pi＋1，如果則

2.1.2 與相鄰3點(diǎn)一階鄰近的活動(dòng)點(diǎn)P0的移動(dòng)區(qū)域

如圖2，⊙O為點(diǎn)P3、P4、P5的外接圓，當(dāng)P0位于⊙O內(nèi)部時(shí)，P0與P3、P4、P5一階鄰近，當(dāng)P0移動(dòng)到外接圓上時(shí)，線段P3P4的垂直平分線與線段P4P5的垂直平分線相交于圓心點(diǎn)O，這時(shí)，P0、P3、P4、P54點(diǎn)共圓，點(diǎn)P0與點(diǎn)P4的Voronoi區(qū)域邊界只交于一點(diǎn)O，改變了二者的鄰近關(guān)系，點(diǎn)P0僅與點(diǎn)P3、P5一階鄰近。隨著P0移出到圓外部，點(diǎn)P0、P4的Voronoi區(qū)域邊界交集為空，表示二者仍非一階鄰近關(guān)系?？梢?jiàn)，點(diǎn)P0與點(diǎn)P3、P4、P5是否一階鄰近，主要取決于P0點(diǎn)與點(diǎn)P3、P4、P5外接圓的位置關(guān)系［13］。

圖2 活動(dòng)點(diǎn)P0位置變化對(duì)鄰近關(guān)系的影響Fig.2 The change of position of the point P0may affect the neighboring relations between the points in the plane

引理：與平面上點(diǎn)Pi－1、Pi、Pi＋1一階鄰近的所有P0點(diǎn)的集合（A1（i））等于以點(diǎn)Pi－1、Pi、Pi＋1為頂點(diǎn)的△Pi－1PiPi＋1的外接圓內(nèi)部點(diǎn)集（A1（i）circlr）與以△Pi－1PiPi＋1頂點(diǎn)為起點(diǎn)的三角形兩邊反向延長(zhǎng)線所夾區(qū)域內(nèi)點(diǎn)集 （A1（i）sectioni）的并集。如圖3所示

圖3 與已知3點(diǎn)一階鄰近的活動(dòng)點(diǎn)P0的移動(dòng)范圍Fig.3 The moving range of point P0which is neighbor to the three points

證明：

（1）如圖4（a），當(dāng)P0位于△Pi－1PiPi＋1的外部、外接圓的內(nèi)部時(shí)（稱該區(qū)域?yàn)椋篈11（i）circle＝｛P0｜（P0∈A1（i）circle）∧（P0?A1（i）△Pi－1PiPi＋1）｝），根據(jù)Delaunay三角網(wǎng)的空?qǐng)A規(guī)則［9］，△Pi－1PiPi＋1不能作為Delaunay三角網(wǎng)的一個(gè)三角形，△Pi－1PiPi＋1的任意一條邊不能作為點(diǎn)P0、Pi－1、Pi、Pi＋1所形成的凸四邊形的對(duì)角線，亦即，點(diǎn)P0與點(diǎn)Pi－1、Pi、Pi＋1分別有一條Delaunay三角形的邊相連，則點(diǎn)P0與點(diǎn)Pi－1、Pi、Pi＋1必然一階鄰近。

（2）如圖4（b），當(dāng)點(diǎn)P0在△Pi－1PiPi＋1的內(nèi)部或邊上時(shí)（稱之為區(qū)域A21（i）circle＝｛P0｜P0∈A1（i）△Pi－1PiPi＋1｝）。同 樣，根 據(jù) 空 圓 規(guī) 則，△Pi－1PiPi＋1不能作為Delaunay三角網(wǎng)的一個(gè)三角形，需要對(duì)其重新剖分，在三角形內(nèi)部及邊上一點(diǎn)對(duì)該三角形進(jìn)行剖分有且只有一種剖分結(jié)果，就是將該點(diǎn)分別與原三角形的三個(gè)頂點(diǎn)相連，線段P0Pi－1、P0Pi、P0Pi＋1就分別成為Delaunay三角形的一條邊，因而點(diǎn)P0分別與點(diǎn)Pi－1、Pi、Pi＋1一階鄰近。

（3）如圖4（c），當(dāng)點(diǎn)P0位于A1（i）section1、A1（i）section2或A1（i）section3內(nèi)部（即P0∈A1（i）section），同樣由于點(diǎn)Pi－1、Pi、Pi＋1外接圓為空?qǐng)A，因而，△Pi－1PiPi＋1可以作為Delaunay三角網(wǎng)的一個(gè)三角形。圖中，由于點(diǎn)P0位于線段Pi－1Pi、Pi＋1Pi延長(zhǎng)線所形成的扇形區(qū)域（不包括延長(zhǎng)線上的點(diǎn)）內(nèi)，點(diǎn)Pi必然位于△Pi－1P0Pi＋1中，以點(diǎn)Pi對(duì)△Pi－1P0Pi＋1進(jìn)行剖分，則P0點(diǎn)與點(diǎn)Pi－1、Pi、Pi＋1的連線分別為Delaunay的一條邊，因而P0點(diǎn)分別與點(diǎn)Pi－1、Pi、Pi＋1一階鄰近。

（4）如圖4（d），當(dāng)點(diǎn)P0位于A1（i）區(qū)域外時(shí)，即P0∈（A1（i））－，由于△Pi－1PiPi＋1外接圓為空?qǐng)A，因而△Pi－1PiPi＋1可以作為Delaunay三角網(wǎng)的一個(gè)三角形，點(diǎn)P0與點(diǎn)Pi－1、Pi、Pi＋1可以形成一個(gè)以△Pi－1PiPi＋1的邊為對(duì)角線的凸四邊形，P0只能和其最近的△Pi－1PiPi＋1的兩個(gè)頂點(diǎn)相連構(gòu)成新的三角形，與△Pi－1PiPi＋1的另外一個(gè)頂點(diǎn)沒(méi)有邊相連，不具有一階鄰近關(guān)系。

由于平面點(diǎn)的全集S＝A1（i）∪（A1（i））－＝A1（i）circle∪A1（i）section∪（A1（i））－＝A11（i）circle∪A21（i）circle∪A1（i）section∪（A1（i））－，以上討論的4類區(qū)域的并集代表整個(gè)平面區(qū)域，因而，A1（i）＝A1（i）circle∪A1（i）section可以完備地表示平面上與點(diǎn)Pi－1、Pi、Pi＋1相鄰的點(diǎn)P0的集合。

圖4 平面上不同區(qū)域活動(dòng)點(diǎn)與已知3點(diǎn)的鄰近關(guān)系Fig.4 The neighboring relations between the point P0 and the other three points of the plane in the different area

以上證明了與一階鄰近多邊形連續(xù)3個(gè)頂點(diǎn)保持鄰近關(guān)系的點(diǎn)P0的活動(dòng)區(qū)域，若保證點(diǎn)P0與其一階鄰近多邊形中每一頂點(diǎn)都一階鄰近，顯然，P0應(yīng)該處在其一階鄰近多邊形每連續(xù)3頂點(diǎn)所確定區(qū)域A1（i）的交集內(nèi)。

結(jié)論1：若P0與n個(gè)一階鄰近點(diǎn)的一階鄰近關(guān)系保持不變，則P0點(diǎn)必須位于其n個(gè)一階鄰近點(diǎn)中依次相鄰3個(gè)一階鄰近點(diǎn)所形成的n個(gè)A1（i）區(qū)域的交集內(nèi)。

設(shè)Pi（1，2，…，n）為P0點(diǎn)的一階鄰近點(diǎn)，相鄰一階鄰近點(diǎn)Pn、P1、P2，P1、P2、P3，P2、P3、P4，…，Pi、Pi＋1、Pi＋2，…，Pn－2、Pn－1、Pn，Pn－1、Pn、P1的A1（i）區(qū)域分別為A1（1）、A1（2）、…、A1（n），則

2.2 不產(chǎn)生新的一階鄰近點(diǎn)的活動(dòng)點(diǎn)P0的移動(dòng)區(qū)域

結(jié)論1所確定的區(qū)域A1只能保證在點(diǎn)P0移動(dòng)過(guò)程中保持與原有一階鄰近點(diǎn)的鄰近關(guān)系不變，但不能保證其沒(méi)有新的一階鄰近點(diǎn)產(chǎn)生。隨著P0點(diǎn)的移動(dòng)，盡管其與原有一階鄰近點(diǎn)的鄰近關(guān)系不變，但其可能與原二階鄰近點(diǎn)形成新的一階鄰近關(guān)系，其一階鄰近點(diǎn)數(shù)目增加，一階鄰近多邊形由于頂點(diǎn)數(shù)目增加而發(fā)生變化。那么，活動(dòng)點(diǎn)P0與原一階鄰近點(diǎn)鄰近關(guān)系不變的情況下，進(jìn)一步研究是否有新的一階鄰近點(diǎn)產(chǎn)生。

如圖5（a）所示，在點(diǎn)P0移動(dòng)之前，其鄰近多邊形頂點(diǎn)為點(diǎn)P1、P2、P3、P4、P5，線段P4P5為一階鄰近多邊形的一條邊，點(diǎn)P4、P5共同的一階鄰近點(diǎn)為點(diǎn)P0和P6。點(diǎn)P0位于△P4P5P6的外接圓外部，與點(diǎn)P6是二階鄰近關(guān)系，此時(shí)，點(diǎn)P0、P4、P5、P64點(diǎn)滿足空外接圓規(guī)則，線段P4P5為4點(diǎn)所構(gòu)成四邊形的對(duì)角線。當(dāng)P0點(diǎn)移動(dòng)到△P4P5P6外接圓及其內(nèi)部時(shí)（P′0點(diǎn)位置），空?qǐng)A規(guī)則破壞，需要對(duì)四邊形重新剖分，交換對(duì)角線，此時(shí)點(diǎn)P0與點(diǎn)P6成為Delaunay三角形的一條邊，點(diǎn)P6成為點(diǎn)P0的一階鄰近點(diǎn)，形成如圖5（b）所示的P0點(diǎn)新的一階鄰近多邊形P1P2P3P4P5P6。可以看出，要保證P0點(diǎn)鄰近多邊形的邊不變，沒(méi)有新的一階鄰近點(diǎn)加入，P0點(diǎn)必須位于該邊兩端點(diǎn)及其除P0點(diǎn)以外的另一共同一階鄰近點(diǎn)所確定外接圓的外部。

圖5 P0點(diǎn)移動(dòng)導(dǎo)致其鄰近多變形變化圖Fig.5 The moving of the point P0may change it’s neighboring polygon

結(jié)論2：點(diǎn)P0在A1區(qū)域內(nèi)移動(dòng)時(shí)要確保其沒(méi)有新的一階鄰近點(diǎn)產(chǎn)生，則P0點(diǎn)應(yīng)保持在該邊兩端點(diǎn)及其除P0點(diǎn)以外的另一共同一階鄰近點(diǎn)所確定外接圓的外部（必要條件）。

設(shè)P0點(diǎn)鄰近多邊形ADJpolygon（P0）的邊PjPj＋1的兩個(gè)端點(diǎn)Pj、Pj＋1與該兩點(diǎn)在鄰近多邊形外側(cè)的共同一階鄰近點(diǎn)的外接圓區(qū)域?yàn)锳2（j）circlr，則在滿足條件的P0點(diǎn)的活動(dòng)區(qū)域可以表示為

2.3 活動(dòng)點(diǎn)拓?fù)溧徑€(wěn)定區(qū)域的確定

結(jié)論2只是保持P0點(diǎn)一階鄰近多邊形不變的必要條件。如圖6（a）中的綠色區(qū)域?yàn)闈M足結(jié)論2的P0點(diǎn)移動(dòng)范圍；圖6（b）表示當(dāng)P0點(diǎn)在綠色區(qū)域中移動(dòng)時(shí)，其鄰近多邊形發(fā)生了變化，改變?cè)浑A鄰近的一階鄰近關(guān)系?？梢?jiàn)，如果P0點(diǎn)移動(dòng)后只滿足結(jié)論1，雖然可以保持原有一階鄰近點(diǎn)不變，但可增加新的一階鄰近點(diǎn)；如果只滿足結(jié)論2，盡管可以確保不會(huì)增加一階鄰近點(diǎn)，可是會(huì)造成原有一階鄰近點(diǎn)數(shù)目減少。可見(jiàn)，要保證P0點(diǎn)移動(dòng)后，其一階鄰近點(diǎn)既不增加又不減少，P0點(diǎn)必須同時(shí)滿足結(jié)論1與結(jié)論2的條件。

圖6 僅滿足結(jié)論2的效果圖Fig.6 The result of conclusion 2

結(jié)論3：若保持P0點(diǎn)的一階鄰近多邊形不變，P0點(diǎn)必須位于A1區(qū)域與A2區(qū)域的交集內(nèi)。

圖7、圖8為利用結(jié)論3確定的拓?fù)浞€(wěn)定區(qū)域。

圖7 結(jié)論3所確定的P0點(diǎn)的拓?fù)浞€(wěn)定區(qū)域Fig.7 The topology stable area of point P0 defined by conclusion 3

圖8 結(jié)論3所確定的離散點(diǎn)的拓?fù)浞€(wěn)定區(qū)域Fig.8 The topology stable areas of the plane discrete points defined by conclusion 3

3 活動(dòng)點(diǎn)拓?fù)溧徑€(wěn)定區(qū)域的計(jì)算

根據(jù)結(jié)論3，可以給出活動(dòng)點(diǎn)拓?fù)溧徑€(wěn)定區(qū)域的計(jì)算模型。

如圖9，設(shè)點(diǎn)P0為扇形區(qū)域A1（i）section中任意一點(diǎn)，則向量P（i＋1）Pi與PiP0的夾角β1，向量PiP0與P（i－1）Pi的夾角β2，向量P（i＋1）Pi與P（i－1）Pi的夾角β存在以下關(guān)系

式中，K（i＋1）－i表示過(guò)點(diǎn)Pi＋1、Pi的直線的斜率，其計(jì)算公式為

圖9 扇形區(qū)域內(nèi)點(diǎn)滿足的條件Fig.9 The condition must be met by the points in the sector

將式（6）、（7）、（8）代入式（5），得到式（10），則A1（i）section中點(diǎn)P0坐標(biāo)一定滿足該等式標(biāo)和半徑分別為設(shè)P0點(diǎn)一階鄰近多邊形ADJpolygon（P0）的邊PiPi＋1的兩個(gè)端點(diǎn)Pi、Pi＋1除P0點(diǎn)外的另一個(gè)共同一階鄰近點(diǎn)Pj的坐標(biāo)為（xj，yj），Pi、Pi＋1、Pj圓心坐標(biāo)和半徑分別為則P0點(diǎn)坐標(biāo)（x，y）為滿足以下方程的解

設(shè)點(diǎn)Pi（1，2，…，n）為點(diǎn)P0（x，y）的一階鄰近點(diǎn)，其坐標(biāo)為（xi，yi），△PnP1P2、△P1P2P3、△Pi－1PiPi＋1、…、△Pn－1PnP1的外接圓圓心坐

4 試 驗(yàn)

采用本文方法和逐點(diǎn)試探法分別繪制移動(dòng)點(diǎn)P0的拓?fù)浞€(wěn)定區(qū)域，進(jìn)一步驗(yàn)證結(jié)論3的正確性。圖10是按照該方法，即利用式（11）繪出的移動(dòng)點(diǎn)P0的拓?fù)浞€(wěn)定區(qū)域。圖11為逐點(diǎn)試探所確定的移動(dòng)點(diǎn)P0的拓?fù)浞€(wěn)定區(qū)域，是以保持P0點(diǎn)的一階鄰近多邊形不變?yōu)榧s束條件，以鄰近多邊形內(nèi)的每一點(diǎn)代替P0，生成Voronoi圖及鄰近關(guān)系，判斷P0點(diǎn)的鄰近多邊形是否變化，如果不變則記錄下該點(diǎn)，最后繪出滿足條件的所有P0點(diǎn)。試驗(yàn)證明兩種方法繪出的滿足條件的P0點(diǎn)的區(qū)域是等價(jià)的，驗(yàn)證結(jié)論3的正確性。

圖10 采用本文方法得到的拓?fù)浞€(wěn)定區(qū)域Fig.10 Topology stable area generated by above method

圖11 采用逐點(diǎn)試探法得到的拓?fù)浞€(wěn)定區(qū)域Fig.11 Topology stable area generated by the one by one trying method

5 結(jié) 論

提出在平面離散點(diǎn)集中每一點(diǎn)的周圍存在一個(gè)拓?fù)溧徑€(wěn)定區(qū)域，并給出其計(jì)算方法。點(diǎn)的拓?fù)溧徑€(wěn)定區(qū)域計(jì)算之后，在點(diǎn)移動(dòng)過(guò)程中，不需要重構(gòu)Voronoi圖或Delaunay三角網(wǎng)即可判斷其與周圍各點(diǎn)的鄰近關(guān)系，同時(shí)利用點(diǎn)的拓?fù)溧徑€(wěn)定區(qū)域可以在確保點(diǎn)的鄰近關(guān)系不變的情況下，進(jìn)行相關(guān)條件約束下的點(diǎn)目標(biāo)位置最優(yōu)規(guī)劃。線目標(biāo)和面目標(biāo)可看做由一系列點(diǎn)連接而成［14－15］。將對(duì)基于點(diǎn)的拓?fù)溧徑€(wěn)定區(qū)域計(jì)算模型對(duì)線和面的拓?fù)溧徑€(wěn)定區(qū)域計(jì)算方法作進(jìn)一步研究。

［1］ GOLD C M.Spatial Adjacency a General Approach［EB／OL］.［2005－03－18］.http：∥www.voronoi.com／wiki／images／a／ae／Spatial＿adjacency－a＿general＿approach.pdf.

［2］ GOLD C M.The Meaning of“Neighbour”［C］∥Proceedings International Conference GIS：Theories and Methods of Spatial－temporal Reasoning in Geographic Space.Berlin：Springer－Verlag，1992：220－235.

［3］ CHARISTOPHER B J，GERAINT L B，WARE J M.Map Generalization with a Triangulated Data Structure［J］.Cartography and GIS，1995，22（4）：317－331.

［4］ TSAL V J D.Delaunay Triangulations in TIN Creation：an Overview and a Linear－time Algorithm［J］.International Journal of Geographical Information Systems，1993，7（6）：501－524.

［5］ WEIBEL R，JONES C B.Computational Perspectives on Map Generalization Guest Editorial for Special［J］.Geo－Informatica，1998，2（4）：307－314.

［6］ AI Tinghua，LIU Yaolin.A Method of Point Cluster Simplification with Spatial Distribution Properties Preserved［J］.Acta Geodaetica et Cartographica Sinica，2002，31（2）：175－181.（艾廷華，劉耀林.保持空間分布特征的群點(diǎn)化簡(jiǎn)方法［J］.測(cè)繪學(xué)報(bào)，2002，31（2）：175－181.）

［7］ YANG W.The Design of a Dynamic Voronoi Map Object（VMO）Model for Sustainable Forestry Data Management［D］.Laval：Laval University，1997.

［8］ CHEN Jun.The Voronoi Dynamic Spatial Data Model［M］.Beijing：Surveying and Mapping Press，2002.（陳軍.Voronoi動(dòng)態(tài)空間數(shù)據(jù)模型［M］.北京：測(cè)繪出版社，2002.）

［9］ W ANG P.Automated Generalization in GIS［M］.Wageningen：Agricultural University and ITC，1997.

［10］ GOLD C M，YANG W.Spatial Data Management Tools Based on the Voronoi Dynamic Data Model（Vordll 1.0）User’s Manual［R］.Laval：Laval University，1994.

［11］ MAO Jianhua，CHEN Fei，MAO Duanqian.A Method for Detecting the Topological Relations’Change of the Moving Object［J］.Bulletin of Surveying and Mapping，2003（4）：22－24.（毛建華，陳斐，毛端謙.地圖目標(biāo)移位的拓?fù)潢P(guān)系變化檢測(cè)方法［J］.測(cè)繪通報(bào)，2003（4）：22－24.）

［12］ LEDOUX H，GOLD C M.A Voronoi－based Map Algebra［EB／OL］.［2005－03－18］.http：∥www.voronoi.com／wiki／images／0／0f／Voronoi＿map＿algebra.pdf.

［13］ MIOC D，ANTON F，GOLD C M，et al.Map Updates in a Dynamic Voronoi Data Structure［EB／OL］.［2005－03－18］.http：∥www.voronoi.com／wiki／images／0／0f／map updates in a dynamic voronoi data structure.pdf.

［14］ CHEN Jun，LIU Wanzeng，LI Zhilin，et al.The Refined Calculation Method of Topological Relationships between Line Objects［J］.Acta Geodaetica et Cartographica Sinica，2006，35（8）：255－260.（陳軍，劉萬(wàn)增，李志林，等.線目標(biāo)間拓?fù)潢P(guān)系的細(xì)化計(jì)算方法［J］.測(cè)繪學(xué)報(bào)，2006，35（3）：255－260.）

［15］ XIE Shunping，F(xiàn)ENG Xuezhi，LU Wei.Algorithm for Constructing Voronoi Area Diagram Based on Road Network Analysis［J］.Acta Geodaetica et Cartographica Sinica，2010，39（1）：88－94.（謝順平，馮學(xué)智，魯偉.基于道路網(wǎng)絡(luò)分析的Voronoi面域圖構(gòu)建算法［J］.測(cè)繪學(xué)報(bào)，2010，39（1）：88－94.）