[發(fā)明專利]一種障礙空間中連續(xù)范圍Skyline查詢

在審

• 申請?zhí)枺?/td>: 202111001293.1
• 申請日: 2021-08-30
• 公開（公告）號: CN113688331A
• 公開（公告）日: 2021-11-23
• 發(fā)明（設(shè)計）人: 王冠群;李松;張麗平
• 申請（專利權(quán)）人: 哈爾濱理工大學(xué)
• 主分類號: G06F16/9537
• 分類號: G06F16/9537
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種障礙空間中連續(xù)范圍Skyline查詢方法，其特征在于，該方法步驟如下：

步驟1：計算數(shù)據(jù)點集中靜態(tài)Skyline點，并求出距離查詢點最遠(yuǎn)的Skyline點，若查詢點和Skyline點是可視的，則以查詢點為圓心，以查詢點和Skyline點的歐式距離為半徑做圓，若查詢點和Skyline點是不可視的，則查詢點到Skyline點的障礙距離為半徑做圓，剪枝圓外的數(shù)據(jù)點，這樣可以有效避免重復(fù)計算；

步驟2：根據(jù)查詢點和興趣點距離的交叉時刻來構(gòu)建模型，其中不同的興趣點在距離上會相交；

步驟3：根據(jù)興趣點之間的靜態(tài)屬性來判斷是否滿足剪枝策略，如果滿足，無需構(gòu)建event事件，否則構(gòu)建event事件；

步驟4：構(gòu)建event事件，將相交時間，前繼節(jié)點和后繼節(jié)點插入event中，并表明該事件所屬的類型；

步驟5：將event事件加入隊列中，將event事件中的前繼節(jié)點按照距離查詢點的距離，按照從小到大插入隊列中，因為距離查詢點最近的會最先處理；

步驟6：處理event隊列中的事件，并按照事件的所屬類型更新Skyline集；

步驟7：更新Skyline結(jié)果集。

2.根據(jù)權(quán)利要求1所述的一種基于障礙空間的移動用戶連續(xù)范圍Skyline查詢方法，其特征在于：所述的步驟1利用興趣點的靜態(tài)屬性有效剪枝無效的興趣點，避免了大量無效的計算。

3.根據(jù)權(quán)利要求1所述的一種基于障礙空間的移動用戶連續(xù)范圍Skyline查詢方法，其特征在于：所述的步驟2中，查詢點距離興趣點計算方法如下所示：

當(dāng)查詢范圍R和數(shù)據(jù)點p之間沒有障礙物時，此時的距離函數(shù)可以表達為：dist(R,p,t)=，其中，a、b和c是系數(shù)，由它們的起始位置和速度決定的，若R的起始位置是(x_R,y_R)、速度是(v_Rx,v_Ry)，p的起始位置是(x_p,y_p)、速度是(v_px,v_py)，則a=(v_px-v_Rx)²+(v_py-v_Ry)²，b=2[(x_p-x_R)(v_px-v_RX)+(y_p-y_R)(v_py-v_Ry)]，c=(x_p-x_R)²+(y_p-y_R)²，當(dāng)數(shù)據(jù)點p靜止時，a、b和c仍然由此公式?jīng)Q定，當(dāng)查詢范圍R和數(shù)據(jù)點p之間有障礙物時，此時的距離函數(shù)可以表達為：

其中，n為可見點總數(shù)，直線段e_ie_i+1不與任何障礙物相交，dist_e表示線段e_ie_i+1的歐幾里得距離的長度，r為查詢范圍半徑。