как быстро найти ближайшую точку в большой сетке

Question

У меня есть сетка, состоящая из 1k точек (long и lat) grid

У меня есть еще один список из 10 тыс. Точек (также лонг и лат) pts

Я хочу найти, к какой точке сетки каждое значение в пунктах ближе всего.

У меня есть алгоритм перебора, но он медленный:

d=NULL
for( i in 1:nrow(pts){
    for(j in 1:nrow(grid){
        d=d,distHaversine(pts[i,2:3],grid[j,2:3]))
}
}
m1=data.frame(matrix(d,ncol=nrow(grid),byrow=1)
c=apply(m,2,which.min)

есть способ ускорить это, и грубая сила довольно медленная и утомительная.

Я использую R

Answer 1

distHaversine векторизовано, поэтому вам нужен только один цикл. И вам, конечно, не нужно хранить все расстояния, просто сохраняйте минимум каждую итерацию, если это все, что вам нужно.

c = numeric(nrow(pts))
for( i in 1:nrow(pts){
  c[i] = which.min(distHaversine(pts[i, 2:3], grid[, 2:3])
}

Вышеуказанное должно работать и быть значительно быстрее. если ты все еще хотите идти быстрее, вы можете посмотреть на параллельное выполнение итераций.