c# - 可扩展性位置距离搜索全美国超过 100,000 个 LatLng 位置

Question

场景=

1) 分布在美国各地的送货办事处各自指定了自己的最大送货半径限制(以英里为单位)。

2) 目标地址geo 转换为LatLng 是交付目的地。

目标 = 返回交付办公室的数据集 (1) 谁的交付半径限制落在到目标地址的此距离内 (2)

尝试=

作为我的问题的起点，我使用 Storm 咨询公司的优秀工作示例来确定离客户最近的办公室:Haversine distance between two points

我的“Offices”表存储办公室地址及其 Lat 和 Lng 值以及它们的最大距离“deliveryLimit”。

计算 Haversine 的 SQL 让我大吃一惊，目前超出了我的理解范围!
Storm SQL 如下，但我需要选择最大距离交付限制小于办公室与客户之间距离的所有办公室行，而不是仅从直线距离计算中选择一行。

问题 1 = 如何将最大距离限制过滤器添加到 SQL 查询中，以便它返回具有包含目标位置的送货区域的办公室？

问题 2 = 如何将查询的办公室数量限制为实际可能位于美国目标区域的办公室数量？例如，如果目标位置是爱达荷州博伊西，办公室位于加利福尼亚州洛杉矶，则配送距离限制为 300 英里。甚至询问这些办公室也没有意义。但是，在华盛顿的办事处；与爱达荷州接壤的俄勒冈州和内华达州北部应该包含在搜索查询中，因为有些州的最大距离值可能达到爱达荷州博伊西的这个示例。

Storm 使用的 Haversine SQL:

SELECT TOP 1 *, ( 3960 * acos( cos( radians( @custLat ) ) *
cos( radians( Lat ) ) * cos( radians(  Lng  ) - radians( @custLng ) ) +
sin( radians( @custLat ) ) * sin( radians(  Lat  ) ) ) ) AS Distance
FROM Offices
ORDER BY Distance ASC

上面的 SQL 示例仅选择离目标纬度/经度最近的办公室 (@custLng)

Storm 从两个不同的方向接近距离计算。上面的 SQL 是第一个。第二种方法是将办公室坐标保存在内存列表中，并创建一个方法，该方法具有循环遍历列表的功能，计算距离并最终选择最近的位置，如下所示:

/// <summary>
/// Returns the distance in miles or kilometers of any two
/// latitude / longitude points.
/// </summary>
/// <param name="pos1">Location 1</param>
/// <param name="pos2">Location 2</param>
/// <param name="unit">Miles or Kilometers</param>
/// <returns>Distance in the requested unit</returns>
public double HaversineDistance(LatLng pos1, LatLng pos2, DistanceUnit unit)
{
    double R = (unit == DistanceUnit.Miles) ? 3960 : 6371;
    var lat = (pos2.Latitude - pos1.Latitude).ToRadians();
    var lng = (pos2.Longitude - pos1.Longitude).ToRadians();
    var h1 = Math.Sin(lat / 2) * Math.Sin(lat / 2) +
              Math.Cos(pos1.Latitude.ToRadians()) * 
              Math.Cos(pos2.Latitude.ToRadians()) *
              Math.Sin(lng / 2) * Math.Sin(lng / 2);
    var h2 = 2 * Math.Asin(Math.Min(1, Math.Sqrt(h1)));
    return R * h2;
}

public enum DistanceUnit { Miles, Kilometers };

和

var Offices = GetMyOfficeList();
for(int i = 0; i< Offices.Count; i++)
{
    Offices[i].Distance = HaversineDistance(
                        coord,
                        new LatLng(Offices[i].Lat, Offices[i].Lng),
                        DistanceUnit.Miles);
}

var closestOffice = Offices.OrderBy(x => x.Distance).Take(1).Single();

可扩展性很重要，因为我的场景很容易以超过 100,000 个办公地点结束，因此内存中办公列表选项不太可能!

Answer 1

如果您使用的是 Sql2008 或更新版本，它具有内置的特定类型，可以让您更轻松地完成任务。您需要使用的主要类型是 geography

我将对您的表结构进行一些猜测，但最主要的是您有一个 Location和一个 DeleveryArea

create table Offices
(
  OfficeName varchar(40),
  Location geography,
  DeliveryDistance float, --stored in miles
  --If you are on SQL2008 or 2008R2 replace BufferWithCurves with one of the older Buffer functions
  DeliveryArea as Location.BufferWithCurves(DeliveryDistance * 1609.34) PERSISTED, --1609.34 converts miles to meters 
)

我用了BufferWithCurves在我上面的示例中，但这仅适用于 Sql2012 和更新版本，如果您使用的是 2008 或 2008R2，则需要使用 BufferWithTolerance或 STBuffer或者只是在插入语句中手动定义您自己的区域。

现在填充数据，因为我们制作了DeliveryArea计算的持久列实际上很容易做到。您需要做的就是输入办公室的位置及其交付区域的半径，它会为您计算该区域的圆。我将使用您在问题中提供的示例:

insert into Offices (OfficeName, Location, DeliveryDistance) 
values ('Boise, ID', 
        geography::Point(43.6187102,-116.2146068, 4326), --4326 represents a "lat and long" coordinate system
        300
       )

insert into Offices (OfficeName, Location,DeliveryDistance) 
values ('LA, CA', 
        geography::Point(34.0204989,-118.4117325, 4326),
        300
       )

insert into Offices (OfficeName, Location,DeliveryDistance) 
values ('Walla Walla, WI', 
        geography::Point(46.0627549,-118.3337259, 4326),
        300
       )

insert into Offices (OfficeName, Location,DeliveryDistance) 
values ('Baker City, OR', 
        geography::Point(44.7746169,-117.8317284, 4326),
        300
       )

insert into Offices (OfficeName, Location,DeliveryDistance) 
values ('Elko, NV', 
        geography::Point(40.846931,-115.7669825, 4326),
        300
       )

现在您的查询，如果您想查找提供服务的送货区域Jordan Vally, Oregon (42.9740245,-117.0533247) 你的查询就是

declare @cust geography = geography::Point(42.9740245,-117.0533247, 4326)

SELECT OfficeName, 
       Location.STDistance(@cust) / 1609.34 AS Distance, --convert back to miles
       Location.Lat as Lat,
       Location.Long as Lng
FROM Offices
where  DeliveryArea.STContains(@cust) = 1
ORDER BY Distance asc

这将为您提供您选择的位置在交付区域内的所有办公室。这个系统真正的好处是如果不是计算DeleveryArea根据位置和传输范围，你实际上可以给它一组点来勾勒出一个非圆形的地理区域，比如一个城市。

精心策划Spatial Index此解决方案甚至适用于您的 100,000 个位置记录集。如果您想详细了解使用 geography 的一些好处见this SO question and answer .

Here is a SQL Fiddle我在上面提出的所有查询都显示在一个工作示例中。