减少纬度和经度点的最快方法 [英] Fastest way to reduce number of latitude and longitude points

问题描述

我正在尝试减少并将这些点合并到这些位置的中心点。现在，我通过找到最接近的对，组合并重复直到将其减少到目标为止来进行蛮力操作（注意：实际上，我通过按（lat * lat + long * long），然后在每个点的每一边搜索10％，根据我的测试，它总是找到该范围内的最短距离。）

I'm trying to reduce and combine a number of points to the center point of those locations. Right now I'm brute-forcing it by finding the closest pair, combining those and repeating until I've reduced it to my target (side note: actually I reduced the problem by sorting by (lat*lat+long*long) then searching 10% on either side of each point, which with my tests has always found the shortest distance within that range).

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

For an example I'd want to reduce 4000 points down to 1000, ideally combining the closest points into the center of those closest points. Basically to build marker points that reflect the number of addresses in that area.

是否有更好的算法可以使我得到尽可能准确的结果？还是更快的距离算法？我想它只需要在短距离内准确即可。

Is there any better algorithm that would give me as accurate as possible results? Or a quicker distance algorithm? I guess it does only need to be accurate at short distances

现在我正在寻找距离（维基百科

Right now I'm finding the distance with (Wikipedia had it under "spherical earth projected to a plane"):

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直到我达到我的最终分数目标，但是我不确定如何使完美主义达到我想要的精确度。这就是我能想到的所有方法，具体取决于输入的点列表的顺序。

I've thought about grouping all the points within x distance of each other, then expanding x until I get to my target number of final points, but I'm not sure how to make that as accurate as my perfectionism would want it. That is all the ways I can think of would vary slightly depending on the order of the input list of points.

编辑描述我当前算法的处理方式（这是找到我想要的结果的理想方法，但是更快的近似值是值得的）：

Edit to describe how my current algorithm processes (This is the ideal way to find the results I want, but an approximation that is much quicker would be worth it):

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

Describing it linearly, if you had 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，以便以此方式找到正确的平均中心）

1. It would combine 4+5=4.5 [first 1.0 distance it finds]
2. (4.5*2+6)/3=5 -- x=1,5,10,20,22 [1.5 distance]
3. 20+22=21 -- x=1,5,10,21 [2.0 distance]
4. (5*3+1)/4=4 -- x=4,10,21 [4.0 distance]
5. (4*4+10)/5.2 -- So you'd end up with x=5.2,21. (It keeps track of the CombineCount so it can find the correct average center in this way)

---

结果：
这是我当前的Distance函数，其中生成了cos ^ 2的查找表。还没有时间检查我的点之间的距离，因此还没有实现乔伊建议的近似cos ^ 2的建议，但这可以提高此处查找表的速度。

---

Results: Here is my current Distance function, with lookup table generation for cos^2. Haven't had time to check how close together my points are, so haven't implemented Joey's suggestion of approximating the cos^2, but that could improve the speed over the lookup table here.

我尝试过的K-Cluster算法（请参阅我对该答案的评论）没有按照我的意愿将它们组合在一起，最终导致在地图和一些指向边缘的点。因此，除非我可以纠正我正在使用速度较慢的算法。

The K-Cluster algorithm I tried (see my comment on that answer) did not combine them as I wanted, it ended up with a ton of points near the center of the map and few points toward the edges. So unless I can correct that I'm using my algorithm which is slower.

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

推荐答案

加快测算距离点之间：

如果您做一些基础代数，您会得到：

If you do some elementary algebra you get:

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次计算。离开：

The first thing you can do to speed this up is normalise to the radius of the Earth (R) and compare squared distances rather than distances, thus avoiding the square root and R term, saving yourself 2 calculations per comparison. Leaving:

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。

Another thing you could do is precalculate Lat^2 and Lon^2 for each coordinate - reducing the number of calculations for each comparison by 4.

如果这些点都相对在纬度上靠得很近，您可以通过使用随机点的纬度或所有点的平均纬度（而不是被比较的两个点的平均纬度）预先计算出cos ^ 2项的近似值。最后，每个比较的计算量减少了4个。

Further, if the points are all relatively close together in latitude you could take an approximation for the cos^2 term by precalculating it using the latitude of a random point or the average latitude of all the points, rather than the average latitude of the two points being compared. This reduces the number of calculations for each comparison by another 4.

最后，您可以为每个点预先计算2 * Lat和2 * Lon，从而省去了另外2个计算

Finally, you could pre-calculate 2*Lat and 2*Lon for each point cutting out 2 more calculations for each comparison.

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

None of this improves your algorithm per se but it should make it run faster and can be applied to any algorithm that needs to compare the distances between points.

这篇关于减少纬度和经度点的最快方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！