gpt4 book ai didi

c# - 减少纬度和经度点数量的最快方法

转载 作者:可可西里 更新时间:2023-11-01 08:43:50 26 4
gpt4 key购买 nike

我正在尝试将一些点减少并组合到这些位置的中心点。现在我通过找到最接近的对来暴力破解它,将它们组合并重复直到我将它减少到我的目标(旁注:实际上我通过按 (lat*lat+long* long) 然后在每个点的两侧搜索 10%,通过我的测试总是找到该范围内的最短距离)。

例如,我想将 4000 个点减少到 1000 个,理想情况下将最近的点组合到这些最近点的中心。基本上是建立反射(reflect)该区域地址数量的标记点。

有没有更好的算法可以给我尽可能准确的结果?或者更快的距离算法?我想它只需要在短距离内准确


现在我正在寻找距离(维基百科在“球形地球投影到平面”下):

double dLat = pos2.LatitudeR - pos1.LatitudeR;
double dLon = pos2.LongitudeR - pos1.LongitudeR;

double cosLatM = Math.Cos((pos2.LatitudeR + pos1.LatitudeR)/2) * dLon;
double a = dLat*dLat + cosLatM*cosLatM;

我考虑过将所有点分组在 x 距离内,然后扩展 x 直到我达到我的目标最终点数,但我不确定如何使它像我的完美主义所希望的那样准确它。这是我能想到的所有方式,根据输入点列表的顺序会略有不同。


编辑以描述我当前的算法处理方式(这是找到我想要的结果的理想方式,但更快的近似值是值得的):

线性描述它,如果你有 x=1,4,5,6,10,20,22

  1. 它将合并 4+5=4.5 [它找到的第一个 1.0 距离]
  2. (4.5*2+6)/3=5 -- x=1,5,10,20,22 [1.5 距离]
  3. 20+22=21 -- x=1,5,10,21 [2.0 距离]
  4. (5*3+1)/4=4 -- x=4,10,21 [4.0 距离]
  5. (4*4+10)/5.2 -- 所以你最终会得到 x=5.2,21。 (它跟踪 CombineCount,因此可以通过这种方式找到正确的平均中心)

结果:这是我当前的距离函数,带有 cos^2 的查找表生成。没有时间检查我的点有多接近,所以没有实现乔伊关于近似 cos^2 的建议,但这可以提高此处查找表的速度。

我尝试过的 K-Cluster 算法(请参阅我对该答案的评论)没有按照我的意愿将它们组合起来,它最终在 map 中心附近有大量点,而只有少数点靠近边缘。因此,除非我能更正我使用的是较慢的算法。

public static double Distance(AddressCoords pos1, AddressCoords pos2, DistanceType type)
{
if (LookupTable == null) LookupTable = BuildLookup();

double R = (type == DistanceType.Miles) ? 3960 : 6371;

double dLat = pos2.LatitudeR - pos1.LatitudeR;
double dLon = pos2.LongitudeR - pos1.LongitudeR;

double LatM = ((pos2.LatitudeR + pos1.LatitudeR)/2);
if (LatM < 0) LatM = -LatM; //Don't allow any negative radian values
double cosLatM2 = LookupTable[(int)(LatM * _cacheStepInverse)];
double a = dLat*dLat + cosLatM2 * dLon*dLon;

//a = Math.Sqrt(a);

double d = a * R;

return d;
}

private const double _cacheStep = 0.00002;
private const double _cacheStepInverse = 50000;

private static double[] LookupTable = null;

public static double[] BuildLookup()
{
// set up array
double maxRadian = Math.PI*2;
int elements = (int)(maxRadian * _cacheStepInverse) + 1;

double[] _arrayedCos2 = new double[elements];
int i = 0;
for (double angleRadians = 0; angleRadians <= maxRadian;
angleRadians += _cacheStep)
{
double cos = Math.Cos(angleRadians);
_arrayedCos2[i] = cos*cos;
i++;
}
return _arrayedCos2;
}

最佳答案

为了加快计算点之间的距离:

如果你做一些初等代数你会得到:

D = R*Sqrt(Lat2^2 + Lat1^2 - 2*Lat1*Lat2 + cos^2((Lat2 + Lat1) /2)(Lon2^2 + Lon1^2 - 2*Lon1*Lon2))

要加快速度,您可以做的第一件事是归一化为地球半径 (R) 并比较平方距离而不是距离,从而避免平方根和 R 项,每次比较节省 2 次计算。离开:

valToCompare = Lat2^2 + Lat1^2 - 2*Lat1*Lat2 + cos^2((Lat2 + Lat1) /2)(Lon2^2 + Lon1^2 - 2*Lon1*Lon2)

您可以做的另一件事是为每个坐标预先计算 Lat^2 和 Lon^2 - 将每次比较的计算次数减少 4。

此外,如果这些点在纬度上都相对靠近,您可以使用随机点的纬度或所有点的平均纬度而不是平均纬度来预先计算 cos^2 项的近似值被比较的两个点。这将每次比较的计算次数减少了另外 4 次。

最后,您可以为每个点预先计算 2*Lat 和 2*Lon,为每次比较减少 2 个以上的计算。

这些都不会改进您的算法本身,但它应该使它运行得更快并且可以应用于需要比较点之间距离的任何算法。

关于c# - 减少纬度和经度点数量的最快方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7643424/

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com