c# - 距离计算功能的优化

Question

在我的代码中，我必须在成对的纬度/经度值之间进行大量距离计算。

代码如下所示：

double result = Math.Acos(Math.Sin(lat2rad) * Math.Sin(lat1rad) 
+ Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad));

（lat2rad 例如是将纬度转换为弧度）。

我已将此功能确定为我的应用程序的性能瓶颈。有什么办法可以改善这一点吗？

（我不能使用查找表，因为坐标是变化的）。我还查看了这个问题，其中建议使用像网格这样的查找方案，这可能是一种可能性。

谢谢你的时间！;-)

score 5 · Accepted Answer

如果您的目标是对距离进行排名（比较），那么近似值（sin和cos表格查找）可以大大减少您所需的计算量（实现快速拒绝。）

您的目标是仅在近似距离（要排名或比较）之间的差异低于某个阈值时才继续进行实际的三角计算。

例如，使用具有 1000 个样本的查找表（即每 1sin次cos采样2*pi/1000），查找不确定性最多为 0.006284。使用参数 to的不确定性计算ACos，累积不确定性，也就是阈值不确定性，最多为 0.018731。

因此，如果评估两个坐标集对（距离）的Math.Sin(lat2rad) * Math.Sin(lat1rad) + Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad)使用表sin和cos查找表会产生一定的排名（根据近似值，一个距离看起来比另一个大），并且差的模量大于上述阈值，那么近似值是有效的。否则继续进行实际的三角计算。

score 4 · Accepted Answer

4

CORDIC算法是否适合您（在速度/准确性方面）？

于 2009-03-05T15:31:31.630 回答

score 3 · Accepted Answer

使用来自@Brann 的灵感，我认为您可以稍微减少计算（警告它很长一段时间，因为我做了任何这些，需要验证）。某种预计算值的查找可能是最快的

你有：

1: ACOS( SIN A SIN B + COS A COS B COS(AB) )

但是 2： COS(AB) = SIN A SIN B + COS A COS B

改写为 3： SIN A SIN B = COS(AB) - COS A COS B

将 SIN A SIN B 替换为 1. 你有：

4: ACOS( COS(AB) - COS A COS B + COS A COS B COS(AB) )

您预先计算 X = COS(AB) 和 Y = COS A COS B，然后将值放入 4

给：

ACOS( X - Y + XY )

4 次三角计算而不是 6 次！

score 2 · Accepted Answer

更改存储长/纬度的方式：

struct LongLat
{
  float
    long,
    lat,
    x,y,z;
}

创建 long/lat 时，还要计算 (x,y,z) 3D 点，该点表示以原点为中心的单位球体上的等效位置。

现在，要确定点 B 是否比点 C 更接近点 A，请执行以下操作：

// is B nearer to A than C?
bool IsNearer (LongLat A, LongLat B, LongLat C)
{
  return (A.x * B.x + A.y * B.y + A.z * B.z) < (A.x * C.x + A.y * C.y + A.z * C.z);
}

并获得两点之间的距离：

float Distance (LongLat A, LongLat B)
{
  // radius is the size of sphere your mapping long/lats onto
  return radius * acos (A.x * B.x + A.y * B.y + A.z * B.z);
}

您可以删除“半径”项，有效地标准化距离。

score 1 · Accepted Answer

切换到 sin/cos/acos 的查找表。会更快，有很多 c/c++ 定点库也包括这些。

这是其他人在Memoization上的代码。如果使用的实际值更聚集，这可能会起作用。

这是关于Fixed Point的 SO question 。

score 1 · Accepted Answer

什么是瓶颈？是正弦/余弦函数调用还是反正弦调用？

如果你的正弦/余弦调用很慢，你可以使用以下定理来防止这么多的调用：

1 = sin(x)^2 + cos(x)^2
cos(x) = sqrt(1 - sin(x)^2)

但我喜欢映射的想法，这样你就不必重新计算你已经计算过的值。虽然要小心，因为地图可能会很快变得非常大。

score 0 · Accepted Answer

您需要这些值有多精确？

如果您将您的值四舍五入，那么您可以存储所有查找的结果并检查是否已在每次计算之前使用它们？

score 0 · Accepted Answer

好吧，由于 lat 和 lon 都在一定范围内，您可以尝试使用某种形式的查找表来调用 Math.* 方法。说，一个Dictionary<double,double>

score 0 · Accepted Answer

我认为您可能需要重新检查您是如何发现该功能成为瓶颈的。（IE 您是否对应用程序进行了概要分析？）

这个方程对我来说似乎很轻，不应该造成任何麻烦。 诚然，我不知道你的申请，你说你做了很多这样的计算。

尽管如此，这是值得考虑的事情。

score 0 · Accepted Answer

正如其他人指出的那样，您确定这是您的瓶颈吗？

我已经对正在构建的类似应用程序进行了一些性能测试，在该应用程序中我调用了一个简单的方法来使用标准三角函数返回两点之间的距离。对它的 20,000 次调用将它推到了分析输出的顶部，但我无法让它更快......这只是调用次数的剪切。

在这种情况下，我需要减少对它的 # 调用......并不是说这是瓶颈。

score 0 · Accepted Answer

我使用不同的算法来计算 2 个纬度/经度位置之间的距离，它可能比你的更轻，因为它只进行 1 个 Cos 调用和 1 个 Sqrt 调用。

public static double GetDistanceBetweenTwoPos(double lat1, double long1, double lat2, double long2)
{
  double distance = 0;
  double x = 0;
  double y = 0;

  x = 69.1 * (lat1 - lat2);
  y = 69.1 * (long1 - long2) * System.Math.Cos(lat2 / 57.3);

  //calculation base : Miles
  distance = System.Math.Sqrt(x * x + y * y);

  //Distance calculated in Kilometres
  return distance * 1.609;
}

score 0 · Accepted Answer

有人已经提到过记忆，这有点相似。如果您将同一点与许多其他点进行比较，那么最好预先计算该等式的各个部分。

代替



double result = Math.Acos(Math.Sin(lat2rad) * Math.Sin(lat1rad) 
+ Math.Cos(lat2rad) * Math.Cos(lat1rad) * Math.Cos(lon2rad - lon1rad));

有：



double result = Math.Acos(lat2rad.sin * lat1rad.sin 
+ lat2rad.cos * lat1rad.cos * (lon2rad.cos * lon1rad.cos + lon1rad.sin * lon2rad.sin));

我认为这与其他人发布的公式相同，因为当您展开括号时，部分等式将消失:)

c# - 距离计算功能的优化

12 回答 12

Related

Reference