Самый быстрый способ уменьшить количество точек широты и долготы

Я пытаюсь уменьшить и объединить несколько точек к центральной точке этих мест. Сейчас я пытаюсь найти ближайшую пару, объединить их и повторять до тех пор, пока не уменьшу их до заданного значения (побочное замечание: на самом деле я решил проблему сортировкой по (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, чтобы найти правильный средний центр таким образом)

Результаты: Вот моя текущая функция Distance, с генерацией таблицы поиска для cos^2. У меня не было времени проверить, насколько близко друг к другу находятся мои точки, поэтому я не реализовал предложение Джоуи об аппроксимации 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;
}