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