Get K nearest neighbors based on latitude and longitude

Question

I have latitude and longitude data for different points. This is a simple version of my data:

# Add library
library(tidyverse)

# Generate data
distance <-
  tibble(
    location = c("first", "second", "third"),
    lat = c(33.720792, 33.715187, 33.714848),
    long = c(-84.468126, -84.468684, -84.454265)
  ) 

Which produces data that looks like this:

# A tibble: 3 x 3
  location   lat  long
  <chr>    <dbl> <dbl>
1 first     33.7 -84.5
2 second    33.7 -84.5
3 third     33.7 -84.5

What I'd like to do is take these latitude and longitude to get the full ranking of nearest neighbors for each location. For example, ideally my final data would look like this:

As you can see the first column in this new data frame contains the first nearest neighbor to location "first", the second column provides the next nearest neighbor, and so on.

Does anyone know how I can make the data frame that I need?

Answer 1

You can use the FNN package to find the k-nearest-neighbours. It handles large amounts of data quite well, so even with large datasets you should be able to find the full ranking with this code:

# Add library
library(tidyverse)
library(FNN)
#> Warning: pakke 'FNN' blev bygget under R version 4.0.4

# Generate data
distance <-
  tibble(
    location = c("first", "second", "third"),
    lat = c(33.720792, 33.715187, 33.714848),
    long = c(-84.468126, -84.468684, -84.454265)
  ) 

# Find KNN
knn <- distance %>% 
  select(lat,long) %>% 
  get.knn(k = nrow(.) - 1)

knn
#> $nn.index
#>      [,1] [,2]
#> [1,]    2    3
#> [2,]    1    3
#> [3,]    2    1
#> 
#> $nn.dist
#>             [,1]       [,2]
#> [1,] 0.005632707 0.01508173
#> [2,] 0.005632707 0.01442298
#> [3,] 0.014422985 0.01508173

# Identify locations
loc <- knn$nn.index
loc[] <- distance$location[loc]
colnames(loc) <- paste0("neighbour_",1:ncol(loc))

loc
#>      neighbour_1 neighbour_2
#> [1,] "second"    "third"    
#> [2,] "first"     "third"    
#> [3,] "second"    "first"

# final data
distance %>% 
  select(location) %>% 
  bind_cols(loc %>% as_tibble())
#> # A tibble: 3 x 3
#>   location neighbour_1 neighbour_2
#>   <chr>    <chr>       <chr>      
#> 1 first    second      third      
#> 2 second   first       third      
#> 3 third    second      first

^{Created on 2021-03-25 by the reprex package (v0.3.0)}