2

Доброго времени суток!

Есть две координаты, каждая с широтой/долготой типа 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, см. здесь.


Спасибо.

11
  • 1
    Для начала, чисто программистский трюк: можно подсчитать расстояния до объекта как числа, запомнить их, и сортировать по ним. Таким образом, у вас будет N вычислений расстояния, а не N Log N, что уже ускорит вычисления.
    – VladD
    20 янв 2014 в 23:39
  • 1
    @Stanislaw Pankevich: Вроде ничего не улучшается. Однако ваш код не реэнтерабельный и не потокобезопасный. Может быть, сделать вот так? (Хотя, не уверен, что это лучше с т. зр. производительности.)
    – VladD
    21 янв 2014 в 13:06
  • 1
    @Stanislaw Pankevich: Ну, если чисто теоретически код сортировки будет вызывать сортировку того же массива с другими параметрами, тогда поле precalculatedDistanceToLocation было бы затёрто. Это в вашем случае, кажется, невозможно, но иногда такие проблемы встречаются. Или если один элемент будет принадлежать нескольким спискам, которые будут «одновременно» сортироваться. (С другой стороны, семантически нехорошо добавлять в CLLocation поле, нужное лишь на момент сортировки, но это уже красивость.)
    – VladD
    21 янв 2014 в 15:36
  • 1
    @Stanislaw Pankevich: Пожалуйста! --- Ещё одна идея: создаём массив структур типа { double distance, int originalIndex } (расстояние, индекс в начальном массиве), сортируем его по distance, создаём новый NSArray *, и копируем данные из исходного массива по новым индексам. Так можно избежать дополнительного поля. [Опять-таки, если игра стоит свеч.]
    – VladD
    21 янв 2014 в 18:30
  • 2
    @VladD, в моём случае игра точно стоит свеч - 30 минут назад я сделал ровно то, что вы только что предложили, и это очень заметно увеличивает производительность (исчез оверхед от инициализации Objective-C объектов). Так что, честь имею ! ;) Ещё раз спасибо за участие! 21 янв 2014 в 18:47

1 ответ 1

1

Пишу редко, но много и, надеюсь, метко. А что делать, раз на дворе бессрочный отпуск))

Этот топик получился своеобразным "два в одном": благодаря комментариям @VladD мне удалось прояснить то, как улучшить оригинальный алгоритм сортировки массива гео-точек по отношению к данной точке (взятый когда-то без оглядки и какой-либо рефлексии с просторов StackOverflow - тот, что описан первым в вопросе), и как мне кажется всё получилось более, чем удачно - см. комментарии и отрывок кода в конце вопроса.

А вот ответ на оригинальный вопрос:

В топике параллельно открытом на SO некто @Taum прислал решение, которое с моими небольшими правками и оптимизациями мне подошло, как достойная альтернатива -[CLLocation distanceFromLocation:] и MKMetersBeetweenMapPoints. Вот текущие варианты обеих функций (расстояние и квадрат расстояния):

static inline CLLocationDistance SquaredGeodesicDistance(CLLocationCoordinate2D a, CLLocationCoordinate2D b) {
    static const CLLocationDistance EarthRadiusInMetersSquared = 40612548751652.179688;
    static const double DegreeesToRad = 0.017453292519943295769236907684886;

    CLLocationDegrees dtheta = (a.latitude - b.latitude) * DegreeesToRad;
    CLLocationDegrees dlambda = (a.longitude - b.longitude) * DegreeesToRad;
    CLLocationDegrees mean_t = (a.latitude + b.latitude) * DegreeesToRad / 2.0;
    CLLocationDegrees cos_meant = cos(mean_t);

    return EarthRadiusInMetersSquared * (dtheta * dtheta + cos_meant * cos_meant * dlambda * dlambda);
}

static inline CLLocationDistance GeodesicDistance(CLLocationCoordinate2D a, CLLocationCoordinate2D b) {
    static const CLLocationDistance EarthRadiusInMeters = 6372797.560856;
    static const double DegreeesToRad = 0.017453292519943295769236907684886;

    CLLocationDegrees dtheta = (a.latitude - b.latitude) * DegreeesToRad;
    CLLocationDegrees dlambda = (a.longitude - b.longitude) * DegreeesToRad;
    CLLocationDegrees mean_t = (a.latitude + b.latitude) * DegreeesToRad / 2.0;
    CLLocationDegrees cos_meant = cos(mean_t);

    return EarthRadiusInMeters * sqrt(dtheta * dtheta + cos_meant * cos_meant * dlambda * dlambda);
}

Безусловное достойнство этого метода - это то, что он работает заметно быстрее, чем оба метода Apple API: -[CLLocation distanceFromLocation:] и MKMetersBeetweenMapPoints (к слову сказать, попутно я выяснил, что в свою очередь сравнивая их между собой: MKMetersBeetweenMapPoints - работает значительно медленнее, чем distanceFromLocation: - откуда вывод, что для дорогих вычислений лучше оставаться в пространстве географических координат lat/lng (CLLocationDegrees) и избегать переходов к MKMapPoints).

Кроме того, в данной реализации этого метода доступна его "квадратичная версия", которая позволяет сэкономить на вычислениях вроде "есть точка и набор точек - к какой точке из этого набора данная точка ближе всего" - так как при сравнении расстояний достаточно сравнивать их квадраты.

Небольшой недостаток этого метода - это то, что он работает с небольшой погрешностью по сравнению с методами Apple API, но для той области, где я собираюсь его использовать (см. ниже) это не важно.

К сожалению, у меня нет времени проникнуть в суть математики, которая стоит за этим методом и за аналогичными методами в Википедии - поэтому единственное, что я пока что могу предположить по поводу данной реализации - это то, что она немного более грубая по сравнению с тем, что делают Apple API - отсюда скорость (хорошо!) и одновременно погрешность (плохо, но не критично).


Теперь добавлю контекста для этого вопроса: я экспериментирую с несколькими алгоритмами класстеризации гео-точек на карте - сравниваю как работают те, которые уже есть на Github, и те, которые я попробовал написать сам -

Например, в алгоритме K-means операция "найти ближайшую точку из набора точек до данной точки" является ключевой и поэтому от любой даже самой небольшой оптимизации подсчёта расстояния между точками (или квадрата этого расстояния) алгоритм начинает хорошо выигрывать.

Я хотел задать на ХК вопрос про такие алгоритмы (ключевые слова: кластеризация, K-Means, K-деревья, Quad-деревья, ...), но как-то всё не соображу, как бы это грамотно сформулировать, чтобы получить полезный результат (Исследование?).


Отмечу, что оба решения прекрасно совмещаются и отлично подходят для задач, когда нужна скорость.


Как всегда отмечаю, что буду рад любым комментариям/замечаниям/возражениям/недоумениям/злобнымнападкам по любым вопросам, заявленным в топике.

Да, и ещё раз спасибо за помощь, @VladD!

3
  • Станислав, спасибо за код! У меня только один вопрос. > Кроме того, в данной реализации этого метода доступна его "квадратичная версия", которая позволяет сэкономить на вычислениях вроде "есть точка и набор точек - к какой точке из этого набора данная точка ближе всего" - так как при сравнении расстояний достаточно сравнивать их квадраты. Не знаком с этой теорией. Почему для сравнения дистанций между точками нужно использовать квадраты, а не просто сравнивать получаемые дистанции и получать минимальную?
    – kuliba
    16 фев 2014 в 12:21
  • 1
    Я полагаю, теория скрывается в простом математическом неравенстве: для неотрицательных чисел (расстояния всегда >= 0) будет верно: что если a > b, то и квадрат a больше квадрата b, обратное при этом тоже верно. (a >= b) <=> (pow(a, 2) >= pow(b, 2)) 16 фев 2014 в 13:15
  • 2
    > Почему для сравнения дистанций между точками нужно использовать квадраты, а не просто сравнивать получаемые дистанции и получать минимальную? Здесь правильнее будет сказать не "нужно", а "лучше", потому что если Вас интересуют не конкретные дистанции, а отношения между ними, то быстрее сравнивать квадраты, так как для каждого данного расстояния происходит экономия: минус одно вычисление квадратного корня. Я понятно объяснил? 16 фев 2014 в 13:24

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.