Доброго времени суток!
Есть две координаты, каждая с широтой/долготой типа double:
double lat1,lng1,lat2,lng2
.
Вопрос: как подсчитать расстояние в метрах между этими координатами?
Я столкнулся с тем, что мне хотелось бы применить некоторые оптимизации для вычислений, связанных с большим количеством гео-точек на карте (алгоритмы для класстеризации), и для этого мне было бы хорошо разобраться в том, как считают расстояния соответствующие функции из Apple API, но так как их код скрыт, я решил попробовать разобраться с тем, как они считают расстояния, сам.
Буду благодарен за любую подсказку по поводу решения этой (наверное) простой задачи. Я уверен в том, что, конечно, разберусь с этим вопросом и без помощи ХК, просто надеюсь, вдруг кто-то из участников внесёт ясность блестящим и точным ответом)) Как всегда, подчёркиваю, что мне интересен ваш личный опыт, а не ссылки на то, что гуглится сверху: например, может быть вы знаете, как сделать этот подсчёт самым быстрым способом.
P.S. Также параллельно я только что открыл топик на StackOverflow про те самые Apple API, вдруг кто оттуда подскажет, что скрывается в их чёрном ящике.
Добавлю немного контекста:
+ (NSArray *)sortArray:(NSArray *)array byDistanceToLocation:(CLLocation *)location {
return [array sortedArrayUsingComparator:^NSComparisonResult(id obj1, id obj2) {
CLLocationCoordinate2D place1Coordinate = CLLocationCoordinate2DMake([[obj1 valueForKey:@"latitude"] doubleValue], [[obj1 valueForKey:@"longitude"] doubleValue]);
CLLocation *obj1location = [CLLocation locationWithCoordinate:place1Coordinate];
CLLocationCoordinate2D place2Coordinate = CLLocationCoordinate2DMake([[obj2 valueForKey:@"latitude"] doubleValue], [[obj2 valueForKey:@"longitude"] doubleValue]);
CLLocation *obj2location = [CLLocation locationWithCoordinate:place2Coordinate];
if ([location distanceFromLocation:obj1location] > [location distanceFromLocation:obj2location]) {
return (NSComparisonResult)NSOrderedDescending;
}
if ([location distanceFromLocation:obj1location] < [location distanceFromLocation:obj2location]) {
return (NSComparisonResult)NSOrderedAscending;
}
return (NSComparisonResult)NSOrderedSame;
}];
}
Приведённый метод сортирует массив с точками на основе расстояния между каждой из этих точек и данной точкой.
Возникла простая мысль: почему бы для возможного ускорения процесса вместо полновесного подсчёта расстояний с помощью Apple API: -[CLLocation distanceFromLocation:]
не сравнивать между собой "неполные эвклидовы расстояния" (сумма квадратов без извлечения корня), подсчитанные для обычных географических координат (рассуждение очень похоже на то, которое провёл @aknew в комментарии): сравнивать pow(lat1 - lat, 2) + pow(lng1 - lng, 2)
и pow(lat2 - lat, 2) + pow(lng2 - lng, 2)
? Наивное размышление подсказывает, что вроде бы результат должен получаться тот же самый, если не забираться сильно к полюсам, но вот результаты получаются какие-то немного странные - "почти те", да не совсем - я встречаю места которые при повторном их измерении с помощью distanceFromLocation:
стоят в обратном порядке: вроде "сначала 12км, а потом 11км" - то есть порядок сортировки нарушается. Отсюда и возникла мысль разобраться в том, что же стоит за distanceFromLocation:
.
+ (NSArray *)sortArrayOfLocations3:(NSArray *)array byDistanceToLocation:(CLLocation *)location {
for (EKALocation *_location in array) {
_location->precalculatedDistanceToLocation = @([_location distanceFromLocation:location]);
}
return [array sortedArrayUsingDescriptors:@[[NSSortDescriptor sortDescriptorWithKey:@"precalculatedDistanceToLocation" ascending:YES]]];
}
Если интересно, почему ->, а не Objective-C @property, см. здесь.
Спасибо.
N
вычислений расстояния, а неN Log N
, что уже ускорит вычисления.precalculatedDistanceToLocation
было бы затёрто. Это в вашем случае, кажется, невозможно, но иногда такие проблемы встречаются. Или если один элемент будет принадлежать нескольким спискам, которые будут «одновременно» сортироваться. (С другой стороны, семантически нехорошо добавлять вCLLocation
поле, нужное лишь на момент сортировки, но это уже красивость.){ double distance, int originalIndex }
(расстояние, индекс в начальном массиве), сортируем его поdistance
, создаём новыйNSArray *
, и копируем данные из исходного массива по новым индексам. Так можно избежать дополнительного поля. [Опять-таки, если игра стоит свеч.]