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 that you have read and understand our privacy policy and code of conduct.

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