计算邮政编码...与用户之间的距离。

Question

这比我迫切需要的东西更具挑战性，所以不要整天花时间在这个家伙身上。

我在2000年左右建立了一个约会网站（早已不复存在），其中一个挑战是计算用户之间的距离，以便我们可以在X英里半径内呈现您的“匹配”。只是陈述问题，给出下面的数据库模式（大约）：

用户表 用户ID 用户名 邮编

ZIPCODE表 邮编 纬度 经度

使用用户和ZIPCODE被连接上USER.ZipCode = ZIPCODE.ZipCode。

您将采取什么方法来回答以下问题：其他用户居住在给定用户邮政编码的X英里范围内的邮政编码中。

我们使用了2000 census data，它有邮政编码表及其近似的经度和纬度。

我们还使用Haversine Formula来计算球体上任意两点之间的距离......真的很简单的数学。

这个问题，至少对我们来说，是我们当时19岁的大学生，真正成为如何高效地计算和/或存储所有成员到所有其他成员的距离。一种方法（我们使用的方法）是导入所有数据并计算从每个邮政编码到每个其他邮政编码的距离。然后你会存储和索引结果。例如：

SELECT User.UserId 
FROM ZipCode AS MyZipCode 
     INNER JOIN ZipDistance ON MyZipCode.ZipCode = ZipDistance.MyZipCode 
     INNER JOIN ZipCode AS TheirZipCode ON ZipDistance.OtherZipCode = TheirZipCode.ZipCode 
     INNER JOIN User AS User ON TheirZipCode.ZipCode = User.ZipCode 
WHERE (MyZipCode.ZipCode = 75044) 
     AND (ZipDistance.Distance < 50) 

这个问题当然是ZipDistance表将会有很多行。它不是完全不可行的，但它确实很大。此外，它需要对整个数据集进行完整的前期工作，这也是不可管理的，但不一定需要。

无论如何，我想知道你们的一些大师可能采取了什么样的方法。另外，我认为这是程序员不时需要解决的常见问题，特别是如果您考虑的算法类似的问题。我对一个彻底的解决方案感兴趣，其中至少包括提示，以便快速有效地完成所有这些操作。谢谢！

Answer 1

好吧，对于初学者来说，你并不需要在这里使用Haversine公式。对于距离较远的地方，如果准确度较低的公式会产生较大的误差，则用户不会在乎匹配是正数还是负数英里，而对于距离较近的距离，误差很小。有更容易（计算）在Geographical Distance维基百科文章上列出的公式。

由于邮递区号是不一样均匀分布的，均匀地划分他们的任何过程将在那里它们被紧密聚集（接近DC东海岸是一个很好的例子），以在地区遭受的境地。如果你想有一个直观对比，看看http://benfry.com/zipdecode，并与07

比较邮政编码前缀89一个更好的方式来处理索引这个空间是使用数据结构像一个Quadtree或R-tree。这种结构允许您对不均匀间隔的数据进行空间和距离搜索。

这里有一个四叉树的样子：

要通过它可以搜索，您通过使用更小的细胞是在它内部的指数每个较大的蜂窝状下钻。维基百科更彻底地解释它。

当然，因为这是做的一个相当普遍的事情，别人已经做了你最困难的部分。既然你没有指定您所使用的数据库中，PostgreSQL扩展PostGIS将作为一个例子。 PostGIS包含了执行R-tree空间索引的功能，可以让您执行高效的空间查询。

一旦导入您的数据和内置的空间索引，查询距离查询，如：

SELECT zip 
FROM zipcode 
WHERE 
geom && expand(transform(PointFromText('POINT(-116.768347 33.911404)', 4269),32661), 16093) 
AND 
distance(
    transform(PointFromText('POINT(-116.768347 33.911404)', 4269),32661), 
    geom) < 16093 

我就让你通过教程自己的休息工作。

• http://unserializableone.blogspot.com/2007/02/using-postgis-to-find-points-of.html

下面是其他一些参考，让你开始。

• http://www.bostongis.com/PrinterFriendly.aspx?content_name=postgis_tut02
• http://www.manning.com/obe/PostGIS_MEAPCH01.pdf
• http://postgis.refractions.net/docs/ch04.html

Answer 2

您可以通过假定一个盒子而不是圆形半径来简化计算。然后，在搜索时，只需计算给定点+“半径”的纬度/经度的下限/上限，并且只要在经度/纬度列上有一个索引，就可以很容易地将所有落在该框内的记录。

Answer 3

将不会使用每一对可能的邮政编码。我会将zipdistance构建为“缓存”表。对于每个请求计算该对的距离并将其保存在缓存中。当距离对的请求到来时，首先查看缓存，然后计算它是否不可用。

我不知道距离计算的复杂性，所以我也会检查运行中的计算是否比查找更便宜（同时考虑到您必须计算多久）。

Answer 4

我会使用经度和纬度。例如，如果您的纬度为45，经度为45，并且要求在50英里内找到匹配，则可以通过在纬度上移动50/69位和在纬度上移动50/69位（1度纬度〜69英里）。选择纬度在此范围内的邮政编码。经度有点不同，因为当你靠近两极时它们会变小。

但是，在45度，1经度~49英里，所以您可以在纬度和50/49ths纬度范围内左移50/49，并选择纬度设置的所有邮政编码。这为您提供长度为一百英里的广场内的所有邮政编码。如果你想要非常精确，那么你可以使用你提到的Haversine公式来除掉盒子角落的拉链，给你一个球体。

Answer 5

你可以将你的空间分成几乎大小相同的区域 - 例如，将地球近似为巴克球或二十面体。这些区域甚至可能重叠一点，如果更容易的话（例如使它们成为圆形）。记录每个邮政编码所在的区域。然后，您可以预先计算每个区域对之间可能的最大距离，在计算所有邮政编码对时它们具有相同的问题，但是对于较小的n。

现在，对于任何给定的邮政编码，您可以获得肯定在给定范围内的区域列表以及跨越边界的区域列表。对于前者，只需抓住所有的邮政编码。对于后者，深入到每个边界地区并根据个别邮政编码进行计算。

它在数学上肯定更复杂，特别是必须选择区域的数量，以便在表格大小和动态计算时间之间保持良好的平衡，但它会减小预先计算的大小表格好利润。

Answer 6

我的问题运行良好，几乎所有人的答案都被使用了。我以前的解决方案考虑这个问题，而不是“重新开始”。 Babtek得到了最简单的说法。

我会跳过这段代码，因为我会提供推导所需公式的参考，而且这里有太多可以干净地发布。

1）考虑球体上的点A，以经度和纬度表示。 Figure out North, South, East, and West edges of a box 2X miles across with Point A at the center。

2）从ZipCode表中选择框中的所有点。这包括一个简单的WHERE子句，其中包含两个由Lat和Long限制的语句。

3）使用半正矢公式来确定点A与每个点B之间的球面距离在步骤2

4返回）丢弃所有点B，其中距离A - > B> X.

5）选择ZipCode在剩余点数B中的用户。

这对于> 100英里相当快。最长的结果是〜0.014秒来计算匹配，并且运行select语句很简单。另外，作为一个附注，有必要在几个函数中实现数学，并在SQL中调用它们。一旦我超过了一定的距离，匹配的ZipCodes数量太大，无法传回SQL并用作IN语句，所以我不得不使用临时表并将ZipCode结果连接到ZipCode列上的User。

我怀疑使用ZipDistance表不会提供长期的性能增益。行数变得非常大。如果您计算从每个邮政编码到每个其他邮政编码的距离（最终），则从40,000个邮政编码得到的行数将为〜1.6B。哇！

或者，我感兴趣的使用SQL内置的地理类型，看看是否会使这更容易，但良好的老INT /浮点类型此样品送达罚款。

所以...我用，以便于您参考在线资源的最终名单：

1）Maximum Difference, Latitude and Longitude。

2）The Haversine Formula。

3）Lengthy but complete discussion of the whole process，我从你的答案中找到谷歌搜索的东西。

Answer 7

我只是简单地创建一个zip_code_distances表和预计算在美国的所有42K邮编它们是彼此的20-25英里半径内之间的距离。

create table zip_code_distances 
(
from_zip_code mediumint not null, 
to_zip_code mediumint not null, 
distance decimal(6,2) default 0.0, 
primary key (from_zip_code, to_zip_code), 
key (to_zip_code) 
) 
engine=innodb; 

只包括彼此的20-25英里半径内邮编减少你需要在距离表中存储的行数从它的最大1.7十亿（42K^2） - 42K到一个更可管理的400万左右。

我从网上下载含有所有的美国官方邮编的经度和纬度以CSV格式Web上的邮编数据文件：

"00601","Adjuntas","Adjuntas","Puerto Rico","PR","787","Atlantic", 18.166, -66.7236 
"00602","Aguada","Aguada","Puerto Rico","PR","787","Atlantic", 18.383, -67.1866 
... 
"91210","Glendale","Los Angeles","California","CA","818","Pacific", 34.1419, -118.261 
"91214","La Crescenta","Los Angeles","California","CA","818","Pacific", 34.2325, -118.246 
"91221","Glendale","Los Angeles","California","CA","818","Pacific", 34.1653, -118.289 
... 

我写了一个快速和肮脏的C＃程序读取该文件，并计算

sw = new StreamWriter(path); 

foreach (ZipCode fromZip in zips){ 

    foreach (ZipCode toZip in zips) 
    { 
     if (toZip.ZipArea == fromZip.ZipArea) continue; 

     double dist = ZipCode.GetDistance(fromZip, toZip); 

     if (dist > 25) continue; 

     string s = string.Format("{0}|{1}|{2}", fromZip.ZipArea, toZip.ZipArea, dist); 
     sw.WriteLine(s); 
    } 
} 

得到的输出文件如下所示：下降25英里半径范围内，每一个邮政编码，但只有输出邮编之间的距离

from_zip_code|to_zip_code|distance 
... 
00601|00606|16.7042215574185 
00601|00611|9.70353520976393 
00601|00612|21.0815707704904 
00601|00613|21.1780461311929 
00601|00614|20.101431539283 
... 
91210|90001|11.6815708119899 
91210|90002|13.3915723402714 
91210|90003|12.371251171873 
91210|90004|5.26634939906721 
91210|90005|6.56649623829871 
... 

然后，我会只是这个距离数据加载到使用LOAD DATA INFILE我zip_code_distances表，然后用它来限制我的应用程序的搜索空间。

例如，如果您有其邮政编码为91210用户，他们希望找到的人是他们的10英里半径内谁，那么你现在可以简单做到以下几点：

select 
p.* 
from 
people p 
inner join 
(
select 
    to_zip_code 
from 
    zip_code_distances 
where 
    from_zip_code = 91210 and distance <= 10 
) search 
on p.zip_code = search.to_zip_code 
where 
p.gender = 'F'.... 

希望这有助于

编辑：扩展半径到100英里，使邮政编码距离增加到3250万行。

快速性能检查邮政编码91210运行时间0.009秒。

select count(*) from zip_code_distances 
count(*) 
======== 
32589820 

select 
to_zip_code 
from 
zip_code_distances 
where 
from_zip_code = 91210 and distance <= 10; 

0:00:00.009: Query OK 

Answer 8

我知道这个帖子太旧了，但做一些研究，为客户，我发现谷歌地图API的一些有用的功能，并且很简单实现，你只需要传递到url出发地和目的地邮政编码，并计算甚至与交通的距离，你可以用任何语言中使用它：

origins = 90210 
destinations = 93030 
mode = driving 

http://maps.googleapis.com/maps/api/distancematrix/json?origins=90210&destinations=93030&mode=driving&language=en-EN&sensor=false%22

的链接，你可以看到它返回一个JSON以下。请记住，您需要一个API密钥才能在您自己的主机上使用此密钥。

来源： http://stanhub.com/find-distance-between-two-postcodes-zipcodes-driving-time-in-current-traffic-using-google-maps-api/