给出纬度/经度的最快方法(纬度,城市,州)

Question

我需要一个免费的(开源)解决方案,给出lat/lng可以返回壁橱城市/州或邮编.mysql不是一个选项,如果可能的话,小型轻量级数据库将是最好的.

更新:没有网络服务,即使是最小的插件也会每天带来5000万次展示,因此添加服务请求会占用响应时间.我不希望在请求上添加超过200毫秒.

我在csv中有数据库,lat/lon/zip/city/state它只是如何存储,更重要的是如何最快地检索它.

Answer 1

这是一个非常有趣的问题,答案很复杂.

你提到一个有纬度/经度的城市数据库,但是城市不是单点,这可以在人口密集的地区产生很大的不同,城市A的大部分地区可能更靠近城市B的"中心"而不是城市的中心.城市A.在一个被较小郊区包围的大城市.大城市的外围部分可能更靠近郊区的中心,而不是大城市的中心.捕捉到最近的市中心意味着地图是城市中心点的Voronoi图.这样的地图看起来不像是城市地区的实际地图.

如果你想知道给定纬度/经度的城市和状态,你需要查询一个合适的地图并在多边形测试中指出它是什么.这听起来计算成本很高,但实际上并不坏你使用适当的空间索引,并在编码时要小心.我运行一个销售此访问和其他地理查询的API访问的网站,我们的底层引擎(用Java编写)可以返回美国的包含或最近的城市,平均查询时间为3e-4秒(超过3,000个查询)每秒).

即使我们正在销售它,我很乐意解释它是如何工作的,因为从我们这里购买它比自己制造它更便宜,即使有说明也是如此.所以他们在这里:

• 找到您想要的地图.对于美国地区,美国人口普查提供了非常准确的地图:http://www.census.gov/geo/www/tiger/tgrshp2010/tgrshp2010.html.我没有找到与美国人口普查地图一样好的全球地图,但它们可能存在.
• 查找或编写ESRI shapefile格式的解析器.我没有这方面的特定链接,因为它高度依赖于语言,但网上有许多免费和商业解析器.只需搜索"shapefile解析器"以及您的编程语言.
• 将地图加载到内存中.数字地图由一系列由纬度/经度对列表示的多边形组成,通常以逆时针方向排序.大多数地图允许切口(例如,南非的莱索托),其仅被列为多边形,其中纬度/经度对以顺时针方向列出.出于性能和内存消耗的原因,您将需要使用原始浮点数组(避免双精度,因为它浪费内存,并尽可能使用本机数组,以避免装箱).
• 接下来,您将需要代码来回答给定多边形中是否包含给定查询点.以下是对多边形点问题的精彩讨论:如何确定2D点是否在多边形内？
• 根据我的经验,在另一个答案(检查每个实体)中建议的暴力技术在国家或世界地图上不能很好地工作.相反,我强烈建议快速空间索引返回给定纬度/经度的候选多边形列表.这里有很多选择.很多人会建议基于树的索引,但我倾向于选择网格索引,因为它们更快,现代服务器往往有大量内存.我写了唯一一个与我合作的索引.我知道它们存在于GIS库中,但我发现大多数GIS代码过于复杂,缓慢且难以使用.因此,给定查询lat/lon,您将从空间索引中获取候选多边形列表,并使用多边形点函数来查找哪些候选包含查询点.
• 处理任何多边形都不包含查询点的情况也很重要.在这种情况下,您可能希望找到最接近指定最大距离的最近这样的多边形.为此,您需要确保空间索引可以返回附近多边形的列表,而不仅仅是包含多边形的候选列表.您还需要使用代码来计算查询点和纬度/经度线段之间的距离(这很难,因为纬度/经度不是欧几里德空间).我没有找到任何关于如何在网上做这个的好讨论,所以我设计了自己的方法.它的工作原理是在查询点周围创建一个线性化空间(在新空间中变为(0,0)),其中相对经度被重新缩放,使得经修改的经度的程度与纬度的程度相同(涉及将相对经度乘以纬度的余弦).在此线性化空间中,您可以使用标准方法找到线段上的最近点(请参阅点与线段之间的最短距离),然后将该点转换回lat/lon并使用Haversine公式计算之间的距离.两点(参见计算两个纬度 - 经度点之间的距离？(Haversine公式)).

就是这样.我打造和关闭这个系统大约半年.我的估计是,其中至少有三个月的严格编码,这是熟悉该主题的人(因此,请注意,如果您正在做出购买或构建决策).

Answer 2

蛮力:将所有数据预加载到阵列中.计算当前点与数组中每个点之间的距离(有一种方法可以使用线性代数而不是触发函数进行此计算,但我不记得是什么随意)来找到最近的点.

请在向下投票之前阅读这篇文章:有很多方法可以加快像这样的暴力搜索,但我发现他们通常不值得这么麻烦.我不仅在使用此方法之前从纬度/经度找到最近的拉链,我已经在Windows Mobile应用程序中使用它(处理能力不是很强大)并且仍然实现了亚秒级搜索时间.只要您避免使用trig函数,这不是一个昂贵的过程.

更新:您可以通过将您的zip数据分配到子区域(象限,例如西北,东南等)并使用每个数据点保存区域ID来加快搜索时间.然后,在搜索中,首先确定当前位置所在的区域,并仅与这些数据点进行比较.

为了避免边界错误(例如当您的当前位置靠近其区域的边缘但实际上最接近相邻区域中的zip时),您的区域应该在某种程度上重叠.这意味着您的一些zip记录将被复制,因此您的整体数据集将会更大一些.