一种基于双色反最近邻查询的最优选址方法

摘要

本发明公开了一种基于双色反最近邻查询的最优选址方法。利用空间数据库中双色反最近邻查询技术，将空间四分法和泰森多边形应用到本发明中，保证查询结果具有最多的反最近邻，并使得查询结果到各自反最近邻的最小距离最大。本方法先为每个客户点生成最近位置圆域；接着用四分法找到矩形区域，并使得该区域落在尽可能多的最近位置圆域交集中；然后用两个有效的剪枝规则对上一步得到的与矩形区域相关的最近位置圆域集合进行修剪；最后根据修剪后的最近位置圆域集合及其泰森多边形找出最佳位置点。本发明极大地减少了查询的搜索空间，且查询效率明显好于现有方法，提供了最佳性能。

主权项

一种基于双色反最近邻查询的最优选址方法，其特征在于该方法的步骤如下： 步骤（1）：对于服务点数据集采用R树索引，维护一个矩形区域结果列表和一个查询结果列表； 步骤（2）：以客户点数据集中的每一个点为查询点，找出其在服务点数据集中的最近邻，并由此建立各个客户点的最近位置圆域； 步骤（3）：根据各客户点的最近位置圆域，采用四分法得到满足条件的矩形区域，并放入矩形区域结果列表； 步骤（4）：对于矩形区域结果列表中的每个矩形区域，求得其相交的最近位置圆域集合； 步骤（5）：利用剪枝规则过滤掉步骤（4）得到的最近位置圆域集合中不满足条件的最近位置圆域，并由此建立泰森多边形； 步骤（6）：利用步骤（5）中得到的最近位置圆域集合和泰森多边形计算最终结果。