Lat,Long坐标的比较

我有一个超过15000个纬度和经度坐标的列表.给定任何X,Y坐标,找到列表中最近坐标的最快方法是什么？

我曾为网站做过一次.即找到距离您的邮政编码50英里范围内的经销商.我用大圆计算找到了北50英里,东50英里,南50英里,西50英里的坐标.这给了我一个min和max lat以及一个min和max long.从那时起,我做了一个数据库查询:

select *
    from dealers
    where latitude  >= minlat
      and latitude  <= maxlat
      and longitude >= minlong
      and longitude <= maxlong

由于其中一些结果仍然会超过50英里,所以我在那个小坐标列表上再次使用了大圆公式.然后我打印出列表以及距目标的距离.

当然,如果你想搜索国际日期线或极点附近的点,那么这将不起作用.但它适用于北美洲的搜索!

您将需要使用称为Voronoi图的几何结构.这将平面划分为多个区域,每个区域一个,包含最接近每个给定点的所有点.

用于创建Voronoi图并排列数据结构查找的精确算法的代码太大,无法容纳在这个小编辑框中.:)

@Linor:这基本上就是你在创建Voronoi图后会做的事情.但是,您可以选择与Voronoi图线紧密匹配的分割线(而不是制作矩形网格)(这样您将获得越过分割线的更少区域).如果按照每个子图的最佳分界线递归地将Voronoi图分成两半,则可以对要查找的每个点进行树搜索.这需要预先做一些工作但以后节省时间.每次查找都是log N的顺序,其中N是点数.16次比较比15,000好很多!