[發明專利]一種基于空間索引及相鄰點信息的最近鄰點搜索方法

在審

• 申請號: 202010012526.7
• 申請日: 2020-01-07
• 公開（公告）號: CN113157688A
• 公開（公告）日: 2021-07-23
• 發明（設計）人: 余艷梅;杭鵬程;陶青川
• 申請（專利權）人: 四川大學
• 主分類號: G06F16/22
• 分類號: G06F16/22;G06F16/2458
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于空間索引及相鄰點信息的最近鄰點搜索方法，其特征在于：

為找到當前點G的k個最近鄰點，以整張散點圖(即圖中的點的坐標多為非整數)的中心為原點，用坐標軸網格將整張圖分成若干個小正方形區域，用位于每個網格左上角的格點(在直角坐標系中橫縱坐標為整數的點稱為“格點”)的坐標作為索引來檢索該網格區域內的各散點的所有信息(包括x、y坐標信息和其他信息)，也即各散點的所有信息被存儲在該網格左上角格點中；

(1)如果當前點G是每行的起始點，采用基于坐標空間的搜索：搜索范圍是以G為中心的正方形，正方形的半徑從1開始不斷增加，直到找到k個存有信息的格點后，將它們的坐標記錄在格點表中；

提取出k個格點中存儲的散點位置信息(x₁,y₁)、(x₂,y₂)……(x_k,y_k)，計算各(x,y)與點G的歐氏距離并求得其最大值d_max1，對d_max1通過公式(1)向上取整計算下一步的精確搜索正方形的半徑R₁：

接著開始精確搜索：在以G為中心、半徑為R₁的正方形區域內進行徹底搜索，為提高速度，只檢查該范圍內尚未被搜索過的格點是否存有散點信息；

計算這些散點的位置(x,y)與點G的歐氏距離，并與精確搜索之前找到的k個散點到點G的歐氏距離進行比較，選出k個最近鄰點；

(2)如果當前點G為每行的非起始點，則采用其同行左側網格點G_left的最近鄰信息進行搜索：計算已知的G_left的k個最近鄰點與當前點G的歐氏距離，求得其中的最大距離d_max2，通過公式(1)計算下一步的精確搜索正方形的半徑R₂；

為提高搜索速度，在當前點G的半徑為R₂的搜索正方形區域下，已經在G_left的正方形搜索區域中被搜索過的格點無需再次搜索，只檢查該范圍內尚未被搜索過的格點是否存有散點信息；計算這些散點的位置(x,y)與點G的歐氏距離，并與G_left的精確搜索區域內的所有鄰點到當前點G的歐氏距離進行比較，從而選出k個最近鄰點。

2.如權利要求1所述的基于空間索引及相鄰點信息的最近鄰點搜索方法，其特征在于用來搜索最近鄰點而創建的空間索引。

3.如權利要求1所述的基于空間索引及相鄰點信息的最近鄰點搜索方法，其特征在于基于非整數坐標的點的空間坐標進行搜索。

4.如權利要求1所述的基于空間索引及相鄰點信息的最近鄰點搜索方法，其特征在于基于先前點的空間信息進行搜索。

5.一種用于執行權利要求1至4所述基于空間索引及相鄰點信息的最近鄰點搜索方法。