[發明專利]一種空間方向感知地圖興趣點搜索方法和系統

有效

• 申請號: 201110402795.5
• 申請日: 2011-12-07
• 公開（公告）號: CN103150309A
• 公開（公告）日: 2013-06-12
• 發明（設計）人: 李國良;黃維篁;馮建華
• 申請（專利權）人: 清華大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 北京潤澤恒知識產權代理有限公司 11319
• 代理人: 蘇培華

1.一種空間方向感知地圖興趣點搜索方法，其特征在于，包括：

步驟N1，接收用戶查詢請求，所述請求包括查詢點經緯度、查詢方位、返回結果個數k和關鍵詞集合K；所述查詢方位包括從查詢點出發的兩條直線與指定坐標軸方向的夾角范圍內的區域；

步驟N2，創建兩個優先級隊列Q_R和Q_P，分別用于存放有待進一步探查的子區域和興趣點；

步驟N3，根據所述查詢方位將所述查詢分解到相應各坐標系地圖中；

步驟N4，計算查詢點與相應各坐標系地圖原點的距離，根據所述距離確定查詢點所在環區域并將其加入Q_R中；其中，Q_R中的區域按距離遠點的距離從近至遠排序；

步驟N5，按順序遍歷Q_R中的區域，并根據索引查找符合查詢方位覆蓋區域、關鍵詞集合K條件的k個興趣點；

步驟N6，將查找結果返回至用戶端；所述查找結果包括Q_P中滿足關鍵詞與方向約束的距查詢點距離最小的k個興趣點；

其中，所述索引通過如下步驟構建：

步驟M1，獲取地圖信息，分別以地圖平面中的四個頂點作為坐標原點O，建立四個坐標系地圖，并調整其中三個坐標系地圖的屬性至與另外一個坐標系地圖屬性相同；其中所述地圖信息包括各興趣點在經緯度和各興趣點的關鍵詞集合；

步驟M2，針對每一個坐標系地圖，以所述原點為圓心，按照到原點的距離，通過N個1/4圓環將所述坐標系地圖切分為N個環區域R_i(1≤i≤N)，所述每個環區域包括的興趣點個數相似；

步驟M3，針對所述切分后的每個區域，通過沿半徑方向多條直線將所述環區域切分為M個子區域，所述每個子區域中包括的興趣點個數相似；并計算每個興趣點與指定正半軸夾角，和每個子區域各興趣點所在的夾角范圍[θ_i，j-1，θ_i，j)，其中θ_{i，(j-1)}表示B_i，j(1≤j≤M)中的角度最小點的角度；

步驟M4，關鍵詞k_i到包括該關鍵詞的子區域的倒排索引L_ki^R，并建立關鍵詞k_i到包括該關鍵詞的興趣點的倒排索引L_ki^P；所述子區域與該子區域的所述興趣點對應并且所述兩個索引序關系相同，所述序關系按照距原點的從近到遠排序；所述各子區域中興趣點按與特征方向正半軸的夾角排序。

2.根據權利要求1所述的方法，其特征在于，通過如下步驟調整其中三個坐標系地圖的屬性與另外一個坐標系地圖屬性相同：

以地圖左下角頂點為原點，正東方向為x軸正方向，正北方向為y軸正方向建立坐標系地圖Map₁；

以地圖右下角頂點為原點，正北方向為x軸正方向，正西方向為y軸正方向建立坐標系地圖Map₂；

以地圖右上角頂點為原點，正西方向為x軸正方向，正南方向為y軸正方向建立坐標系地圖Map₃；

以地圖左上角頂點為原點，正南方向為x軸正方向，正東方向為y軸正方向建立坐標系地圖Map₄。

3.根據權利要求1或2所述的方法，其特征在于，通過以下步驟通過N個1/4圓環將所述坐標系地圖切分為N個環區域：

將有序的p個興趣點p₁，p₂，...，p_P，均勻放入N個不相交的集合中B_i，每個集合B_i＝{p_(i-1)×λ+1，...，p_i×λ}，1≤i≤N-1；其中，所述的λ＝[p/N]；

計算B_i中(1≤i≤N)的點到原點O的最短距離r_i-1；

以O為圓心，r₁，r₂，...，r_N-1為半徑作N-1個1/4圓環，得到N個環區域R₁，R₂，...，R_N。