高分求一算法实现

Question

从数据库中查询出多个点（N）的X 和 Y放在内存中。要求传入一个点（P）的X和Y，找出P与N中哪个点距离最近。
注，N大约为几千至几百万

Answer 1

最暴力的方法：
    计算N中每一个点与P的距离，保留最大的；最能蒙的方法：
    把P.X放到N的X中排序，找出一定数量（比如100个，1000个）的在X轴上和P最近的点的集合N'；
    把P.Y放到N的Y中排序，找出一定数量的在Y轴上和P最近的点N''；
    取得N'和N''的交集，然后可以参见暴力算法；最……的方法：
    以P为圆心画圆，半径从0开始步进，画出一个圆后，判断有没有点在圆上，第一个出现在圆上的就是最近的
数据量太大的话就分批来，100万分成两份10份10万来做

Answer 2

根据点的分布大致密度给出一个值Z，在数据库中查点的时候select *  from * where  x-p.x < z and y - p.y < z
这样就能取得最近的一小群点，然后精确计算

Answer 3

如果你在内存中是以DataTable的形式保存的，照样可以用类似SQl文的形式来过滤如果都包装成了类或结构体，那就复杂了

Answer 4

大致看了一下，个人理解的和 8 、 9 楼的兄弟的看法差不多。1、自己确认好一个范围，比如：地图搜索时，可以指定搜索的范围 “周围100m ？ 200m ?” 即：8楼兄弟的z = 100
2、利用 8楼的兄弟的sql，可以得到过滤掉大部分的数据集 (这个的影响因素是z的取值)
3、从2中得到的数据再放到内存中进行二次筛选这个是思路，实际中有相应的应用。如果再结合贪婪算法，或其他的算法，效果应该更好。

Answer 5

我写个伪码把:Point pi;//输入的点值
Point po = pi;//输出的最近点double minDist = Double.MaxValue;//最小距离
double dx,dy,dist;
foreach(Point p in pointDataBase)//对数据库中所有的点遍历
{
    dx = fabs(p.x-pi.x);
    if(dx>minDist)
        contine;
    dy = fabs(p.y-pi.y);
    if(dy>minDist)
        contine;
    dist = math.sqrt(dx*dx+dy*dy);
    if (dist<minDist )
    {
       minDist = dist;
       po  = p;
    }
}如果这个查询算法需要频繁调用,可以进一步作如下优化:
将整个大的区域分成若干个小的区域,也就是切成一个个矩形,并把所有点存到相应的矩形里面.
当查询点来的时候,先判断这个点的左上,左下右上右下四个区域是哪个,并对这四个区域中的点调用上面的算法,这样大大减少了遍历的点数.