我需要一个免费（开源）解决方案，给定 lat/lng 可以返回壁橱城市/州或 zip。mysql 不是一个选项，如果可能的话，一个小型轻量级数据库将是最好的。
更新：没有网络服务，每天有 5000 万次展示，即使是最小的插件也会受到伤害，因此添加服务请求会缩短响应时间。我不希望在请求上增加超过 200 毫秒。
我在 csv 中有数据库，lat/lon/zip/city/state，它只是如何存储，更重要的是如何最快地检索它。
问问题
17961 次
10 回答
10
蛮力：将所有数据预加载到数组中。计算当前点与数组中每个点之间的距离（有一种方法可以使用线性代数而不是三角函数进行此计算，但我不记得它是什么）以找到最近的点。
请在投票前阅读此内容：有一些方法可以加快这样的蛮力搜索，但我发现它们通常不值得麻烦。我之前不仅使用过这种方法从纬度/经度中找到最近的 zip，而且我已经在 Windows Mobile 应用程序中使用过它（其中处理能力并不完全是压倒性的）并且仍然实现了亚秒级的搜索时间。只要您避免使用三角函数，这不是一个昂贵的过程。
更新：您可以通过将 zip 数据分配到子区域（例如象限，例如西北、东南等）并保存每个数据点的区域 ID 来加快搜索时间。然后，在搜索中，您首先确定您当前位置所在的区域，然后仅与这些数据点进行比较。
为避免边界错误（例如，当您当前的位置靠近其区域的边缘但实际上最接近相邻区域的 zip 时），您的区域应在一定程度上重叠。这意味着您的一些 zip 记录将被复制，因此您的整体数据集会更大一些。
于 2009-08-11T14:35:00.853 回答
10
这是一个非常有趣的问题，答案很复杂。
您提到了具有纬度/经度的城市数据库，但城市不是单点，这在人口稠密的地区可能会产生很大的不同，因为城市 A 的大部分地区可能更接近城市 B 的“中心”而不是城市的中心城市 A. 以一个被较小郊区包围的大城市为例。大城市的外围地区可能更接近郊区的中心，而不是大城市本身的中心。捕捉到最近的市中心意味着地图是市中心点的 Voronoi 图。这样的地图看起来一点也不像城市地区的实际地图。
如果您想知道给定纬度/经度的城市和州，您需要查询适当的地图并进行多边形测试以找出它所在的位置。这听起来计算量很大，但实际上还不错您使用适当的空间索引，并且在编码时要小心。我运行一个销售 API 访问这个和其他地理查询的网站，我们的底层引擎（用 Java 编写）可以返回美国的包含或最近的城市，平均查询时间为 3e-4 秒（超过 3,000 个查询每秒）。
尽管我们正在出售它，但我很乐意解释它是如何工作的，因为从我们这里购买它比自己建造它便宜得多，即使有说明也是如此。所以他们在这里：
- 找到你想要的地图。对于美国位置，美国人口普查提供了极其准确的地图，网址为：http ://www.census.gov/geo/www/tiger/tgrshp2010/tgrshp2010.html 。我没有找到与美国人口普查地图一样好的全球地图，但它们可能存在。
- 查找或编写 ESRI shapefile 格式的解析器。我没有具体的链接，因为它高度依赖于语言，但是网络上有许多免费的和商业的解析器。只需搜索“shapefile parser”以及您的编程语言即可。
- 将地图加载到内存中。数字地图由一组由纬度/经度对表示的多边形组成，通常按逆时针方向排列。大多数地图都允许裁剪（例如，南非的莱索托），它们只是以多边形的形式列出，其中纬度/经度对按顺时针方向列出。出于性能和内存消耗的原因，您将需要使用原始浮点数组（避免双精度，因为它会浪费内存，并尽可能使用本机数组，以避免装箱）。
- 接下来，您将需要代码来回答给定的查询点是否包含在给定的多边形中。这是对多边形内点问题的精彩讨论：如何确定 2D 点是否在多边形内？
- 以我的经验，另一个答案中建议的蛮力技术（检查每个实体）在国家或世界地图上效果不佳。相反，我强烈建议使用快速空间索引，该索引返回给定纬度/经度的候选多边形列表。这里有很多选择。很多人会建议基于树的索引，但我更喜欢网格索引，因为它们速度更快，而且现代服务器往往有很多内存。我编写了我使用过的唯一一个这样的索引。我知道它们存在于 GIS 库中，但我发现大多数 GIS 代码过于复杂、缓慢且难以使用。因此，给定查询纬度/经度，您可以从空间索引中获取候选多边形列表，并使用多边形中的点函数来查找哪些候选多边形包含查询点。
- 处理查询点不包含在任何多边形中的情况也很重要。在这种情况下，您可能希望找到最接近指定最大距离的此类多边形。为此，您需要确保您的空间索引可以返回附近多边形的列表，而不仅仅是包含多边形的候选列表。您还需要代码来计算查询点和纬度/经度线段之间的距离（这很难，因为纬度/经度不是欧几里得空间）。我没有找到任何关于如何在网上进行此操作的好的讨论，所以我设计了自己的方法。它通过在查询点（在新空间中变为 (0, 0)）周围创建一个线性化空间来工作，其中相对重新调整经度，使得修改后的经度与纬度的距离相同（包括将相对经度乘以纬度的余弦）。在这个线性化空间中，您可以使用标准方法找到线段上最近的点（请参阅点和线段之间的最短距离），然后将该点转换回纬度/经度并使用 Haversine 公式计算两点之间的距离两个点（请参阅计算两个经纬度点之间的距离？（Haversine 公式））。
And that's it. I built such a system on and off for about half a year. My estimate is that there are at least three man months of serious coding in it, and that's someone familiar with the subject matter (so beware if you are making a buy-or-build decision).
于 2012-05-07T22:50:47.233 回答
3
使用kd-tree加速最近邻搜索。无论您的平台是什么，都应该有很多免费的实现。
于 2009-08-11T15:26:05.167 回答
1
它不是开源的，但也许你可以使用 Google Maps API：
于 2009-08-11T14:04:46.767 回答
1
你应该检查geonames。他们有一个返回 XML 和/或 JSON 的 API。此外，您可以 dl 他们的数据库。
于 2009-08-11T14:38:37.010 回答
0
另一个线程通过 MaxMind 推荐 mod_geoip。它在 Apache 级别上运行，甚至在它到达 PHP/.NET/Java 之前。 Maxmind 地理定位 API：Apache 与 PHP
于 2009-08-11T14:23:29.080 回答
0
如果你有拉链的长和纬度以及当前位置，你可以计算一个半径并找到那个圆内的点。如果您对每个邮政编码范围进行假设边界，则可以加快搜索速度。
如果您可以使用 SQL 2008（标准或快速），则可以使用空间数据类型。
于 2009-08-11T14:28:26.637 回答
0
雅虎！Placemaker是一个免费的网络服务，可以做到这一点。它可以查找地名（“纽约市”、“白金汉宫”），但也可以使用Geo 微格式查找纬度和经度。
要使用该服务，您需要提交一个 POST 请求，它会返回 XML：
一个小的命令行示例（我隐藏了我的 Yahoo! 应用 ID；您需要自己注册）：
$ curl -X POST -ddocumentContent='<div class="geo">GEO: <span class="latitude">37.386013</span>, <span class="longitude">-122.082932</span></div>' -ddocumentType='text/html' -dappid='your_yahoo_app_id' http://wherein.yahooapis.com/v1/document
这会返回一个非常详细的 XML 文档，其中一部分是：
<type>Town</type>
<name><![CDATA[Los Altos, CA, US]]></name>
它还包含以下数据：
<type>Zip</type>
<name><![CDATA[94024, Los Altos, CA, US]]></name>
我没有用过 Placemaker，但是我用过他们的Geocoding API，而且速度非常快。将此与本地数据结合起来memcached，用户不知道数据不是本地数据。
于 2009-08-11T14:35:27.967 回答
0
查看 geonames.org 数据库以获取源数据。
对于轻量级的数据库，sqlite 是一个不错的选择。
geonames 也提供网络服务，但如果您想在不通过网络调用的情况下自己完成（听起来好像是这样），那么您将需要一个本地数据库。然后，您只需要进行正确的三角计算来计算出一对 lat / lng 点之间的大圆距离（google that），然后按距离对结果进行排序。如果您想在进行计算之前限制搜索半径，也可以使用边界框或半径。
如果您的本地数据库可以是基于 SQL 的（其中 sqllite3 是），那么所有这些加起来就是一个 SQL 查询，该查询添加了一堆三角计算来计算一个“距离”列，也许还有一个类似的“where”子句来限制搜索范围内半径或边界框。计算出查询中的距离列后，就可以轻松按距离排序并添加您喜欢的任何其他条件。如果您了解 ruby/rails 并希望看到一个很好的例子来说明如何做到这一点，请查看 GeoKit rails 插件源。
于 2009-08-11T14:41:41.717 回答
0
您预计最近的城市距离您的源位置有多远？50英里？200英里？500英里？如果两个城市几乎等距，那么您的算法是否会选择最接近的城市？您可以使用此信息来帮助加快搜索速度。
如果您可以合理地假设距离差异很小（约 250 英里左右可能足够接近以被认为是“小”），并且您的距离计算可能有点“模糊”，那么您可以优化“蛮力”通过将您的搜索空间限制在距离源头 +/- 5 拉特（每拉特约 70 英里，因此这使您向北和南提供 350 英里左右）和 +/- 5 长（假设您没有搜索）来检查对于两极的城市，这是从赤道约 350 英里到加拿大北部约 100 英里的任何地方）。将这些范围调整为您认为适合您的问题空间的范围。
虽然三角函数将帮助您准确指示距离，但对于较小的距离，例如这些毕达哥拉斯通常足够接近“最佳猜测”答案，x = 69.1 * (sourcelat - citylat) 和 y = 53.0 * (sourcelong -长城）。
于 2009-08-11T15:31:08.697 回答