[發明專利]一種基于雙色反最近鄰查詢的最優選址方法

有效

• 申請號: 201410007605.3
• 申請日: 2014-01-07
• 公開（公告）號: CN103778196B
• 公開（公告）日: 2017-01-18
• 發明（設計）人: 高云君;崔會永;李萌;柳晴;苗曉曄;陳璐;趙靖文
• 申請（專利權）人: 浙江大學
• 主分類號: G06F17/30
• 分類號: G06F17/30
• 代理公司: 杭州天正專利事務所有限公司33201
• 代理人: 王兵,黃美娟

1.一種基于雙色反最近鄰查詢的最優選址方法，其特征在于該方法的步驟如下：?

步驟（1）：對于服務點數據集采用R樹索引，維護一個矩形區域結果列表和一個查詢結果列表；?

步驟（2）：以客戶點數據集中的每一個點為查詢點，找出其在服務點數據集中的最近鄰，并由此建立各個客戶點的最近位置圓域；?

步驟（3）：根據各客戶點的最近位置圓域，采用四分法得到滿足條件的矩形區域，并放入矩形區域結果列表；?

步驟（4）：對于矩形區域結果列表中的每個矩形區域，求得其相交的最近位置圓域集合；?

步驟（5）：利用剪枝規則過濾掉步驟（4）得到的最近位置圓域集合中不滿足條件的最近位置圓域，并由此建立泰森多邊形；?

步驟（6）：利用步驟（5）中得到的最近位置圓域集合和泰森多邊形計算最終結果。?

2.根據權利要求1所述的一種基于雙色反最近鄰查詢的最優選址方法，其特征在于：所述的步驟（1）中矩形區域結果列表存放滿足條件的矩形；查詢結果列表存放最終的查詢結果。?

3.根據權利要求1所述的一種基于雙色反最近鄰查詢的最優選址方法，其特征在于：所述的步驟（2）中最近位置圓域是以客戶點為圓心、其到服務點數據集中最近鄰的距離為半徑的圓；所有的最近位置圓域通過R樹建立索引；最近位置圓域在R樹中用其最小包含?矩形表示，矩形的邊分別與各坐標軸平行。?

4.根據權利要求1所述的一種基于雙色反最近鄰查詢的最優選址方法，其特征在于：所述的步驟（3）中找到的矩形區域具有兩個屬性：上界值和下界值；上界值表示與矩形區域有共同區域的最近位置圓域數量；下界值表示包含整個矩形區域的最近位置圓域數量；在查找過程中，使用一個優先隊列存放待處理的矩形區域；該優先隊列是以矩形區域的上界值為排序度量，上界值最大的優先訪問；用四分法查找矩形區域的步驟包括：?

1)將索引最近位置圓域集合的R樹根節點放入優先隊列；?

2)取出優先隊列中度量最大的矩形區域，若該矩形區域滿足上界值與下界值相等，則將該矩形區域添加到結果列表中；否則對矩形區域進行四分劃分，并將劃分出來的子區域添加到優先隊列。劃分的方式需分兩種情況考慮：?

a)連續4次遍歷到的矩形區域的相交最近位置圓域集合相同，并具有相同的下界值；這種情況下需分兩種情況進行處理：i）與矩形區域相交但不包含的最近位置圓域相交于一點，那么在該交點對矩形區域進行劃分，分成4個矩形區域；ii）與矩形區域相交但不包含的最近位置圓域不相交于一點，那么在該矩形區域的中心進行劃分，分成4個面積相同的矩形區域；?

b）未出現a）中所述的連續分割的情況，則在該矩形區域的中心進行劃分，分成4個面積相同的矩形區域。?

5.根據權利要求1所述的一種基于雙色反最近鄰查詢的最優選?址方法，其特征在于：所述的步驟（4）的計算與矩形區域相交的最近位置圓域是通過以矩形區域為查詢條件，在NLC集合的R樹中查詢得到的。?

6.根據權利要求1所述的一種基于雙色反最近鄰查詢的最優選址方法，其特征在于：所述的步驟（5）的剪枝規則有兩種：?

1）某個最近位置圓域的半徑大于集合中最小最近位置圓域半徑的3倍，則該最近位置圓域可被過濾；?

2）對于集合中的一個最近位置圓域，若其與集合中任一最近位置圓域圓心之間的距離的一半小于該最近位置圓域的半徑，則該最近位置圓域可被過濾；?

泰森多邊形通過掃描線算法建立。?

7.根據權利要求1所述的一種基于雙色反最近鄰查詢的最優選址方法，其特征在于：所述的步驟（6）中利用步驟（5）中得到的最近位置圓域集合和泰森多邊形計算最終結果的步驟包括：?

1）計算泰森多邊形的頂點，計算各頂點與客戶點數據集的最小距離；?

2）計算最近位置圓域集合與泰森多邊形的交點，計算各交點與客戶點數據集的最小距離；?

3）在1）、2）步驟產生的兩類點中，根據其與客戶點數據集的最小距離，選取該值最大的點作為查詢結果。?