Как эффективно рассчитать расстояние между парой координат с помощью data.table: =

Я хочу найти наиболее эффективный (самый быстрый) метод вычисления расстояний между парами координат широта и долгота.

Не очень эффективное решение было представлено (здесь) с использованием sapply и spDistsN1{sp}. Я считаю, что это можно было бы сделать намного быстрее, если бы можно было использовать spDistsN1{sp} внутри data.table с оператором :=, но я не смог этого сделать. Какие-либо предложения?

Вот воспроизводимый пример:

# load libraries
  library(data.table)
  library(dplyr)
  library(sp)
  library(rgeos)
  library(UScensus2000tract)

# load data and create an Origin-Destination matrix
  data("oregon.tract")

# get centroids as a data.frame
  centroids <- as.data.frame(gCentroid(oregon.tract,byid=TRUE))

# Convert row names into first column
  setDT(centroids, keep.rownames = TRUE)[]

# create Origin-destination matrix
  orig <- centroids[1:754, ]
  dest <- centroids[2:755, ]
  odmatrix <- bind_cols(orig,dest)
  colnames(odmatrix) <- c("origi_id", "long_orig", "lat_orig", "dest_id", "long_dest", "lat_dest")

Моя неудачная попытка использования data.table

odmatrix[ , dist_km := spDistsN1(as.matrix(long_orig, lat_orig), as.matrix(long_dest, lat_dest), longlat=T)]

Вот решение, которое работает (но, вероятно, менее эффективно)

odmatrix$dist_km <- sapply(1:nrow(odmatrix),function(i)
  spDistsN1(as.matrix(odmatrix[i,2:3]),as.matrix(odmatrix[i,5:6]),longlat=T))

head(odmatrix)

>   origi_id long_orig lat_orig  dest_id long_dest lat_dest dist_km
>      (chr)     (dbl)    (dbl)    (chr)     (dbl)    (dbl)   (dbl)
> 1 oregon_0   -123.51   45.982 oregon_1   -123.67   46.113 19.0909
> 2 oregon_1   -123.67   46.113 oregon_2   -123.95   46.179 22.1689
> 3 oregon_2   -123.95   46.179 oregon_3   -123.79   46.187 11.9014
> 4 oregon_3   -123.79   46.187 oregon_4   -123.83   46.181  3.2123
> 5 oregon_4   -123.83   46.181 oregon_5   -123.85   46.182  1.4054
> 6 oregon_5   -123.85   46.182 oregon_6   -123.18   46.066 53.0709

person rafa.pereira    schedule 23.04.2016    source источник
comment
Посмотрите на код для spDistsN1. Вам следует переписать свою собственную функцию, которая не требует преобразования в матрицу, так как я уверен, что это то место, где большую часть времени находится.   -  person MichaelChirico    schedule 24.04.2016
comment
Также ознакомьтесь с этим сообщением: stackoverflow.com/questions/36686312/   -  person chinsoon12    schedule 24.04.2016


Ответы (2)


Я написал свою собственную версию geosphere::distHaversine, чтобы она более естественно вписывалась в вызов data.table :=, и может быть здесь полезна

dt.haversine <- function(lat_from, lon_from, lat_to, lon_to, r = 6378137){
    radians <- pi/180
    lat_to <- lat_to * radians
    lat_from <- lat_from * radians
    lon_to <- lon_to * radians
    lon_from <- lon_from * radians
    dLat <- (lat_to - lat_from)
    dLon <- (lon_to - lon_from)
    a <- (sin(dLat/2)^2) + (cos(lat_from) * cos(lat_to)) * (sin(dLon/2)^2)
    return(2 * atan2(sqrt(a), sqrt(1 - a)) * r)
}

Обновление 18.07.2019

Вы также можете написать версию на C ++ через Rcpp.

#include <Rcpp.h>
using namespace Rcpp;

double inverseHaversine(double d){
  return 2 * atan2(sqrt(d), sqrt(1 - d)) * 6378137.0;
}

double distanceHaversine(double latf, double lonf, double latt, double lont,
                         double tolerance){
  double d;
  double dlat = latt - latf;
  double dlon =  lont - lonf;

  d = (sin(dlat * 0.5) * sin(dlat * 0.5)) + (cos(latf) * cos(latt)) * (sin(dlon * 0.5) * sin(dlon * 0.5));
  if(d > 1 && d <= tolerance){
    d = 1;
  }
  return inverseHaversine(d);
}

double toRadians(double deg){
  return deg * 0.01745329251;  // PI / 180;
}

// [[Rcpp::export]]
Rcpp::NumericVector rcpp_distance_haversine(Rcpp::NumericVector latFrom, Rcpp::NumericVector lonFrom, 
                        Rcpp::NumericVector latTo, Rcpp::NumericVector lonTo,
                        double tolerance) {

  int n = latFrom.size();
  NumericVector distance(n);

  double latf;
  double latt;
  double lonf;
  double lont;
  double dist = 0;

  for(int i = 0; i < n; i++){

    latf = toRadians(latFrom[i]);
    lonf = toRadians(lonFrom[i]);
    latt = toRadians(latTo[i]);
    lont = toRadians(lonTo[i]);
    dist = distanceHaversine(latf, lonf, latt, lont, tolerance);

    distance[i] = dist;
  }
  return distance;
}

Сохраните где-нибудь этот файл и используйте Rcpp::sourceCpp("distance_calcs.cpp") для загрузки функций в сеанс R.

Вот несколько тестов их эффективности по сравнению с исходными geosphere::distHaversine и geosphere::distGeo

Я сделал объекты 85 тыс. Строк, чтобы они были более значимыми.


dt <- rbindlist(list(odmatrix, odmatrix, odmatrix, odmatrix, odmatrix, odmatrix))
dt <- rbindlist(list(dt, dt, dt, dt, dt, dt, dt, dt, dt, dt, dt, dt, dt, dt, dt, dt, dt, dt, dt))

dt1 <- copy(dt); dt2 <- copy(dt); dt3 <- copy(dt); dt4 <- copy(dt)


library(microbenchmark)

microbenchmark(

  rcpp = {
    dt4[, dist := rcpp_distance_haversine(lat_orig, long_orig, lat_dest, long_dest, tolerance = 10000000000.0)]
  },

  dtHaversine = {
    dt1[, dist := dt.haversine(lat_orig, long_orig, lat_dest, long_dest)]
  }   ,

  haversine = {
    dt2[ , dist := distHaversine(matrix(c(long_orig, lat_orig), ncol = 2), 
                                 matrix(c(long_dest, lat_dest), ncol = 2))]
  },

  geo = {
    dt3[ , dist := distGeo(matrix(c(long_orig, lat_orig), ncol = 2), 
                           matrix(c(long_dest, lat_dest), ncol = 2))]
  },
  times = 5
)

# Unit: milliseconds
#       expr       min        lq      mean    median        uq        max neval
#        rcpp  5.622847  5.683959  6.208954  5.925277  6.036025   7.776664     5
# dtHaversine  9.024500 12.413380 12.335681 12.992920 13.590566  13.657037     5
#   haversine 30.911136 33.628153 52.503700 36.038927 40.791089 121.149197     5
#         geo 83.646104 83.971163 88.694377 89.548176 90.569327  95.737117     5

Естественно, из-за того, что расстояния рассчитываются двумя разными методами (гео и гаверсинус), результаты будут немного отличаться.

person SymbolixAU    schedule 02.02.2017
comment
ваше решение возвращает результат в км? - person rafa.pereira; 03.02.2017
comment
@ rafa.pereira - я думаю, это в метрах - person SymbolixAU; 03.02.2017
comment
Меня очень впечатлило повышение эффективности вашего решения, поэтому я награждаю вас принятым ответом. - person rafa.pereira; 03.02.2017
comment
@ rafa.pereira очень щедрый! на самом деле именно ваше решение здесь вдохновило этот ответ - person SymbolixAU; 03.02.2017
comment
Версия C ++ (с использованием Rcpp) формулы гаверсинуса включена в пространственный риск :: haversine - person mharinga; 08.10.2019
comment
Я попробовал версию на C ++, так как у меня возникла та же проблема оптимизации скорости вычисления расстояния: stackoverflow.com/questions/62871216/ Версия C ++, предоставленная @SymbolixAU, очень быстрая, но, к сожалению, неточная. У меня было отклонение до 4 км по сравнению с расчетами, выполненными distGeo и distHaversine. Вы улучшили это решение, так как этот пост опубликован в 2019 году? Хотел бы это увидеть. - person Andreas; 14.07.2020

Благодаря комментарию @chinsoon12 я нашел довольно быстрое решение, сочетающее distGeo{geosphere} и data.table. В моем ноутбуке быстрые решения были более чем в 120 раз быстрее альтернативы.

Давайте увеличим набор данных, чтобы сравнить быстродействие.

# Multiplicate data observations by 1000 
  odmatrix <- odmatrix[rep(seq_len(nrow(odmatrix)), 1000), ]

медленное решение

system.time(
           odmatrix$dist_km <- sapply(1:nrow(odmatrix),function(i)
             spDistsN1(as.matrix(odmatrix[i,2:3]),as.matrix(odmatrix[i,5:6]),longlat=T)) 
            )

 >   user  system elapsed 
 >   222.17    0.08  222.84 

быстрое решение

# load library
  library(geosphere)

# convert the data.frame to a data.table
  setDT(odmatrix)

system.time(
            odmatrix[ , dist_km2 := distGeo(matrix(c(long_orig, lat_orig), ncol = 2), 
                                            matrix(c(long_dest, lat_dest), ncol = 2))/1000]
           )

>   user  system elapsed 
>   1.76    0.03    1.79 
person rafa.pereira    schedule 24.04.2016
comment
идентичны ли результаты? - person Edzer Pebesma; 24.04.2016
comment
Хороший замечание @EdzerPebesma. Результаты примерно такие же (разница в несколько сантиметров) для этого конкретного примера. Однако на больших расстояниях разница может немного увеличиться. Это потому, что spDistsN1{sp} использует расстояние по Евклиду или Большому кругу между точками, а distGeo{geosphere} вычисляет расстояние на эллипсоиде. - person rafa.pereira; 24.04.2016