平面離散點集拓撲鄰近穩(wěn)定區(qū)域計算模型

劉萬增，陳 軍，閆超德，趙仁亮，趙 勇，孫文彬

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

1 引 言

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

2 拓撲鄰近穩(wěn)定區(qū)域的確定

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

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

2.1 不改變原一階鄰近點的活動點移動區(qū)域

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

2.1.1 平面上活動點與3點一階鄰近的定義

定義：如果活動點與3個非共線點當中的每一點一階鄰近，則稱該活動點與該平面3點一階鄰近。

活動點P0與平面3個非共線點Pi－1、Pi、 Pi＋1，如果則

2.1.2 與相鄰3點一階鄰近的活動點P0的移動區(qū)域

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

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

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

圖3 與已知3點一階鄰近的活動點P0的移動范圍Fig.3 The moving range of point P0which is neighbor to the three points

證明：

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

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

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

（4）如圖4（d），當點P0位于A1（i）區(qū)域外時，即P0∈（A1（i））－，由于△Pi－1PiPi＋1外接圓為空圓，因而△Pi－1PiPi＋1可以作為Delaunay三角網(wǎng)的一個三角形，點P0與點Pi－1、Pi、Pi＋1可以形成一個以△Pi－1PiPi＋1的邊為對角線的凸四邊形，P0只能和其最近的△Pi－1PiPi＋1的兩個頂點相連構(gòu)成新的三角形，與△Pi－1PiPi＋1的另外一個頂點沒有邊相連，不具有一階鄰近關(guā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ū)域的并集代表整個平面區(qū)域，因而，A1（i）＝A1（i）circle∪A1（i）section可以完備地表示平面上與點Pi－1、Pi、Pi＋1相鄰的點P0的集合。

圖4 平面上不同區(qū)域活動點與已知3點的鄰近關(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個頂點保持鄰近關(guān)系的點P0的活動區(qū)域，若保證點P0與其一階鄰近多邊形中每一頂點都一階鄰近，顯然，P0應(yīng)該處在其一階鄰近多邊形每連續(xù)3頂點所確定區(qū)域A1（i）的交集內(nèi)。

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

設(shè)Pi（1，2，…，n）為P0點的一階鄰近點，相鄰一階鄰近點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)生新的一階鄰近點的活動點P0的移動區(qū)域

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

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

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

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

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

2.3 活動點拓撲鄰近穩(wěn)定區(qū)域的確定

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

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

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

圖7、圖8為利用結(jié)論3確定的拓撲穩(wěn)定區(qū)域。

圖7 結(jié)論3所確定的P0點的拓撲穩(wěn)定區(qū)域Fig.7 The topology stable area of point P0 defined by conclusion 3

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

3 活動點拓撲鄰近穩(wěn)定區(qū)域的計算

根據(jù)結(jié)論3，可以給出活動點拓撲鄰近穩(wěn)定區(qū)域的計算模型。

如圖9，設(shè)點P0為扇形區(qū)域A1（i）section中任意一點，則向量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表示過點Pi＋1、Pi的直線的斜率，其計算公式為

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

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

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

4 試 驗

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

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

圖11 采用逐點試探法得到的拓撲穩(wěn)定區(qū)域Fig.11 Topology stable area generated by the one by one trying method

5 結(jié) 論

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

［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.（艾廷華，劉耀林.保持空間分布特征的群點化簡方法［J］.測繪學(xué)報，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動態(tài)空間數(shù)據(jù)模型［M］.北京：測繪出版社，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.（毛建華，陳斐，毛端謙.地圖目標移位的拓撲關(guān)系變化檢測方法［J］.測繪通報，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.（陳軍，劉萬增，李志林，等.線目標間拓撲關(guān)系的細化計算方法［J］.測繪學(xué)報，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］.測繪學(xué)報，2010，39（1）：88－94.）