吳 濤，向隆剛，龔健雅

1．中南大學(xué)地球科學(xué)與信息物理學(xué)院，湖南 長(zhǎng)沙410083；2．武漢大學(xué)測(cè)繪遙感信息工程國(guó)家重點(diǎn)實(shí)驗(yàn)室，湖北 武漢430079；3．地球空間信息技術(shù)協(xié)同創(chuàng)新中心，湖北 武漢430079

1 引 言

伴隨著各種定位技術(shù)的日趨成熟，以及移動(dòng)終端的廣泛應(yīng)用，使得海量規(guī)模的移動(dòng)對(duì)象的時(shí)空數(shù)據(jù)以軌跡的形式保存下來(lái)，給國(guó)內(nèi)外學(xué)者提供了一個(gè)深入探索移動(dòng)行為的契機(jī)，更拓展了全新的技術(shù)應(yīng)用和服務(wù)領(lǐng)域［1］。近年來(lái)，眾多學(xué)者圍繞軌跡數(shù)據(jù)的組織管理［2－6］、索引查詢［7－8］和分析挖掘［9－15］等方面進(jìn)行了大量研究，并取得了豐碩的成果。其中在軌跡數(shù)據(jù)組織方面比較典型的有，文獻(xiàn)［2—4］基于已有空間模塊類型組織軌跡的點(diǎn)串?dāng)?shù)據(jù)，研制了一系列的軌跡數(shù)據(jù)庫(kù)（如 DOMINO［2］、SECONDO［3］和TrajStore［4］）；文獻(xiàn)［5］針對(duì)軌跡變化，基于 Reeb圖研究了軌跡數(shù)據(jù)的組織框架；文獻(xiàn)［6］面向路網(wǎng)中移動(dòng)數(shù)據(jù)，通過(guò)改進(jìn)Douglas－Peucker算法實(shí)現(xiàn)了軌跡數(shù)據(jù)的高效壓縮組織。

軌跡是對(duì)象在地理空間中移動(dòng)過(guò)程的記錄，其數(shù)據(jù)表現(xiàn)為攜帶對(duì)象位置與時(shí)間信息的離散時(shí)空點(diǎn)P（x，y，t）序列（例如P1→P2→P3→…）。從其空間特征出發(fā)，它在地理空間中的投影是有向線，稱為軌跡線。顯然，線－面拓?fù)潢P(guān)系方面的研究直接與本文密切相關(guān)。拓?fù)鋵W(xué)在描繪軌跡移動(dòng)相關(guān)的地理事件特性的認(rèn)知中扮演者相當(dāng)重要的角色［16－17］。為了表達(dá)拓?fù)潢P(guān)系，文獻(xiàn)［18］基于點(diǎn)集拓?fù)涮岢龅?交模型區(qū)分出了19種線－面拓?fù)潢P(guān)系；文獻(xiàn)［19］提出改進(jìn)的9交模型能描述26種有向線與單區(qū)域間的拓?fù)潢P(guān)系；文獻(xiàn)［20］基于Voronoi提出的空間代數(shù)區(qū)分出了拓?fù)潢P(guān)系中包括6種基本的線－面關(guān)系；文獻(xiàn)［21］提出了線面目標(biāo)間拓?fù)潢P(guān)系的層次表達(dá)方法，結(jié)合相應(yīng)的圖例，可以精確描述復(fù)合的線－面拓?fù)潢P(guān)系；文獻(xiàn)［22］提出的組合描述可以得到97種線－面拓?fù)潢P(guān)系；文獻(xiàn)［23—25］基于目標(biāo)整體交－差和歐拉數(shù)提出的拓?fù)潢P(guān)系模型覆蓋了19種線面拓?fù)潢P(guān)系；文獻(xiàn)［26］通過(guò)引入節(jié)點(diǎn)度，進(jìn)一步研究了線－面拓?fù)潢P(guān)系細(xì)分方法，總結(jié)出21種有意義的線－面單元交線類型。

回歸到軌跡的本質(zhì)，軌跡并不是簡(jiǎn)單的有向線，而是對(duì)象在空間中的移動(dòng)過(guò)程記錄，包含了對(duì)象在整個(gè)移動(dòng)過(guò)程中的時(shí)間信息、位置信息以及特定的行為或移動(dòng)模式。合理的組織和描述這些重要信息對(duì)于后續(xù)更進(jìn)一步研究移動(dòng)對(duì)象至關(guān)重要，比如游客軌跡中的停留行為對(duì)于行程規(guī)劃的研究是至關(guān)重要的信息。當(dāng)前軌跡描述或直接對(duì)原始的GPS點(diǎn)位序列數(shù)據(jù)進(jìn)行組織（如前文所述），或以特定的語(yǔ)義標(biāo)簽描述特定環(huán)境中的移動(dòng)對(duì)象軌跡（如文獻(xiàn)［26］以興趣點(diǎn)為節(jié)點(diǎn)和移動(dòng)方式為弧段描述路網(wǎng)移動(dòng)對(duì)象的軌跡），較少考慮從拓?fù)浣嵌葋?lái)研究對(duì)象軌跡的移動(dòng)過(guò)程，更缺少軌跡相對(duì)于區(qū)域的拓?fù)溥^(guò)程研究。軌跡－區(qū)域的拓?fù)溥^(guò)程描述可以直觀地反映出軌跡相對(duì)區(qū)域時(shí)空拓?fù)潢P(guān)系，以及移動(dòng)對(duì)象的行為語(yǔ)義（如起始、終止、停留等），且不受特定環(huán)境限制，即路網(wǎng)中的移動(dòng)（如車(chē)輛在路網(wǎng)中的移動(dòng)）和自由空間移動(dòng)的軌跡（如臺(tái)風(fēng)的移動(dòng)）。此外，軌跡相對(duì)于多區(qū)域的拓?fù)溥^(guò)程尚未有研究涉及，而實(shí)際場(chǎng)景中移動(dòng)對(duì)象軌跡往往游走于地理空間上多個(gè)區(qū)域之間。具體到應(yīng)用的層面，軌跡－區(qū)域移動(dòng)過(guò)程研究少涉及對(duì)于軌跡－區(qū)域拓?fù)溥^(guò)程查詢分析方面的支持。

完整的時(shí)空拓?fù)溥^(guò)程模型不僅要從空間層面上描述對(duì)象軌跡與區(qū)域之間存在的線／面拓?fù)潢P(guān)系，還應(yīng)當(dāng)覆蓋對(duì)象在其移動(dòng)過(guò)程中附帶語(yǔ)義的行為。軌跡相對(duì)于區(qū)域的移動(dòng)過(guò)程中發(fā)生的起始點(diǎn)、終止點(diǎn)、交疊點(diǎn)和停留點(diǎn)所表達(dá)的語(yǔ)義對(duì)于研究軌跡－區(qū)域時(shí)空關(guān)系方面是至關(guān)重要的，本文將其統(tǒng)稱為關(guān)鍵點(diǎn)。本文從拓?fù)浣嵌瘸霭l(fā)，基于關(guān)鍵點(diǎn)來(lái)探討軌跡與區(qū)域地理要素（面狀）之間的時(shí)空過(guò)程，采用分解組合策略，將軌跡與地理要素之間的復(fù)雜拓?fù)溥^(guò)程分解為若干個(gè)局部拓?fù)潢P(guān)系，以基于點(diǎn)集拓?fù)涞慕化B模型判定拓?fù)湔Z(yǔ)義，發(fā)掘不同區(qū)分能力的拓?fù)洳蛔兞?；然后基于軌跡數(shù)據(jù)的時(shí)間特征與行為語(yǔ)義，結(jié)合STOP－MOVE的語(yǔ)義結(jié)構(gòu)，設(shè)計(jì)軌跡－區(qū)域語(yǔ)義關(guān)聯(lián)模型得到切合人們思維習(xí)慣的軌跡相對(duì)區(qū)域的全局拓?fù)溥^(guò)程表達(dá)，進(jìn)而將該拓?fù)溥^(guò)程表達(dá)框架從軌跡－單區(qū)域的拓?fù)溥^(guò)程表達(dá)推廣至軌跡－多區(qū)域的拓?fù)溥^(guò)程表達(dá)。

2 基于關(guān)鍵點(diǎn)的軌跡－區(qū)域拓?fù)溥^(guò)程模型

2．1 軌跡－區(qū)域關(guān)鍵點(diǎn)

本文研究提取了軌跡移動(dòng)過(guò)程中4類具有較強(qiáng)語(yǔ)義的行為：起始、終止、停留和交疊。在此基礎(chǔ)上，以這些行為對(duì)應(yīng)的關(guān)鍵點(diǎn)構(gòu)建模型綜合描述軌跡相對(duì)區(qū)域移動(dòng)的拓?fù)溥^(guò)程。

顯然，起始與終止分別對(duì)應(yīng)軌跡的起點(diǎn)與終點(diǎn)。停留行為則指對(duì)象在地理空間中移動(dòng)時(shí)，其軌跡數(shù)據(jù)采樣點(diǎn)的空間位置分布在某一空間點(diǎn)的小鄰域內(nèi)超過(guò)某一給定的時(shí)間閾值。軌跡上發(fā)生停留行為的點(diǎn)稱為停留點(diǎn)。而交疊行為指軌跡經(jīng)過(guò)區(qū)域邊界某點(diǎn)時(shí)，在該點(diǎn)鄰域內(nèi)軌跡線段與區(qū)域邊界之間的局部拓?fù)潢P(guān)系發(fā)生改變。軌跡上發(fā)生交疊行為的關(guān)鍵點(diǎn)稱為交疊點(diǎn)。下文首先將從軌跡－區(qū)域交疊點(diǎn)展開(kāi)描述。

2．2 軌跡－區(qū)域交疊類型

本節(jié)首先基于點(diǎn)集拓?fù)淅碚摚?6－17］，以軌跡線與區(qū)域（r）的3個(gè)拓?fù)浞至浚ㄟ吔?r，內(nèi)部r°和外部r┑）的幾何交疊形態(tài)來(lái)描述和區(qū)分軌跡與區(qū)域?qū)ο笾g的局部拓?fù)潢P(guān)系。

定義1：交疊點(diǎn)（intersection point）。二維空間內(nèi)，如果存在軌跡線與區(qū)域邊界的一個(gè)公共點(diǎn)P，在以該點(diǎn)為中心，半徑為ε（ε足夠小且大于0）的鄰域內(nèi)，連接點(diǎn)P兩端的軌跡線弧段不同時(shí)屬于該區(qū)域邊界時(shí)，則稱P點(diǎn)為軌跡與區(qū)域的一個(gè)交疊點(diǎn)。

如圖1所示，鄰域內(nèi)沿時(shí)間軸方向進(jìn)入交疊點(diǎn)的弧段稱為交疊前弧段（pre＿arc），離開(kāi)交疊點(diǎn)的弧段稱為交疊后弧段（post＿arc）。本文將交疊點(diǎn)限定為0維交點(diǎn)，而軌跡線與區(qū)域邊界一維交疊情況將被視作為在時(shí)間軸上的兩個(gè)相鄰交疊點(diǎn)。

圖1 軌跡－區(qū)域時(shí)空拓?fù)溥^(guò)程Fig．1 The topological process between trajectories and regions

定義2：交疊類型Itp（intersection type）。在交疊點(diǎn)鄰域中，交疊前弧段和交疊后弧段與區(qū)域3個(gè)拓?fù)浞至拷M成的矩陣描述的軌跡與區(qū)域在該點(diǎn)處的局部拓?fù)涮卣鳌?/p>

交疊類型是軌跡與區(qū)域要素空間關(guān)系中的一個(gè)拓?fù)洳蛔兞?。交疊類型矩陣的一般表達(dá)式為

為了更直觀表達(dá)，本文以3×2的方塊矩陣圖形表達(dá)對(duì)應(yīng)于交疊類型矩陣中的元素［17］，通過(guò)枚舉驗(yàn)證所有可能組合的合理性，得到如圖2所示的14種不同的交疊類型。考慮到特定場(chǎng)景中交疊點(diǎn)的進(jìn)入和離開(kāi)弧段可能存在空值，則可將14種交疊類型劃分為3類：基本交疊（basic intersection type，BIT），見(jiàn)圖2（a）—（h）；起點(diǎn)交疊（initial intersection type，IIT），見(jiàn)圖2（i）—（k）；終點(diǎn) 交 疊 （terminal intersection type，TIT），見(jiàn)圖2（l）—（n）。

圖2 交疊類型Fig．2 Types of intersetion

為簡(jiǎn)化表述，本文在交疊類型矩陣的基礎(chǔ)上采用字符編碼描述，弧段與區(qū)域3個(gè)拓?fù)浞至康目战患洖?；非空交集分別記為：b（邊界），i（內(nèi)部）和e（外部）。這14種交疊類型在時(shí)間軸上存在42組概念鄰居關(guān)系，組成了如圖3所示的概念鄰域圖。

圖3 交疊類型概念領(lǐng)域圖Fig．3 Conceptual neighborhood diagram of intersection types

2．3 軌跡－區(qū)域語(yǔ)義關(guān)聯(lián)模型

軌跡并非簡(jiǎn)單的有向線段，單純的交疊關(guān)系并不能完全客觀描述軌跡在真實(shí)地理環(huán)境中的移動(dòng)狀態(tài)。作者綜合考慮軌跡拓?fù)潢P(guān)系與軌跡行為語(yǔ)義，從移動(dòng)對(duì)象相對(duì)于區(qū)域的移動(dòng)軌跡中提取反映軌跡－區(qū)域拓?fù)溥^(guò)程的關(guān)鍵點(diǎn)，構(gòu)造軌跡中的STOP－MOVE語(yǔ)義對(duì)象，映射交疊序列，沿時(shí)間軸建立軌跡關(guān)鍵點(diǎn)與區(qū)域要素的語(yǔ)義關(guān)聯(lián)模型，如圖4所示。實(shí)際場(chǎng)景中，一個(gè)關(guān)鍵點(diǎn)可能同時(shí)描述交疊與停留、交疊與起始或交疊與終止的軌跡語(yǔ)義行為。

圖4 軌跡－區(qū)域語(yǔ)義關(guān)聯(lián)模型Fig．4 Semantic model between trajectories and regions

模型中，“⊕”是語(yǔ)義區(qū)隔符，用于區(qū)隔關(guān)鍵點(diǎn)與區(qū)域要素之間所屬的多個(gè)拓?fù)湔Z(yǔ)義描述；“→”是關(guān)鍵點(diǎn)區(qū)隔符，用于區(qū)隔時(shí)間軸上不同的關(guān)鍵點(diǎn)。進(jìn)而將軌跡－區(qū)域語(yǔ)義關(guān)聯(lián)模型進(jìn)行編碼可以得到軌跡相對(duì)于單個(gè)區(qū)域的拓?fù)溥^(guò)程的三元組表達(dá)

式中，首項(xiàng)［E｜I｜IIT］與末項(xiàng)［E｜I｜TIT］，即軌跡的起點(diǎn)和終點(diǎn)分別標(biāo)記其與區(qū)域之間可能的拓?fù)潢P(guān)系；中間項(xiàng)，描述軌跡與區(qū)域之間的交疊以及停留語(yǔ)義。該編碼中，必有首末兩項(xiàng)，對(duì)應(yīng)軌跡必有起點(diǎn)與終點(diǎn)；中間項(xiàng)可以為空，對(duì)應(yīng)軌跡可能未與區(qū)域發(fā)生過(guò)交疊，或者軌跡過(guò)程中未發(fā)生停留行為等。由此，圖1中示例軌跡T1相對(duì)區(qū)域r6的拓?fù)溥^(guò)程可表達(dá)為：T1（r6）＝〈E，eb→bi，I〉。

模型中結(jié)合交疊類型的概念領(lǐng)域關(guān)系，通過(guò)沿時(shí)間軸順序組合各種交疊類型（基本交疊、起點(diǎn)交疊和終點(diǎn)交疊）可以覆蓋現(xiàn)有研究中常見(jiàn)的各類線／面空間關(guān)系和拓?fù)溥^(guò)程。例如，圖1中軌跡T1對(duì)于的區(qū)域r6的行為，表示為先外部進(jìn)入?yún)^(qū)域邊界（eb），再?gòu)膮^(qū)域邊界進(jìn)入到區(qū)域內(nèi)部（bi）。依此類推，更多復(fù)雜的線面拓?fù)潢P(guān)系都能通過(guò)本模型表達(dá)。

3 軌跡的時(shí)空關(guān)系推導(dǎo)

3．1 多區(qū)域的時(shí)空拓?fù)潢P(guān)系描述

在真實(shí)的場(chǎng)景中軌跡的移動(dòng)過(guò)程可能會(huì)同時(shí)或者陸續(xù)遭遇多個(gè)區(qū)域要素。軌跡－區(qū)域語(yǔ)義關(guān)聯(lián)模型沿軌跡T移動(dòng)方向考查其與區(qū)域集合R中要素的局部語(yǔ)義關(guān)系集，先以軌跡與區(qū)域要素發(fā)生語(yǔ)義行為的關(guān)鍵點(diǎn)切分軌跡線段，然后再按時(shí)序組合一對(duì)多的語(yǔ)義關(guān)系的單元描述，從而得到軌跡對(duì)多個(gè)區(qū)域的拓?fù)溥^(guò)程編碼一般表達(dá)式T（R）＝〈［｜E｜I｜IIT＠r1⊕…｜E｜I｜IIT＠ri⊕…

式中，T（R）是軌跡T相對(duì)于區(qū)域集合R的拓?fù)溥^(guò)程描述；ri為R集合中的某個(gè)區(qū)域；＠為區(qū)域關(guān)聯(lián)符，與其前項(xiàng)的交疊類型和后項(xiàng)的交疊參與區(qū)域共同組成一次局部交疊描述；S為軌跡停留點(diǎn)（與stop序列對(duì)應(yīng)）。需要指出的是，該模型在首尾兩項(xiàng)分別針對(duì)軌跡的起始與終止兩個(gè)關(guān)鍵點(diǎn)處，顯式申明其相對(duì)于所有感興趣區(qū)域的交疊類型，據(jù)此在后續(xù)的解析中（比如，提取其中某個(gè)區(qū)域的拓?fù)溥^(guò)程描述）可以不必通過(guò)附加的計(jì)算即可從中獲取軌跡起止關(guān)鍵點(diǎn)相對(duì)于任意目標(biāo)區(qū)域的拓?fù)潢P(guān)系，避免出現(xiàn)提取之后信息不完備的情況。由此，圖1中軌跡T2相對(duì)區(qū)域集合R（R＝｛r1，r2，r3，r4，r5，r6｝）的拓?fù)溥^(guò)程描述為

3．2 區(qū)域間的拓?fù)潢P(guān)系與軌跡移動(dòng)模式

本質(zhì)上區(qū)域之間的拓?fù)潢P(guān)系在空間和時(shí)間上約束了軌跡相對(duì)于區(qū)域的移動(dòng)模式，表現(xiàn)在模型上為區(qū)域拓?fù)潢P(guān)系對(duì)于交疊行為的約束。本文通過(guò)解讀模型中交疊序列上相接交疊中兩次交疊行為特征，考查連續(xù)兩個(gè)交疊點(diǎn)之間的概念鄰居關(guān)系和相接交疊中隱藏的區(qū)域拓?fù)湫畔?duì)軌跡移動(dòng)模式的約束。

定義3：相接交疊。二維空間內(nèi)，如果軌跡線上沿時(shí)間軸方向存在兩個(gè)不同點(diǎn)先后與至少兩個(gè)不同區(qū)域發(fā)生交疊，則稱這兩個(gè)交疊點(diǎn)為相接交疊。

交疊點(diǎn)在空間中可能同時(shí)與多個(gè)區(qū)域（本文著重考查兩個(gè)區(qū)域，兩個(gè)以上的區(qū)域可以在此基礎(chǔ)上進(jìn)行推導(dǎo)得出，限于篇幅不展開(kāi)闡述）發(fā)生交疊，因此，研究相接交疊時(shí)還要考慮公共交疊點(diǎn)的存在?；谇拔乃龅摹败壽E－區(qū)域交疊類型”，每個(gè)相接交疊都可以分解成n個(gè)交疊類型的組合，即為1－n的對(duì)應(yīng)關(guān)系。

由此，可以得出相接交疊的一般表達(dá)式

式中，［］內(nèi)的交疊關(guān)系為該交疊點(diǎn)在公共邊界時(shí)，與其他區(qū)域發(fā)生的交疊關(guān)系。

本文經(jīng)過(guò)驗(yàn)證后得到如圖5所示的33種不同的相接交疊。

圖5 兩區(qū)域拓?fù)潢P(guān)系對(duì)相接交疊的約束Fig．5 Contiguous intersections between two regions

（1）兩個(gè)區(qū)域外相離時(shí)，相接交疊只表現(xiàn)出一種移動(dòng)模式：“？e＠rA→e？＠rB”，見(jiàn)圖5（1）（“？”表示可取任意合理字（限于篇幅本文不列出所有表達(dá)式）。

（2）兩個(gè)區(qū)域內(nèi)相離時(shí)，相接交疊表現(xiàn)的移動(dòng)模式有兩種：“？i＠rA→e？＠rB”和“？i＠rB→e？＠rA”，見(jiàn)圖5（2）。

（3）兩個(gè)區(qū)域內(nèi)相切時(shí)，相接交疊表現(xiàn)的移動(dòng)模式依據(jù)軌跡與區(qū)域公共邊的關(guān)系，可分為公共弧段未經(jīng)過(guò)公共邊（圖5（3）），公共弧段一次經(jīng)過(guò)公共邊，見(jiàn)圖5（4）—（8），以及公共弧段兩次經(jīng)過(guò)公共邊（圖5（9）—（14））。

（4）兩個(gè)區(qū)域外相切時(shí)，相接交疊表現(xiàn)的移動(dòng)模式依據(jù)軌跡與區(qū)域公共邊的關(guān)系，可分為（軌跡從rA到rB與從rB到rA的相接交疊是對(duì)稱的）：公共弧段未經(jīng)過(guò)公共邊（圖5（15）），公共弧段一次經(jīng)過(guò)公共邊（圖5（16）—（18）），以及公共弧段兩次經(jīng)過(guò)公共邊（圖5（19）—（22））。

（5）兩區(qū)域相交時(shí)，相接交疊表現(xiàn)的移動(dòng)模式依據(jù)軌跡與區(qū)域公共邊的關(guān)系，可分為（軌跡從rA到rB與從rB到rA的相接交疊是對(duì)稱的）：公共弧段未經(jīng)過(guò)公共邊（圖5（23）—（25）），公共弧段一次經(jīng)過(guò)公共邊（圖5（26）—（30）），以及公共弧段兩次經(jīng)過(guò)公共邊（圖5（31）—（33））。

（6）兩區(qū)域重疊時(shí)，軌跡相接交疊相對(duì)于rA到rB所表現(xiàn)的移動(dòng)模式所受約束類似單區(qū)域情況下交疊類型概念鄰域的約束（例如，兩區(qū)域重疊時(shí)相接交疊不可能出現(xiàn)ie＠rA→ie＠rB的情況等）。

4 模型應(yīng)用示例

根據(jù)臺(tái)風(fēng)的原始移動(dòng)軌跡數(shù)據(jù)，基于軌跡－區(qū)域拓?fù)溥^(guò)程模型，可以完整描述其相對(duì)過(guò)境區(qū)域之間的拓?fù)溥^(guò)程，不但可以提取臺(tái)風(fēng)行進(jìn)的移動(dòng)特征，同時(shí)還能為進(jìn)一步的分析與挖掘提供支持。圖6為2008年8月臺(tái)風(fēng)“鳳凰”與2001年1月的臺(tái)風(fēng)“飛燕”在中國(guó)東南沿海一帶的移動(dòng)路徑圖。

圖6 臺(tái)風(fēng)軌跡移動(dòng)Fig．6 Movements of typhoon trajectories

以“鳳凰”為例，T1與中國(guó)東南部各地區(qū)之間的模型描述為

從其模型描述可以解讀拓?fù)溥^(guò)程的完整信息：起于所有陸地區(qū)域之外的太平洋（E＠r1⊕E＠r2⊕E＠r3⊕E＠r4⊕E＠r5⊕E＠r6⊕E＠r7⊕E＠r8）；依次穿過(guò)r1、r2兩個(gè)區(qū)域，從r2、r3的共同邊界進(jìn)入r3區(qū)域（ei＠r1→ie＠r1→ei＠r2→ie＠r2→ei＠r3）；在r3中繼續(xù)移動(dòng)，最后在區(qū)域r3、r4和r6的邊界交點(diǎn)處終止（E＠r1⊕E＠r2⊕i?＠r3⊕e?＠r4⊕E＠r5⊕e?＠r6⊕E＠r7⊕E＠r8）。

5 結(jié) 論

本文從空間拓?fù)潢P(guān)系出發(fā)，提出了一種基于關(guān)鍵點(diǎn)的軌跡－區(qū)域拓?fù)溥^(guò)程模型。該模型通過(guò)軌跡的起關(guān)鍵點(diǎn)，表達(dá)軌跡移動(dòng)過(guò)程中所固有的拓?fù)洳蛔兞考罢Z(yǔ)義信息。首先基于交疊關(guān)鍵點(diǎn)提出軌跡－區(qū)域交疊類型描述，以交疊類型矩陣分析確定了14種交疊類型，并采用字符編碼表達(dá)，從局部拓?fù)潢P(guān)系開(kāi)始討論，進(jìn)而依據(jù)交疊類型在單－多區(qū)域情況下的組合約束，設(shè)計(jì)軌跡－區(qū)域關(guān)聯(lián)語(yǔ)義模型，導(dǎo)出切合人們思維習(xí)慣的符號(hào)化描述，直觀表達(dá)軌跡－區(qū)域的全局拓?fù)溥^(guò)程，并在此表達(dá)框架上按一定約束完成復(fù)雜軌跡的時(shí)空推導(dǎo)。本文提出的面向關(guān)鍵點(diǎn)的軌跡－區(qū)域拓?fù)溥^(guò)程模型相對(duì)于其他模型，具有以下3個(gè)特點(diǎn)：

（1）以起始點(diǎn)、終止點(diǎn)、交疊點(diǎn)以及停留點(diǎn)等作為軌跡－區(qū)域拓?fù)溥^(guò)程的關(guān)鍵點(diǎn)，從拓?fù)浣嵌葘?duì)其進(jìn)行語(yǔ)義描述，以表達(dá)軌跡相對(duì)于區(qū)域的隨時(shí)間演變的語(yǔ)義拓?fù)潢P(guān)系。

（2）軌跡對(duì)于區(qū)域而言，其關(guān)鍵點(diǎn)表達(dá)的拓?fù)涮卣鲀H在局部范圍內(nèi)有效，據(jù)此，引入關(guān)鍵點(diǎn)鄰域概念，在此基礎(chǔ)上建立鄰域內(nèi)的交疊類型矩陣，并進(jìn)行簡(jiǎn)單直觀地編碼表達(dá)，例如，eb＠r3表示軌跡從外部進(jìn)入?yún)^(qū)域r3的邊界，且沿著邊界方向移動(dòng)。

（3）在關(guān)鍵點(diǎn)編碼的基礎(chǔ)上，提出了軌跡－區(qū)域拓?fù)溥^(guò)程模型，不僅可以有效表達(dá)軌跡相對(duì)于單個(gè)區(qū)域以及多個(gè)區(qū)域間各種復(fù)雜的拓?fù)溥^(guò)程，還能反映區(qū)域間的拓?fù)潢P(guān)系對(duì)于軌跡在區(qū)域間移動(dòng)模式的約束。

本文后續(xù)的研究工作將研究從原始軌跡數(shù)據(jù)中提取空間拓?fù)潢P(guān)系和停留點(diǎn)的算法，計(jì)算生成軌跡－區(qū)域拓?fù)溥^(guò)程模型，并考慮基于本文模型分析挖掘軌跡－區(qū)域拓?fù)湟苿?dòng)過(guò)程的模式。

［1］ ZHENG Yu，ZHOU Xiaofang．Computing with Spatial Trajectories［M］．New York：Springer，2011．

［2］ WOLFSON O，SISTLA P，XU Bo，et al．Tracking Moving Objects Using Database Technology in DOMINO［C］∥Proceedings of the 4th Workshop on Next Generation Information Technologies and Systems（NGITS）．Zikhron－Yaakov，Israel：［s．n．］，1999：112－119．

［3］ GüTING R H，BEHR T，ALMEIDA V，et al．SECONDO：An Extensible DBMS Architecture and Prototype［J］．Collaborative Design，2004：439－450．

［4］ CUDRé－MAUROUX P，WU E，MADDEN S．Trajstore：An Adaptive Storage System for Very Large Trajectory Data Sets［C］∥ICDE Conference．［S．l．］：IEEE，2010：109－120．

［5］ BUCHIN K，BUCHIN M，VAN KREVELD M，et al．Trajectory Grouping Structure［C］∥DEHNE F，SOLISOBA R，SACK J R．Proceedings of the 13th International Symposium WADS．Berlin：Springer，2013：219－230．

［6］ POPAI S，ZEITOUNI K，ORIA V，et al．Spatio－temporal Compression of Trajectories in Road Networks［J］．Geoinformatica，2015，9（1）：117－145．

［7］ VIEIRA M R，BAKALOV P，TSOTRAS V J．Querying Trajectories Using Flexible Patterns［C］∥Proceedings of the 13th International Conference on Extending Database Technology．New York：ACM，2010：406－417．

［8］ FREN TZOS E，GRATSIAS K，T HEODORIDIS Y．Index－based Most Similar Trajectory Search ［C］∥Proceedings of the IEEE International Conference on Data Engineering．Istanbul：IEEE，2007：816－825．

［9］ ZHENG Kai，ZHENG Yu，YUAN N J，et al．On Discovery of Gathering Patterns from Trajectories［C］∥Proceedings of the IEEE International Conference on Data Engineering．Washington，D．C．：IEEE，2013．

［10］ CAO Xin，CONG Gao，JENSEN C S．Mining Significant Semantic Locations from GPS Data［J］．Proceedings of the VLDB Endowment，2010，3（1－2）：1009－1020．

［11］ HADJIELEFTHERIOU M，KOLLIOS G，GUNOPULOSD，et al．On－line Discovery of Dense Areas in Spatio－temporal Databases［C］∥HADZILACOST，MANOLOPOULOS Y，RODDICK J，et al．Advances in Spatial and Temporal Databases．Berlin：Springer，2003：306－324．

［12］ LEE J G，H AN Jiawei，LI Xiaolei．Trajectory Outlier Detection：A Partition and Detect Framework［C］∥Proceedings of the IEEE International Conference on Data Engineering．Cancun，Mexico：IEEE，2008：140－149．

［13］ QUDDUS M A，OCHIENG W Y，NOLAND R B．Current Map－matching Algorithms for Transport Applica－tions：State－of－the－art and Future Research Directions［J］．Transportation Research Part C：Emerging Technologies，2007，15（5）：312－328．

［14］ SPACCAPIETRA S，PARENT C，DAMIANI M L，et al．A Conceptual View on Trajectories［J］．Data ＆Knowledge Engineering，2008，65（1）：126－146．

［15］ YING J J C，LEE W C，WENG T C，et al．Semantic Trajectory Mining for Location Prediction［C］∥Proceedings of the 19th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems．Chicago：ACM，2011：34－43．

［16］ KLIPPELA．Spatial Information Theory Meets Spatial Thinking：Is Topology the Rosetta Stone of Spatio－temporal Cognition？［J］．Annals of the Association of American Geographers，2012，102（6）：1310－1328．

［17］ EGENHOFER M J，F(xiàn)RANZOSA R D．Point－set Topological Spatial Relations［J］．International Journal of Geographical Information Systems，1991，5（2）：161－174．

［18］ KURATAY．Three－valued 9－intersection for Deriving Possible Topological Relations from Incomplete Observations［M］∥SESTER M，BERNARD L，PAELKE V．Advances in GIS Science．Berlin：Springer，2009：289－308．

［19］ KURATAY．9＋－intersection Calculi for Spatial Reasoning on the Topological Relations between Heterogeneous Objects［C］∥Proceedings of the 18th SIGSPATIAL International Conference on Advances in Geographic Information Systems．San Jose，CA：ACM，2010：390－393．

［20］ LI Zhilin，ZH AO Renliang，CHEN Jun．A Voronoibased Spatial Algebra for Spatial Relations［J］．Progress in Natural Science，2002，12（7）：528－536．

［21］ DENG Min，MA Hangying．The Hierarchical Representation of Topological Relations between a Line and an Area［J］．Acta Geodaetica et Cartographica Sinica，2008，37（4）：507－520．（鄧敏，馬杭英．線與面目標(biāo)間拓?fù)潢P(guān)系的層次表達(dá)方法［J］．測(cè)繪學(xué)報(bào)，2008，37（4）：507－520．）

［22］ GUO Qingsheng，CHEN Yujian，LIU Hao．Combinational Reasoning of Spatial Topological Relations between a Line and an Area［J］．Geomatics and Information Science of Wuhan University，2005，30（6）：529－532．（郭慶勝，陳宇箭，劉浩．線與面的空間拓?fù)潢P(guān)系組合推理［J］．武漢大學(xué)學(xué)報(bào)：信息科學(xué)版，2005，30（6）：529－532．）

［23］ ZHOU Xiaoguang，CHEN Jun，LI Zhilin，et al．Computation of Topological Relations between Cadastral Objects Based on Euler－number［J］．Acta Geodaetica et Cartographica Sinica，2006，35（3）：293－298．（周曉光，陳軍，李志林，等．基于歐拉數(shù)的地籍拓?fù)潢P(guān)系計(jì)算［J］．測(cè)繪學(xué)報(bào)，2006，35（3）：293－298．）

［24］ ZHOU Xiaoguang，CHEN Jun，ZHAN FB，et al．A Euler Number－based Topological Computation Model for Land Parcel Database Updating［J］．International Journal of Geographical Information Science，2013，27（10）：1983－2005．

［25］ ZHOU Xiaoguang，CHEN Fei，CHEN Jun．A Node－degree Based Line／Region Topological Relationship Refinement Model and Its Applications［J］．Acta Geodaetica et Cartographica Sinica，2015，44（4）：445－452．（周曉光，陳斐，陳軍．引入結(jié)點(diǎn)度的線面拓?fù)潢P(guān)系細(xì)分方法與應(yīng)用［J］．測(cè)繪學(xué)報(bào)，2015，44（8）：445－452．）

［26］ SESTERM，F(xiàn)EUERH AKE U，KUNTZSCH C，et al．Revealing Underlying Structure and Behaviour form Movement Data［J］．Künstliche Intelligenz，2012，26（3）：223－231．

［27］ EGENHOFER M J，MARK D M．Modeling Conceptual Neighborhoods of Topological Line－region Relations［J］．International Journal of Geographical Information Systems，1995，9（5）：555－565．