我正在尝试减少并组合一些点到这些位置的中心点。现在,我通过找到最接近的一对,将它们组合起来并重复,直到将其减少到我的目标(旁注:实际上我通过排序来减少问题)(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
。 (它跟踪组合计数,因此可以通过这种方式找到正确的平均中心)
Results:这是我当前的距离函数,带有 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;
}