减少纬度和经度点数的最快方法
我正在尝试减少并将多个点组合到这些位置的中心点。 现在我通过寻找最接近的一对来强制它，结合它们并重复直到我将它减少到我的目标（旁注：实际上我通过排序(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 ，则线性描述
- 它会结合4 + 5 = 4.5 [找到的第一个1.0距离]
- （4.5 * 2 + 6）/ 3 = 5 –
x=1,5,10,20,22[1.5距离] - 20 + 22 = 21 –
x=1,5,10,21[2.0距离] - （5 * 3 + 1）/ 4 = 4 –
x=4,10,21[4.0距离] - （4 * 4 + 10）/5.2 – 所以你最终得到
x=5.2,21。 （它跟踪CombineCount，以便以这种方式找到正确的平均中心）
结果：这是我当前的距离函数，其中cos ^ 2的查找表生成。 没有时间检查我的点有多接近，所以没有实现Joey建议的近似cos ^ 2，但这可以提高查询表的速度。
我尝试过的K-Cluster算法（参见我对该答案的评论）并没有像我想的那样将它们组合在一起，它最终得到了地图中心附近的大量点和边缘的几点。 所以除非我能纠正我正在使用的算法慢一些。
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个计算。
这些都不会改善您的算法本身，但它应该使它运行得更快，并且可以应用于任何需要比较点之间距离的算法。
您是否考虑过查看K-Cluster算法？
这些算法用于根据最近的平均值将关闭/相关对象（在您的情况下，点）“分组”为群集。 这些算法通常都经过了相当优化，并且可以处理大量数据。 在4000点 – > 1000点的情况下，您将对数据运行1000-Cluster运行，并返回1000组点，每组可以合并为单个点。
至于一种有效的方法，您是否考虑在地图上铺设网格，然后将每个点分配给网格中相应的单元格？ 这应该有很好的表现。
更好（但更慢）的方法是使用动态细胞而不是固定细胞，如上面的建议。 你从没有细胞开始。 然后放下地图中的第一个点并定义一个周围有一些预定尺寸的单元格。 然后删除地图上的下一个点。 如果它落在前一个单元格中，则将其添加到其中，并可能在两个点周围重新定位单元格。 如果该点落在单元格之外，则为其创建第二个单元格。 现在，您将第三个点添加到地图中，并针对两个单元格进行检查。 此过程将继续，直到您将所有点添加到地图。 我希望你明白这个主意。 我认为你可以通过改变细胞的大小来大致限制减少的点数。
编辑（基于rrenaud的评论）：您可以开始使用大单元格大小并应用上述算法之一。 如果您最终得到的单元格数量太少，那么您可以在每个单元格上重复算法并进一步细分它们。 虽然这不允许您精确地减少到固定数量的点，但您可以非常接近。