减少纬度和经度点数的最快方法

Question

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

举个例子,我希望将4000点减少到1000点,理想情况下将最近点组合到最近点的中心.基本上是构建反映该区域中地址数量的标记点.

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

---

现在我找到距离(维基百科在"投射到飞机上的球形地球"下):

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的查找表生成.没有时间检查我的点有多接近,所以没有实现Joey建议的近似cos ^ 2,但这可以提高查询表的速度.

在K-聚类算法我想(看到我对这个问题的答案评论),因为我想没有将它们组合起来,它结束了与附近的地图和几个点向边缘的中心一吨的点.所以除非我能纠正我使用的算法慢一点.

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

Answer 1

加快计算点之间的距离:

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

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次计算.

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