• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

    一種線—線拓?fù)潢P(guān)系識別算法及其應(yīng)用

    2015-11-04 02:14:42安曉亞徐道柱
    測繪科學(xué)與工程 2015年5期
    關(guān)鍵詞:端點重合交點

    安曉亞,金 澄,3,徐道柱,3

    1.西安測繪研究所,陜西 西安,710054;2.地理信息工程國家重點實驗室,陜西 西安,710054;3.信息工程大學(xué)地理空間信息學(xué)院,河南 鄭州,450052

    ?

    一種線—線拓?fù)潢P(guān)系識別算法及其應(yīng)用

    安曉亞1,2,金澄1,2,3,徐道柱1,2,3

    1.西安測繪研究所,陜西 西安,710054;2.地理信息工程國家重點實驗室,陜西 西安,710054;3.信息工程大學(xué)地理空間信息學(xué)院,河南 鄭州,450052

    線-線拓?fù)潢P(guān)系的識別與檢測是空間關(guān)系研究的熱點與難點。本文改進(jìn)了平面交點算法,簡化了維度擴展的9交集矩陣,建立了線線之間局部拓?fù)潢P(guān)系的索引文件,通過搜索和組合得到了線-線之間整體而又詳細(xì)的拓?fù)潢P(guān)系;利用研究成果對道路數(shù)據(jù)進(jìn)行關(guān)系處理,對地理要素間關(guān)系進(jìn)行沖突探測。實驗結(jié)果表明,該算法具有高效、準(zhǔn)確識別線-線詳細(xì)拓?fù)潢P(guān)系的優(yōu)點。

    地理信息處理;拓?fù)潢P(guān)系;沖突檢測;拓?fù)潢P(guān)系矩陣

    1 引 言

    在地理信息生產(chǎn)和處理過程中,要素間關(guān)系的檢測與一致性處理至關(guān)重要,是保證最終地理信息產(chǎn)品質(zhì)量的關(guān)鍵環(huán)節(jié)。主要解決兩個問題:一是在數(shù)據(jù)綜合處理階段對原有拓?fù)潢P(guān)系的“破壞”,例如對道路進(jìn)行化簡后,導(dǎo)致道路與居民地之間的關(guān)系由相切關(guān)系變?yōu)橄嚯x關(guān)系,道路與河流發(fā)生矛盾,等高線與河流發(fā)生水曲矛盾等;二是不同來源數(shù)據(jù)之間關(guān)系的不協(xié)調(diào)、不一致等問題。解決上述問題的基礎(chǔ)和前提是識別要素間的空間關(guān)系并對其進(jìn)行描述,然后再根據(jù)制圖知識判斷關(guān)系是否協(xié)調(diào)一致,進(jìn)而進(jìn)行處理。地理信息中存在著大量的線目標(biāo),線-線拓?fù)潢P(guān)系的識別與檢測是空間關(guān)系研究的熱點與難點。線-線目標(biāo)之間是否相交的判別及交點的求解是研究拓?fù)潢P(guān)系的基礎(chǔ),算法效率的高低對空間拓?fù)潢P(guān)系的識別與處理起到一個決定性的作用。當(dāng)前一般采用“暴力求交”方法來判別線線是否相交,即假設(shè)平面上有n條線段,如果對n條線段兩兩求交,其時間復(fù)雜度為O(n2),當(dāng)交點很少時,效率會更低[1]。

    針對上述問題,本文將計算幾何中的平面交點算法[2](1979年由Bentley和Ottmann提出,簡稱BO算法,下同)進(jìn)行改進(jìn)應(yīng)用于線-線空間拓?fù)潢P(guān)系的識別,并對維度擴展的9交集矩陣進(jìn)行簡化,以便描述地理信息生產(chǎn)處理中的線-線拓?fù)潢P(guān)系,最后將算法應(yīng)用于地理信息生產(chǎn)處理系統(tǒng)中。

    2 基本算法

    2.1平面交點算法及其改進(jìn)

    假設(shè)平面上有一平面線要素的集合S,掃描線(一條垂直于X軸的直線)SL從S的最左端向最右端掃描。在SL掃描過程中,算法動態(tài)地維護(hù)S∩SL的結(jié)果,這個結(jié)果一般表現(xiàn)為一個一維排序的集合。在掃描過程中,每條線段根據(jù)它與掃描線的關(guān)系,分成三種狀態(tài),如圖1所示(SL是正在進(jìn)行的掃描線,虛線是已經(jīng)或者即將進(jìn)行的掃描線,S0-S8是線段):

    圖1 BO線段的3種狀態(tài)

    (1)死亡態(tài)。位于掃描線SL的左側(cè),例如S0,S1,指已經(jīng)參與求交運算的線段后續(xù)不再參與運算。

    (2)激活態(tài)。與掃描線SL有交點的線段,例如S2至S6,指正在參與求交運算的線段。

    (3)睡眠態(tài)。位于掃描線SL右側(cè)的線段,例如S7,S8,這些線段暫不參與求交運算,直到掃描線到達(dá)。

    處于激活態(tài)的線段保存在結(jié)構(gòu)Y-Structure中,為了保證算法的時間復(fù)雜度,將這些線段以一定的順序存儲于Y-Structure,這個順序關(guān)系由線段和掃描線SL交點的y值決定,y值越大越靠前。

    在掃描的過程中,線段的狀態(tài)不斷變化,經(jīng)歷一個從睡眠態(tài)到激活態(tài)至死亡態(tài)的轉(zhuǎn)化過程。狀態(tài)轉(zhuǎn)化發(fā)生在特定的時刻,即SL遇到線段端點或者交點的時候,這些特定的點被稱為事件點。這些事件點保存在結(jié)構(gòu)X-Structure中,并且按照事件點的x大小值維持一個全序關(guān)系。初始化時,把所有線段的端點加入到X-Structure中,在掃描過程中,動態(tài)求得的交點也要加入到X-Structure中。將X-Structure和Y-Structure定義為:

    typedef struct YSTRUCTURE

    {

    ElementID ID; //線段所在線串的ID

    long Index;//線段的索引號

    Dpoint3d point[2];//線段的坐標(biāo)

    Dpoint3d cutpoint;//掃描線與線段的交點坐標(biāo)

    struct YSTRUCTURE *next;

    }Y-Structure;

    typedef struct XSTRUCTURE

    {

    ElementID ID; //點所在線串的ID

    long Index;//點的索引號

    Dpoint3d point;//點的坐標(biāo)

    int flag;//值為-1時point處于睡眠態(tài),值為0時處于激活態(tài),值為1時為交點

    struct XSTRUCTURE *next;

    } X-Structure;

    在掃描過程中,最關(guān)鍵的是當(dāng)事件點發(fā)生改變時如何處理,有以下3種情況:

    (1)事件點是線段的左端點。如圖2所示:

    圖2 事件點為線段的左端點

    在這種情況下,首先將S插入至Y-Structure中;然后在Y-Structure中找到與S相鄰的前后線段above和below(在存在的情況下),如果S與它們有交點,并且交點在SL的右側(cè),則將這個交點插入至X-Structure。

    (2)事件點是線段的右端點。如圖3所示:

    圖3 事件點為線段的右端點

    這時,首先把S從Y-Structure中刪除;然后在Y-Structure中找到與S相鄰的前后線段above和below(在存在的情況下),如果S與它們有交點,并且交點在SL的右側(cè),則將這個交點插入至X-Structure。

    (3)事件點是兩線段的交點。如圖4所示:

    圖4 事件點為兩線段的交點

    S1和S2是相交的線段,且Y-Structure中S1在S2的上面,這時首先在Y-Structure中找到S1的上鄰above和S2的下鄰below(如果存在),如果S1和below有交點并且交點在SL的右側(cè),把它插入至X-Structure中;同樣,如果S2和above有交點并且交點在SL的右側(cè),也把它插入至X-Structure中;然后在Y-Structure中交換S1和S2的次序,使得在Y-Structure中S2在S1上面。BO算法的時間復(fù)雜度是O((n+k)×logn),空間復(fù)雜度是O(n+k)。

    但BO算法存在的問題是:其對輸入線段要求比較嚴(yán)格(要求不存在垂直的線段、不存在三線共點的情況、線段的端點不能相等、線段端點或者交點x值不能相等、不存在有公共邊等情況)。針對這些問題,我們對其進(jìn)行改進(jìn),改進(jìn)的思路是把上述特殊情況當(dāng)做一般情況,主要包括:

    (1)X-Structure中事件點的順序關(guān)系確定

    BO算法根據(jù)事件點x值的大小定義事件點的順序關(guān)系,本文則首先比較點的X值大小,再比較Y值的大小。經(jīng)過這樣的改進(jìn),算法可以處理線段端點或交點的x值相等下的特殊情況。

    (2)Y-Structure中線段的順序關(guān)系確定

    處理垂直線段。根據(jù)對X-Structure的改進(jìn),掃描點總是首先到達(dá)線段的頭節(jié)點(約定線段的頭節(jié)點小于線段的尾節(jié)點),即約定垂直的線段和與其相交線段的次序關(guān)系。

    處理端點相等線段。如果是右端點,線段馬上就會轉(zhuǎn)入死亡態(tài),所以我們只考慮左端點的情況,左端點與之類似,即約定端點相等線段次序關(guān)系。

    處理重疊線段。根據(jù)線段ID值區(qū)分線段。

    (3)多線相交情況的處理

    對于多線相交的情況,應(yīng)該整體交換它們的次序,即只要找到經(jīng)過交點的所有線段,然后整體交換它們的次序即可。

    2.2維度擴展的9交矩陣及其簡化

    Egenhofer(1991)等用9交模型(9IM)描述點、線、面間的拓?fù)潢P(guān)系[3]。9交模型利用了對象內(nèi)部、邊界和外部相交的拓?fù)洳蛔兞縼韰^(qū)分不同的拓?fù)潢P(guān)系,理論上可區(qū)分的拓?fù)潢P(guān)系數(shù)為29個,但是經(jīng)過Clementini(1995)的總結(jié),認(rèn)為真正有實際意義的空間關(guān)系只有56種[4]。9交模型的定義是:空間實體a,b的拓?fù)潢P(guān)系M(a,b)根據(jù)二者的內(nèi)部、邊界和外部三者的兩兩相交,生成一個3*3的矩陣:

    上式中,a0,?a和a-分別代表空間實體的內(nèi)

    部、邊界和外部,根據(jù)相交結(jié)果矩陣中的元素取值為0或1。

    在9交集矩陣中,矩陣中每個要素的值域是{0,1},即根據(jù)相交生成的幾何體是否為空(0)還是非空(1)設(shè)定。但這種描述是不夠的,還需要相交生成的幾何體的維度信息來確定其空間關(guān)系。經(jīng)過這樣修正的關(guān)系矩陣被稱為維度擴展的9交矩陣,它是這樣定義的:

    上式中,dim(X)的值域是{-1,0,1,2},分別表示交集為空和交集為點、線和面。維度擴展的9交矩陣在理論上有49種關(guān)系類型,經(jīng)過選擇排除,有實際意義的類型共81種。

    Clementini(1995)將線-線拓?fù)潢P(guān)系分為33種,要判斷兩線串之間的拓?fù)潢P(guān)系,必須先研究線段與線段之間的拓?fù)潢P(guān)系。郭慶勝(2000)通過進(jìn)一步歸納總結(jié),將兩線段之間的空間關(guān)系分為14種情況[5],鄧敏(2006)根據(jù)4交叉模型將線線關(guān)系分為11種情況。事實上,在地理信息生產(chǎn)與處理過程中,大多數(shù)線段與線段之間的拓?fù)潢P(guān)系都用不到[6],將其簡化為圖5中5種關(guān)系:

    圖5 地理信息生產(chǎn)與處理過程中線段與線段之間的拓?fù)潢P(guān)系

    上表中的模式串是這樣定義的:將9交集拓?fù)潢P(guān)系矩陣中每個元素按從左到右、從上到下排列而成。圖6所示為線串L1、L2和L3之間的拓?fù)潢P(guān)系。

    圖6 數(shù)字地圖制圖中線串與線串之間的拓?fù)潢P(guān)系

    顯然,線串與線串之間的拓?fù)潢P(guān)系是一系列線段與線段之間局部拓?fù)潢P(guān)系的組合,在圖6中,點1和點2處為局部相接關(guān)系,點3和點9處為局部相交關(guān)系,大的虛線橢圓內(nèi)的線段是線串L2與L3的局部包含關(guān)系。

    3 線—線詳細(xì)拓?fù)潢P(guān)系的識別與檢測

    3.1預(yù)處理

    一是對待輸入的兩條線串進(jìn)行自相交檢查。維度擴展的9交集矩陣本身就不適應(yīng)線串自相交的情形,因此,需將其標(biāo)識出來。問題的關(guān)鍵是如何探測到線段的自相交。常規(guī)的方法是對線串上的所有線段進(jìn)行求交運算,但其運算效率十分低。這里采用趙紅超(2005)提出的INum結(jié)論:即對于兩個不自相交的簡單幾何體,交點的情況可以分成交點0次、1次、2次或者4次四類。定義INum(i)表示交點i的次數(shù),D表示不自相交的簡單幾何體的交點集合,INum結(jié)論可以用數(shù)學(xué)的形式化表達(dá)如下:i∈D,INum(i)={0,1,2, 4},表示不存在自相交,如圖7(a)~(d);如果交點為3,表示不滿足INum結(jié)論,說明存在自相交,如圖7(e)所示。

    圖7 判斷自相交的INum結(jié)論

    二是為提高效率,有必要對待處理的線串集進(jìn)行篩選處理。本文利用線串的最小外接矩形(MBR)來篩選,如圖8所示:算法并不是對線串包含的所有線段進(jìn)行初始化,只是對兩線串的最小外接矩形交集內(nèi)的線段進(jìn)行初始化。

    圖8 輸入線段的優(yōu)化

    3.2線-線詳細(xì)拓?fù)潢P(guān)系的識別

    首先定義存儲所有線串信息的數(shù)據(jù)結(jié)構(gòu)為:

    typedef struct INITIALSTRUCTURE{

    ElementID ID; //線串的ID

    Dpoint3d point[5];//線串的外接矩形

    TongYong tongyong;//線串在數(shù)據(jù)庫中的屬性記錄

    struct INITIALSTRUCTURE *next;

    }Initial-Structure;

    若通過線串中線段的局部拓?fù)潢P(guān)系得到整個線串的詳細(xì)關(guān)系,必須要有相應(yīng)的數(shù)據(jù)庫或文件來記錄這些局部拓?fù)潢P(guān)系,以方便后續(xù)工作的處理??紤]到檢索的效率,本文以索引文件的形式來記錄這些局部拓?fù)潢P(guān)系,表1為圖6三線串局部拓?fù)潢P(guān)系索引文件的記錄形式:

    表1線串局部拓?fù)潢P(guān)系的索引文件記錄

    CIDCPOINTLINEINDEX1LINEINDEX2LINESTRINGID1LINESTRINGID2BianMa1BianMa2MODECODE1(232.483,56.397)004823748376140309140309001000102(268.313,102.751)004837648532140309140307001100103(298.245,145.901)11483764853214030914030701**000*04(403.147,101.492)214837648532140309140307001100105(403.147,101.492)224837648532140309140307001000106(521.431,168.258)324837648532140309140307000010007(600.389,76.591)434837648532140309140307000010008(690.627,103.615)5448376485321403091403070000*00019(746.421,136.367)65483764853214030914030701**000*0

    各數(shù)據(jù)項的具體含義如下。CID:記錄線段交點的順序標(biāo)識號;CPOINT:交點的平面坐標(biāo);LINE INDEX1:第一條相交線段在所屬線串中的索引號;LINE INDEX2:第二條相交線段在所屬線串中的索引號;LINESTRING ID1:唯一標(biāo)識第一條線串的ID號;LINESTRING ID2:唯一標(biāo)識第二條線串的ID號;BianMa1:第一條線串對應(yīng)的編碼;BianMa2:第二條線串對應(yīng)的編碼;MODE CODE:相交線段對應(yīng)的模式串。

    在利用改進(jìn)的平面交點算法對所有線段求交的過程中,每求出一個交點,就往索引文件中寫入一條記錄,待將所有線段求交完畢后,整個索引文件就記錄了所有線串的局部拓?fù)潢P(guān)系。但是在寫入的過程中必須注意,圖6中如果超過兩條線段交于一點時,交點須重復(fù)記錄;對于重合或者局部重合的線段,交點只記錄一次(規(guī)定只記錄末端點)。例如,圖6中,交點4和交點5為重合點,交點6、交點7和交點8只記錄一次。

    要獲取線串的整體詳細(xì)的局部關(guān)系,只需根據(jù)索引文件中記錄的模式串、線串的編碼、線段的索引號,通過檢索和組合即可得到。

    通過前文的分析發(fā)現(xiàn),獲取線線詳細(xì)拓?fù)潢P(guān)系的基本思路是首先將全局的、整體的拓?fù)潢P(guān)系分解為局部的、線段之間的局部拓?fù)潢P(guān)系,然后通過檢索組合獲取線線整體而又詳細(xì)的拓?fù)潢P(guān)系[7]?;玖鞒倘缦拢?/p>

    圖9 獲取線線詳細(xì)的拓?fù)潢P(guān)系

    4 實驗與分析

    4.1重合道路的處理與道路合并

    在地理信息更新生產(chǎn)過程中,存在兩個問題:一個問題是不同等級、相同等級之間完全重合的道路比較多見,一幅數(shù)據(jù)重合的道路可能達(dá)到數(shù)百條之多;另一個問題是數(shù)據(jù)的破碎程度比較嚴(yán)重,有的一條完整的道路由幾十條短小道路組成,若不進(jìn)行處理,更新出來的基礎(chǔ)地理信息數(shù)據(jù)必然會給應(yīng)用帶來很大的困難。為此,需利用本文關(guān)于線線之間的拓?fù)潢P(guān)系的研究成果,根據(jù)相關(guān)的標(biāo)準(zhǔn)和規(guī)范有條件地對重合道路進(jìn)行刪除,對短小的道路進(jìn)行合并。實驗數(shù)據(jù)為某地區(qū)1幅1∶25萬地理信息數(shù)據(jù)。

    刪除重合道路的基本思路是:搜索索引文件中模式串為“00001000”(完全重合)和“0000*1000”(部分重合)的所有線段,找到模式串對應(yīng)兩線段的屬性值(編碼)。若編碼不相同,則將低等級道路(線段)從所在線串中打斷并刪除,同時將索引文件中對應(yīng)的交點標(biāo)識為已經(jīng)處理過;若編碼相同,則根據(jù)線串的ID值找到數(shù)據(jù)庫中該道路的其它屬性值,進(jìn)行有條件刪除,其余處理同上。

    合并短小道路的基本思路是:搜索索引文件中模式串為“00100010”(這類結(jié)點叫“二鏈結(jié)點”或“偽結(jié)點”),并且編碼相同的(道路等級一致)所有線段,根據(jù)相關(guān)標(biāo)準(zhǔn)和規(guī)范進(jìn)行有條件合并,即合并該交點對應(yīng)的兩線段,并將該頂點和對應(yīng)的兩線段標(biāo)識為已經(jīng)處理過。如圖10所示,左圖為重合道路處理后的結(jié)果,黑色位置為刪除后剩余的道路;右圖為道路合并后的結(jié)果,藍(lán)色為合并后的道路。

    4.2地圖要素間關(guān)系沖突的探測

    如前文所述,在基礎(chǔ)地理信息數(shù)據(jù)融合的過程中,必然會造成要素間關(guān)系的不合理、不協(xié)調(diào),例如公路與河流在小范圍內(nèi)的多點相交,河流爬坡,公路、等高線和居民地入水等情況??梢岳帽疚闹醒芯康木€線之間詳細(xì)的拓?fù)潢P(guān)系的方法來探測這些沖突,其基本思路是:

    圖10 道路的重合與合并處理

    首先確定要探測的要素類型,然后根據(jù)編碼在索引文件記錄中查找這些發(fā)生相交、相接、重合與包含關(guān)系的線段與交點,并將這些可能發(fā)生沖突的交點和線段標(biāo)識出來,最后通過人機交互的方式去處理沖突。如圖11所示,縣道與常年河在小范圍發(fā)生沖突,虛線圓為計算機自動探測到的出現(xiàn)交點的地方。需要注意的是,在實際操作中,由于數(shù)據(jù)的情況異常復(fù)雜,因此不可能發(fā)生一次交點就將其標(biāo)識出來,因為在許多情況下這種情況是合理的,比如河流與道路相交的地方有橋就屬于合理的情況,因此這才將其限定為“小范圍內(nèi)的多點相交”。

    圖11 河流與道路之間的沖突

    4.3比較與分析

    為了對本文提出的線-線拓?fù)潢P(guān)系識別與檢測性能進(jìn)行評估,我們與傳統(tǒng)的采用“暴力求交”算法識別線-線拓?fù)潢P(guān)系在相同的硬件環(huán)境和數(shù)據(jù)條件(與4.1數(shù)據(jù)一致,主要檢測識別道路與河流拓?fù)潢P(guān)系)下進(jìn)行實驗,比較二者的耗時情況。橫坐標(biāo)為輸入的線串?dāng)?shù),縱坐標(biāo)為所耗時間,如圖12所示。

    圖12 性能對比

    分析圖12發(fā)現(xiàn),當(dāng)輸入的線串個數(shù)小于500時,本文的方法與“暴力求交”的方法耗時差別不大,但當(dāng)大于500時,“暴力求交”算法耗時成幾何級數(shù)增加,而本文的方法耗時增長曲線沒有成幾何級數(shù)增加。之所以出現(xiàn)這種情況,理論上有以下分析:

    (1)按照“暴力求交”方法,對n條線段兩兩求交,其時間復(fù)雜度為O(n2),而本文算法的時間復(fù)雜度是O((n+k)×logn),空間復(fù)雜度是O(n+k),k為交點個數(shù);

    (2)通過求輸入線串的最小外接矩形交集中的線段,對輸入線段進(jìn)行優(yōu)化,對算法的效率有較大的提高;

    (3)以索引文件的形式存儲線-線局部拓?fù)潢P(guān)系,有助于高效地檢索和獲取線線整體的拓?fù)潢P(guān)系。

    5 結(jié)束語

    高效的線-線拓?fù)潢P(guān)系檢測與識別在地理信息生產(chǎn)處理過程中十分重要。本文利用描述拓?fù)潢P(guān)系的9交集模型和改進(jìn)的平面交點算法重點研究了線-線之間的拓?fù)潢P(guān)系,利用研究成果對道路數(shù)據(jù)中完全重合的道路、部分重合的道路進(jìn)行處理,并對數(shù)據(jù)中比較破碎的道路進(jìn)行有條件合并處理,同時將其應(yīng)用于道路河流空間沖突的檢測,實驗結(jié)果表明本文的方法是高效的。

    [1]趙紅超.空間關(guān)系的研究與實現(xiàn)[D].北京:中國科學(xué)院,2005.

    [2]J. L. Bentley, T. A. Ottmann. Algorithms for Reporting and Counting Geometric Intersections[J]. IEEE Trans. Computer, 1979(9): 643-647.

    [3]EGENHOFER M J,HERRING J.Categorizing binary topological relations between regions,lines and points in graphic databases[R]. Technical Report.Department of Surveying Engineering,University of Maine,1991.

    [4]E. Clementini,P. Di Felice. A Comparison of Methods for Representing Topological Relationships[J]. Information Sciences,1995(3):149-178.

    [5]郭慶勝,劉小利,陳宇箭. 線與線之間的空間拓?fù)潢P(guān)系組合推理[J].武漢大學(xué)學(xué)報·信息科學(xué)版,2006,31(1):40-42.

    [6]鄧敏,李志林,李永禮等. GIS線目標(biāo)間拓?fù)潢P(guān)系描述的4交差模型[J]. 武漢大學(xué)學(xué)報·信息科學(xué)版,2006,31(11):945-978.

    [7]陳軍,劉萬增,李志林等.線目標(biāo)間拓?fù)潢P(guān)系的細(xì)化計算方法[J].測繪學(xué)報,2006,35(3):255-260.

    An Algorithm Identifying Topological Relations between Lines and Its Application

    An Xiaoya1,2,Jin Cheng1,2,3,Xu Daozhu1,2,3

    1. Xi’an Research Institute of Surveying and Mapping , Xi’an 710054,China 2. State Key Laboratory of Geo-information Engineering, Xi’an 710054,China 3. Institute of Geospatial Information, Information Engineering University, Zhengzhou 450001, China

    Identifying line-line topological relations is the focus and difficulty of spatial relations research. This paper is trying to improve plane sweep algorithm, simplify dimension extending 9 intersection matrix and establish index documents of the local topological relations between lines. Then this paper attempts to acquire the holistic and detailed topological relations between lines by searching index documents and compounding. Besides the paper deals with the superposition and combination of the road data, detects and disposes the relations between road and area inhabited. Experiment results show that this method has some advantages such as high efficiency and accuracy in identifying topological relations between lines.

    geographical information processing; topological relations; conflict detection; topological relations matrix

    2015-06-01。

    國家自然科學(xué)基金資助項目(41201469;41071297),地理信息工程國家重點實驗室開放基金資助項目(SKLGIE2013-Z-4-1,SKLGIE2013-M-4-5)。

    安曉亞(1982—),男,助理研究員,主要從事地理信息處理與服務(wù)研究。

    P208

    A

    猜你喜歡
    端點重合交點
    非特征端點條件下PM函數(shù)的迭代根
    不等式求解過程中端點的確定
    閱讀理解
    借助函數(shù)圖像討論含參數(shù)方程解的情況
    參數(shù)型Marcinkiewicz積分算子及其交換子的加權(quán)端點估計
    電力系統(tǒng)單回線自適應(yīng)重合閘的研究
    電子制作(2017年10期)2017-04-18 07:23:07
    試析高中數(shù)學(xué)中橢圓與雙曲線交點的問題
    青年時代(2017年3期)2017-02-17 01:40:47
    基丁能雖匹配延拓法LMD端點效應(yīng)處理
    考慮暫態(tài)穩(wěn)定優(yōu)化的自適應(yīng)重合閘方法
    指數(shù)函數(shù)與冪函數(shù)圖象的交點的探究性學(xué)習(xí)
    女人十人毛片免费观看3o分钟| 久久久久久久亚洲中文字幕| 色婷婷久久久亚洲欧美| 一区二区三区乱码不卡18| 丝袜美腿在线中文| 久久99热这里只频精品6学生| 欧美日韩视频高清一区二区三区二| 国产视频首页在线观看| 综合色丁香网| 搡老乐熟女国产| 久久ye,这里只有精品| 亚洲,欧美,日韩| 久久精品夜色国产| 国产亚洲一区二区精品| 在线 av 中文字幕| 女人十人毛片免费观看3o分钟| 欧美成人a在线观看| 青青草视频在线视频观看| 午夜免费鲁丝| 国产av不卡久久| 国产精品国产三级国产av玫瑰| 97超视频在线观看视频| 一边亲一边摸免费视频| 国产精品精品国产色婷婷| 最近中文字幕高清免费大全6| 性插视频无遮挡在线免费观看| 精品久久久精品久久久| 男插女下体视频免费在线播放| 春色校园在线视频观看| 能在线免费看毛片的网站| 亚洲欧美日韩卡通动漫| 九色成人免费人妻av| 亚洲国产欧美人成| 久久人人爽人人爽人人片va| 国产欧美另类精品又又久久亚洲欧美| 3wmmmm亚洲av在线观看| 国产一区二区在线观看日韩| 九九久久精品国产亚洲av麻豆| 国产精品久久久久久精品电影| 欧美日韩精品成人综合77777| 国内揄拍国产精品人妻在线| 亚洲精品成人久久久久久| 日日啪夜夜撸| 男的添女的下面高潮视频| 男女边摸边吃奶| 久久久久久九九精品二区国产| 日产精品乱码卡一卡2卡三| 精品熟女少妇av免费看| 国产白丝娇喘喷水9色精品| 久久女婷五月综合色啪小说 | 午夜精品一区二区三区免费看| 国产又色又爽无遮挡免| 欧美老熟妇乱子伦牲交| 内射极品少妇av片p| 欧美高清成人免费视频www| 国产淫语在线视频| kizo精华| 99久久九九国产精品国产免费| 国产毛片在线视频| 久久精品国产亚洲av涩爱| 男人添女人高潮全过程视频| 国产高清三级在线| tube8黄色片| 精品一区二区三卡| 夜夜爽夜夜爽视频| 联通29元200g的流量卡| 日韩视频在线欧美| 精品一区二区三卡| 国产精品人妻久久久久久| 久久精品熟女亚洲av麻豆精品| 80岁老熟妇乱子伦牲交| 亚洲国产精品999| 91狼人影院| 亚洲精品一二三| 人妻 亚洲 视频| 亚洲无线观看免费| www.av在线官网国产| 人妻制服诱惑在线中文字幕| 精品国产一区二区三区久久久樱花 | 欧美三级亚洲精品| 国产av码专区亚洲av| 亚洲国产高清在线一区二区三| 两个人的视频大全免费| 成人毛片a级毛片在线播放| 成年女人看的毛片在线观看| 99精国产麻豆久久婷婷| 国产午夜福利久久久久久| 在线天堂最新版资源| 天堂中文最新版在线下载 | 欧美日韩视频精品一区| 亚洲av国产av综合av卡| 日韩av在线免费看完整版不卡| 精品人妻偷拍中文字幕| 亚洲欧美日韩无卡精品| 2021天堂中文幕一二区在线观| 亚洲精品,欧美精品| 久久久午夜欧美精品| 91午夜精品亚洲一区二区三区| 欧美亚洲 丝袜 人妻 在线| 国产黄色免费在线视频| 亚洲一区二区三区欧美精品 | 国产人妻一区二区三区在| 午夜爱爱视频在线播放| 亚洲欧美一区二区三区国产| 少妇熟女欧美另类| av在线app专区| 一个人看视频在线观看www免费| 韩国av在线不卡| 五月天丁香电影| 国模一区二区三区四区视频| 亚洲人与动物交配视频| 欧美日韩亚洲高清精品| 国产欧美日韩一区二区三区在线 | 国产一区有黄有色的免费视频| 国产免费又黄又爽又色| 亚洲三级黄色毛片| 大又大粗又爽又黄少妇毛片口| 亚洲三级黄色毛片| 波多野结衣巨乳人妻| 日日摸夜夜添夜夜添av毛片| 在线精品无人区一区二区三 | 不卡视频在线观看欧美| 国产毛片a区久久久久| 你懂的网址亚洲精品在线观看| 国产精品国产三级专区第一集| 久久久久精品久久久久真实原创| 欧美精品国产亚洲| 国产综合精华液| 国内精品宾馆在线| 欧美成人午夜免费资源| 国产精品人妻久久久久久| 国产男女超爽视频在线观看| 日本与韩国留学比较| 精品午夜福利在线看| 一区二区三区四区激情视频| 青春草国产在线视频| 国产免费又黄又爽又色| 看免费成人av毛片| 亚洲精品乱码久久久久久按摩| 亚洲伊人久久精品综合| 日韩强制内射视频| 久久久久九九精品影院| 亚洲成人一二三区av| 久久久精品免费免费高清| .国产精品久久| 日本与韩国留学比较| 亚洲综合色惰| 搡老乐熟女国产| 国内精品宾馆在线| 免费黄网站久久成人精品| 久久久a久久爽久久v久久| 亚洲,欧美,日韩| 男的添女的下面高潮视频| 亚洲伊人久久精品综合| 天天躁日日操中文字幕| 青春草国产在线视频| 国产色爽女视频免费观看| 亚洲最大成人中文| .国产精品久久| 深夜a级毛片| a级毛片免费高清观看在线播放| 亚洲精品影视一区二区三区av| 免费黄色在线免费观看| 亚洲国产精品国产精品| 久久亚洲国产成人精品v| 成人毛片a级毛片在线播放| 日日撸夜夜添| 国产精品久久久久久av不卡| 建设人人有责人人尽责人人享有的 | 免费高清在线观看视频在线观看| 精品一区二区免费观看| 久久久久久久精品精品| 少妇熟女欧美另类| 免费人成在线观看视频色| av天堂中文字幕网| 国产黄频视频在线观看| 九色成人免费人妻av| 日韩免费高清中文字幕av| 如何舔出高潮| 欧美日本视频| 亚洲精品aⅴ在线观看| 国产精品一及| 日韩成人av中文字幕在线观看| 美女高潮的动态| 小蜜桃在线观看免费完整版高清| 一级毛片黄色毛片免费观看视频| 亚洲av中文av极速乱| 亚洲综合色惰| 精品久久久精品久久久| 免费黄频网站在线观看国产| 岛国毛片在线播放| 91午夜精品亚洲一区二区三区| 我的女老师完整版在线观看| 97热精品久久久久久| 亚洲精品乱码久久久v下载方式| 久久鲁丝午夜福利片| 在线看a的网站| 一区二区av电影网| 午夜免费鲁丝| 国产69精品久久久久777片| 国产色爽女视频免费观看| 日本-黄色视频高清免费观看| 日韩不卡一区二区三区视频在线| 亚洲最大成人av| 五月天丁香电影| 国产亚洲av片在线观看秒播厂| 欧美三级亚洲精品| 搡女人真爽免费视频火全软件| 69人妻影院| 少妇的逼好多水| 天堂中文最新版在线下载 | 国模一区二区三区四区视频| 国产成人精品婷婷| 午夜福利在线观看免费完整高清在| 国产日韩欧美在线精品| 中文字幕久久专区| 国产精品蜜桃在线观看| 在线免费十八禁| 内地一区二区视频在线| 欧美老熟妇乱子伦牲交| 午夜福利高清视频| 亚洲综合色惰| 亚洲国产精品成人综合色| 欧美 日韩 精品 国产| 91狼人影院| 制服丝袜香蕉在线| 美女主播在线视频| 有码 亚洲区| 丰满少妇做爰视频| 狠狠精品人妻久久久久久综合| 小蜜桃在线观看免费完整版高清| 在线天堂最新版资源| 搡女人真爽免费视频火全软件| 一级片'在线观看视频| 性色avwww在线观看| 成人鲁丝片一二三区免费| 波多野结衣巨乳人妻| 熟女电影av网| 视频区图区小说| 99九九线精品视频在线观看视频| 久久国内精品自在自线图片| 欧美日韩亚洲高清精品| 中国美白少妇内射xxxbb| 天天躁夜夜躁狠狠久久av| 一本—道久久a久久精品蜜桃钙片 精品乱码久久久久久99久播 | av卡一久久| 91精品国产九色| 91精品一卡2卡3卡4卡| 久久热精品热| 一级片'在线观看视频| 最近手机中文字幕大全| 亚洲丝袜综合中文字幕| 色网站视频免费| 777米奇影视久久| 日韩亚洲欧美综合| 老师上课跳d突然被开到最大视频| 精品酒店卫生间| eeuss影院久久| 日本爱情动作片www.在线观看| 中文乱码字字幕精品一区二区三区| 日日啪夜夜爽| 成人高潮视频无遮挡免费网站| 美女国产视频在线观看| 亚洲四区av| 久久精品熟女亚洲av麻豆精品| 国产高潮美女av| 久久久精品欧美日韩精品| 成年免费大片在线观看| 国产又色又爽无遮挡免| 精品人妻视频免费看| 黄色怎么调成土黄色| 亚洲精品456在线播放app| 看黄色毛片网站| 欧美日韩在线观看h| av在线播放精品| 人妻系列 视频| 免费av观看视频| 亚洲精品乱码久久久久久按摩| 国产亚洲午夜精品一区二区久久 | 久久久久国产网址| 久久热精品热| 亚洲内射少妇av| 亚洲精品日本国产第一区| 日本一本二区三区精品| 夜夜看夜夜爽夜夜摸| 又粗又硬又长又爽又黄的视频| 麻豆成人午夜福利视频| 大又大粗又爽又黄少妇毛片口| 国产成人精品久久久久久| av又黄又爽大尺度在线免费看| 少妇猛男粗大的猛烈进出视频 | 日韩精品有码人妻一区| 日本av手机在线免费观看| 欧美日韩亚洲高清精品| 国产老妇女一区| 高清日韩中文字幕在线| 亚洲精品影视一区二区三区av| 国产久久久一区二区三区| 免费av不卡在线播放| 国产成人精品婷婷| 久久精品夜色国产| 人妻一区二区av| 亚洲精品成人久久久久久| 国产免费视频播放在线视频| 亚洲av在线观看美女高潮| 国产有黄有色有爽视频| 免费电影在线观看免费观看| 亚洲国产精品成人综合色| 中文在线观看免费www的网站| 欧美三级亚洲精品| 国产国拍精品亚洲av在线观看| 久久精品国产亚洲网站| 高清视频免费观看一区二区| 精华霜和精华液先用哪个| 丝袜美腿在线中文| 国产 一区 欧美 日韩| 色网站视频免费| 亚洲自偷自拍三级| 少妇 在线观看| 亚洲国产精品999| 黄片wwwwww| 国产在视频线精品| 联通29元200g的流量卡| 亚洲精品久久久久久婷婷小说| 一级毛片久久久久久久久女| 别揉我奶头 嗯啊视频| av.在线天堂| 18禁裸乳无遮挡动漫免费视频 | av天堂中文字幕网| 我的女老师完整版在线观看| 亚洲精品国产av成人精品| 联通29元200g的流量卡| 日韩av不卡免费在线播放| 超碰av人人做人人爽久久| 午夜精品国产一区二区电影 | 亚洲欧美成人综合另类久久久| 国产精品久久久久久av不卡| 日韩视频在线欧美| 亚洲一区二区三区欧美精品 | 不卡视频在线观看欧美| 黄片wwwwww| 春色校园在线视频观看| 一级毛片aaaaaa免费看小| 亚洲成人精品中文字幕电影| 亚洲天堂国产精品一区在线| 伊人久久精品亚洲午夜| 亚洲精品,欧美精品| 毛片一级片免费看久久久久| 免费少妇av软件| 亚洲精品亚洲一区二区| 亚洲欧美日韩卡通动漫| 亚洲天堂国产精品一区在线| 亚洲精品乱码久久久久久按摩| 午夜亚洲福利在线播放| 香蕉精品网在线| 高清午夜精品一区二区三区| 亚洲精品国产色婷婷电影| 国产精品蜜桃在线观看| 国产av码专区亚洲av| 亚州av有码| 久久精品国产亚洲网站| 十八禁网站网址无遮挡 | 中文字幕制服av| 在线看a的网站| 青青草视频在线视频观看| 国产乱人偷精品视频| 精品人妻偷拍中文字幕| 久久97久久精品| 男女那种视频在线观看| 国产黄色免费在线视频| 久久久久久久精品精品| 亚洲人成网站在线播| 免费观看在线日韩| 搡老乐熟女国产| 午夜精品国产一区二区电影 | 免费观看a级毛片全部| 一本久久精品| 日韩视频在线欧美| 日韩欧美精品v在线| 一级毛片我不卡| 国产午夜精品一二区理论片| 最新中文字幕久久久久| 简卡轻食公司| 不卡视频在线观看欧美| 一区二区av电影网| 国产片特级美女逼逼视频| kizo精华| 国产伦精品一区二区三区视频9| 好男人在线观看高清免费视频| 特级一级黄色大片| 国产成人免费观看mmmm| 熟女人妻精品中文字幕| 人妻制服诱惑在线中文字幕| 亚洲国产欧美在线一区| 天堂俺去俺来也www色官网| av天堂中文字幕网| 国产亚洲最大av| 精品99又大又爽又粗少妇毛片| 在线观看av片永久免费下载| 观看美女的网站| 国产精品麻豆人妻色哟哟久久| av在线观看视频网站免费| 精品久久久精品久久久| 一级毛片aaaaaa免费看小| av免费观看日本| 久久久久精品性色| 免费看光身美女| 午夜激情久久久久久久| 特大巨黑吊av在线直播| 日韩欧美 国产精品| 国产综合精华液| 成人综合一区亚洲| 97人妻精品一区二区三区麻豆| 美女cb高潮喷水在线观看| 91狼人影院| 国产一区亚洲一区在线观看| 性色av一级| av在线蜜桃| 久久97久久精品| 成年女人在线观看亚洲视频 | 国产v大片淫在线免费观看| 国产av码专区亚洲av| 欧美日韩视频高清一区二区三区二| 伊人久久国产一区二区| 免费高清在线观看视频在线观看| 久久韩国三级中文字幕| av专区在线播放| 男女下面进入的视频免费午夜| 国产精品一区www在线观看| 成人亚洲精品一区在线观看 | 欧美亚洲 丝袜 人妻 在线| 大香蕉97超碰在线| av在线亚洲专区| 色吧在线观看| 热re99久久精品国产66热6| 天堂中文最新版在线下载 | 婷婷色av中文字幕| 免费观看av网站的网址| 视频中文字幕在线观看| 亚洲在线观看片| 五月伊人婷婷丁香| 久久久久网色| 伦理电影大哥的女人| 我要看日韩黄色一级片| av在线老鸭窝| 五月伊人婷婷丁香| 亚洲成人久久爱视频| 人体艺术视频欧美日本| 国产精品女同一区二区软件| 丝袜喷水一区| 日日啪夜夜撸| 毛片女人毛片| 免费大片黄手机在线观看| 一级a做视频免费观看| 国产在线一区二区三区精| 亚洲精品日韩av片在线观看| 国产片特级美女逼逼视频| 国产精品.久久久| 亚洲av电影在线观看一区二区三区 | 直男gayav资源| 国产精品国产三级专区第一集| 国语对白做爰xxxⅹ性视频网站| 久久鲁丝午夜福利片| 一级毛片电影观看| 在线观看人妻少妇| 少妇被粗大猛烈的视频| 成人二区视频| 乱码一卡2卡4卡精品| 少妇人妻一区二区三区视频| 熟女人妻精品中文字幕| 国产精品久久久久久久电影| 毛片一级片免费看久久久久| 亚洲在久久综合| 精品久久国产蜜桃| 丝袜喷水一区| 精品国产三级普通话版| 男人爽女人下面视频在线观看| 久久久久久久久久久免费av| 黄色怎么调成土黄色| a级一级毛片免费在线观看| 免费不卡的大黄色大毛片视频在线观看| 亚洲久久久久久中文字幕| 久久99蜜桃精品久久| 国产黄色视频一区二区在线观看| 全区人妻精品视频| 毛片一级片免费看久久久久| 午夜免费男女啪啪视频观看| 我的女老师完整版在线观看| 成年av动漫网址| 亚洲精品视频女| 成年人午夜在线观看视频| 免费av不卡在线播放| av在线播放精品| 日日摸夜夜添夜夜添av毛片| 精品久久国产蜜桃| 日本一本二区三区精品| 亚洲熟女精品中文字幕| 久久久久精品性色| 人人妻人人澡人人爽人人夜夜| 男女边吃奶边做爰视频| 一级爰片在线观看| 一级毛片 在线播放| 九九爱精品视频在线观看| 日韩欧美精品v在线| 性色av一级| 国产黄频视频在线观看| 午夜爱爱视频在线播放| 欧美xxⅹ黑人| 亚洲四区av| 天堂中文最新版在线下载 | 一级av片app| 街头女战士在线观看网站| 久久久久性生活片| 久久久午夜欧美精品| 麻豆乱淫一区二区| 男女啪啪激烈高潮av片| 国产精品嫩草影院av在线观看| 亚洲精品aⅴ在线观看| 国产亚洲av嫩草精品影院| 国产有黄有色有爽视频| 日韩欧美精品免费久久| 国产精品.久久久| av在线播放精品| 亚洲性久久影院| 18禁在线播放成人免费| 国产毛片在线视频| 欧美一区二区亚洲| 国产伦理片在线播放av一区| 搡老乐熟女国产| 午夜免费男女啪啪视频观看| a级毛片免费高清观看在线播放| 日韩电影二区| 国产伦精品一区二区三区视频9| 高清毛片免费看| 亚洲av成人精品一二三区| 国产乱人偷精品视频| 亚洲综合色惰| 国产在线一区二区三区精| 亚洲av成人精品一二三区| 国产爽快片一区二区三区| 少妇丰满av| 在线亚洲精品国产二区图片欧美 | 一个人看视频在线观看www免费| 夫妻午夜视频| 成人午夜精彩视频在线观看| av一本久久久久| 国产精品人妻久久久久久| 欧美国产精品一级二级三级 | 视频中文字幕在线观看| 国产探花极品一区二区| 嫩草影院新地址| 十八禁网站网址无遮挡 | 三级国产精品欧美在线观看| 国产精品嫩草影院av在线观看| 永久免费av网站大全| av女优亚洲男人天堂| 精品人妻偷拍中文字幕| 最近的中文字幕免费完整| 汤姆久久久久久久影院中文字幕| 日韩一区二区三区影片| 少妇人妻一区二区三区视频| 91精品国产九色| 精品久久久久久久久亚洲| 中文字幕制服av| 国产精品av视频在线免费观看| 欧美高清性xxxxhd video| 久久久成人免费电影| 日日啪夜夜爽| 在线观看三级黄色| 亚洲三级黄色毛片| 国产黄a三级三级三级人| 人人妻人人看人人澡| 综合色丁香网| 女人久久www免费人成看片| 一区二区三区免费毛片| 肉色欧美久久久久久久蜜桃 | 在线天堂最新版资源| 久久久久精品性色| 婷婷色麻豆天堂久久| 成人二区视频| 成人国产麻豆网| 老师上课跳d突然被开到最大视频| 爱豆传媒免费全集在线观看| 联通29元200g的流量卡| 国产亚洲最大av| 99re6热这里在线精品视频| 欧美成人a在线观看| 一级毛片黄色毛片免费观看视频| 大香蕉97超碰在线| 亚洲精品自拍成人| 国产69精品久久久久777片| eeuss影院久久| 国产 一区 欧美 日韩| 亚洲国产欧美人成| 99re6热这里在线精品视频| 天天躁日日操中文字幕| 国产精品久久久久久久电影| 水蜜桃什么品种好| 日韩欧美精品v在线| 99久久人妻综合| 自拍欧美九色日韩亚洲蝌蚪91 | 少妇猛男粗大的猛烈进出视频 | 久久韩国三级中文字幕| 欧美区成人在线视频| 亚洲成人久久爱视频| 国产精品福利在线免费观看| av线在线观看网站| 久久人人爽人人爽人人片va| 亚洲人成网站在线观看播放| 午夜亚洲福利在线播放| 精品国产露脸久久av麻豆| 国产精品久久久久久精品电影小说 | 欧美高清成人免费视频www| 国产高清有码在线观看视频| 美女脱内裤让男人舔精品视频|