0

I am using R-Studio and I have a dataframe where I have points for x,y. I want to find the next nearest point when I chose a x0, y0. Then when I have x1, y1, I want to use these as x0, y0 and find the next nearest point which would be x2, y2.

The answer in this question helped: Find the nearest X,Y coordinate using R But now I need help with the second part in updating x0, y0. until it goes through all my data.

SecretAgentMan
  • 2,856
  • 7
  • 21
  • 41
Ramona Luna
  • 1
  • What happens when the closest to point `m` is point `n`, and then the closest to point `n` is `m`? Have you looked at `dist`? – r2evans Oct 07 '20 at 04:52
  • You can run the command `dput(YOURDATA)` and paste the output into your question. If you do this, other people will be able to work with your data and ask better-informed questions to help you. – BrianLang Oct 07 '20 at 06:47

2 Answers2

2

here is an solution, approaching your question as a travelling salesperson problem...

sample data

mydata <- data.frame( id = letters[1:4],
                      x = c(1,10,2,5),
                      y = c(1,10,4,6) )

#what does it look like?
library(ggplot2)
ggplot( mydata, aes( x = x, y = y, label = id)) + geom_point() + geom_text( vjust = -1 )

enter image description here

code

#introducing the Travelling SalesPerson
#   install.packages("TSP")
library( TSP )

#calculate distances
d <- dist( mydata[-1] )
#create TSP model...
tsp <- TSP( d, labels = mydata$id )
#...and solve it. start on first point, using nearest neighbour
tsp_solved <- solve_TSP( tsp, method = "nn", start = 1 )
#so.. what do we travel like?
labels( tsp_solved )
#[1] "a" "c" "d" "b"
Wimpel
  • 26,031
  • 1
  • 20
  • 37
0

Here is an example that takes a list of coordinates, then calculates the euclidean distance between each pair of points, then creates a path through the points of length steps while never visiting the same point twice.

library(tidyverse)

set.seed(1234)

distance_table <- tibble(id = 1:100, x = runif(0,100,n = 100), y = runif(0,100,n=100)) %>%
 (function(X)expand_grid(X, X %>% setNames(c("id_2", "x2","y2"))))  %>%
 filter(id != id_2) %>%
 mutate(euc_dist = sqrt((x - x2)^2 +(y-y2)^2))


steps = 25
starting_id = sample(1:100, 1)
results_holder = tibble(order = 1:steps, location_id = numeric(steps), x = numeric(steps), y = numeric(steps))
results_holder$location_id[1] <- starting_id
results_holder$x[1] <- unique(distance_table$x[distance_table$id == starting_id])
results_holder$y[1] <- unique(distance_table$y[distance_table$id == starting_id])

for(i in 2:steps){
 data_tmp <- distance_table %>% 
  filter(results_holder$location_id[i - 1] == id) %>% 
  filter(!(id_2 %in% results_holder$location_id)) %>%
  filter(euc_dist == min(euc_dist))
 results_holder$location_id[i] <- data_tmp$id_2[1]
 results_holder$x[i] <- data_tmp$x2[1]
 results_holder$y[i] <- data_tmp$y2[1]
}

results_holder

ggplot(distance_table %>% filter(!(id %in% results_holder$location_id)), aes(x, y)) +
 geom_point() + 
 geom_label(data = results_holder, aes(label = order), size = 2)

the plotted route

BrianLang
  • 831
  • 4
  • 14