34

这是一个比我迫切需要的更具挑战性的问题，所以不要整天花在这上面。

我在 2000 年左右建立了一个约会网站（早已不复存在），其中一个挑战是计算用户之间的距离，以便我们可以在 X 英里半径内展示你的“匹配”。仅说明问题，给定以下数据库模式（大致）：

用户表 UserId 用户名 ZipCode

邮政编码表 邮政编码 纬度 经度

在 USER.ZipCode = ZIPCODE.ZipCode 上加入 USER 和 ZIPCODE。

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

我们使用了2000 年的人口普查数据，其中包含邮政编码及其大致纬度和经度的表格。

我们还使用Haversine 公式来计算球体上任意两点之间的距离……非常简单的数学运算。

问题，至少对我们来说，作为 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 表中将有很多行。它不是完全不可行，但它确实很大。它还需要对整个数据集进行完整的前期工作，这也不是不可管理的，但不一定是可取的。

无论如何，我想知道你们中的一些大师可能会采取什么方法来处理这样的事情。此外，我认为这是程序员必须不时解决的一个常见问题，尤其是当您考虑算法相似的问题时。我对一个彻底的解决方案感兴趣，该解决方案至少包括所有部分的提示，以便真正快速有效地结束。谢谢！

4

8 回答 8

34

好的，对于初学者来说，您实际上并不需要在这里使用 Haversine 公式。对于不太准确的公式会产生较大误差的大距离，您的用户不在乎匹配是正负几英里，而对于更近的距离，误差非常小。地理距离维基百科文章中列出了更容易（计算）的公式。

由于邮政编码不像均匀分布的那样，任何将它们均匀划分的过程都会在它们紧密聚集的区域受到严重影响（华盛顿附近的东海岸就是一个很好的例子）。如果您想进行视觉比较，请查看http://benfry.com/zipdecode并将邮政编码前缀 89 与 07 进行比较。

处理索引这个空间的更好方法是使用像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

我将让您自己完成本教程的其余部分。

这里有一些其他参考资料可以帮助您入门。

于 2010-10-21T19:55:21.997 回答
14

我只需创建一个 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 英里半径内的邮政编码可将距离表中需要存储的行数从最大值 17 亿 (42K ^ 2) - 42K 减少到更易于管理的 400 万左右。

我从网上下载了一个邮政编码数据文件，其中包含 csv 格式的所有美国官方邮政编码的经度和纬度：

"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# 程序来读取文件并计算每个邮政编码之间的距离，但只输出 25 英里半径内的邮政编码：

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);
    }
}

生成的输出文件如下所示：

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
于 2010-10-21T16:42:45.713 回答
5

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

于 2010-10-21T00:20:33.770 回答
2

我知道这篇文章太旧了，但是为客户做一些研究我发现了谷歌地图 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/

于 2015-07-08T20:02:51.457 回答
1

我会使用纬度和经度。例如，如果您的纬度为 45，经度为 45，并被要求在 50 英里范围内查找匹配项，那么您可以通过将纬度上移 50/69 和纬度下移 50/69（1 度纬度 ~ 69 英里）。选择纬度在此范围内的邮政编码。经度略有不同，因为随着您靠近两极，它们会变小。

但是在 45 度，1 经度 ~ 49 英里处，因此您可以将纬度向左移动 50/49，纬度向右移动 50/49，并从具有该经度的纬度集中选择所有邮政编码。这将为您提供长度为一百英里的正方形内的所有邮政编码。如果您想非常精确，则可以使用您提到的 Haversine 公式清除盒子角落的拉链，给您一个球体。

于 2010-10-21T00:33:48.233 回答
1

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

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

它在数学上肯定更复杂，特别是必须选择区域的数量，以便在表的大小与动态计算所花费的时间之间取得良好的平衡，但它可以很好地减少预先计算的表的大小利润。

于 2010-10-21T02:00:12.193 回答
0

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

我不知道距离计算的复杂性，所以我还会检查动态计算是否比查找便宜（还要考虑你必须计算的频率）。

于 2010-10-21T00:27:49.243 回答
0

我的问题运行得很好，几乎每个人的答案都被使用了。我是根据旧的解决方案来考虑这个问题，而不仅仅是“重新开始”。Babtek 得到了用最简单的术语陈述的点头。

我将跳过代码，因为我将提供参考来推导所需的公式，而且这里有太多内容要清楚地发布。

1）考虑球体上的点A，由纬度和经度表示。 找出以 A 点为中心的 2X 英里宽的盒子的北、南、东和西边。

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

3) 使用半正弦公式确定 A 点与步骤 2 中返回的每个 B 点之间的球面距离。

4) 丢弃距离 A -> B > X 的所有点 B。

5) 选择 ZipCode 在剩余点集 B 中的用户。

对于> 100英里，这非常快。最长的结果是大约 0.014 秒来计算匹配，并且运行 select 语句很简单。

另外，作为旁注，有必要在几个函数中实现数学并在 SQL 中调用它们。一旦超过一定距离，匹配的 ZipCode 数量太大而无法传回 SQL 并用作 IN 语句，因此我必须使用临时表并将生成的 ZipCode 连接到 ZipCode 列上的用户。

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

或者，我有兴趣使用 SQL 的内置地理类型来查看这是否会使这更容易，但是旧的 int/float 类型可以很好地用于此示例。

所以......我使用的在线资源的最终列表，供您参考：

1）最大差异，纬度和经度。

2）Haversine公式。

3）对整个过程进行了冗长但完整的讨论，这是我从谷歌搜索你的答案中找到的。

于 2010-10-21T15:57:24.987 回答