0

Currently, I am conducting spatial analysis in R over a taxi data set. The data set gives lat-long coordinate pairs to denote where someone was picked up and dropped off, and I am also working with a road network with clearly defined street intersection nodes. I am looking for a way to find the nearest street intersection when given a certain pair of coordinates in the reference system:

nearestNeighborID <- someFunction(myNetwork, xCoordinate, yCoordinate)

I believe there may be such a function in R's sp or igraph packages, but I haven't been able to find anything yet: only a gdistance function which computes the distance between two given points. Does anybody know of such a function in R where you may find the nearest vertex/feature in a network when given an xy point in space?

Also, here is an example of my network and some pickup/dropoff locations. I apologize that it is a bit messy, but the fairly organized square is the street network, and the strewn-across points are the locations that I wish to approximate to the nearest street intersection (an example is the bottom right point with the blurry ID number): https://i.stack.imgur.com/qeKEf.jpg.

Anthony Niemiec
  • 37
  • 3
  • Please create a reproducible example with data and expected output: http://stackoverflow.com/questions/5963269/how-to-make-a-great-r-reproducible-example – emilliman5 Feb 20 '18 at 15:27
  • This sounds more like a GIS problem than a graph problem. – emilliman5 Feb 20 '18 at 16:38
  • @emilliman5 There is no reproducible example, because it is the example itself which I am seeking. If I were able to reproduce an example of finding a nearest vertex given two coordinates, wouldn't my problem be solved? My question is generalized to any xy coordinate data, and I have stated the form of the function I am seeking (along with its expected behavior). – Anthony Niemiec Feb 20 '18 at 20:31
  • A reproducible example does not necessarily mean that your problem has already been solved. A reproducible example means that you provide a sample of the data you are working with and any code you have written to try to solve the problem yourself. What do the edges represent, how are the interesection's locations represented? Why are the taxis in the same network as the intersections? What do their edges represent? Are you working with longitude and latitude or some other coordinate system? Please read the link I posted in my first comment as it provides valuable information. – emilliman5 Feb 20 '18 at 21:02

2 Answers2

0

This does not appear to be a graph problem but a simple distance problem.

Step1: convert your graph to an x,y dataframe of each intersection. Since we do not know how location data for the intersections and taxis is represented in the graph I cannot provide any code.

Step2: 

require(proxy)
##creating some example data 100 intersections and 10 taxis
road <- data.frame(Intersection=sapply(1:100, function(x) paste(sample(x= LETTERS, size=10, replace=T), collapse = "")),
                   lat=runif(100, 0, 360), lon=runif(100, 0, 360))
taxis <- data.frame(ID=1:10,
                    lat=runif(10, 0, 360), 
                    lon=runif(10, 0, 360))

#Calculate the distance between each taxi and every intersection using euclidean distance
taxiDist <- proxy::dist(road[, -1], taxis[, -1])
#Find the index for closest intersection for each taxi
idx <- apply(taxiDist, 2, which.min)
#Retrieve the intersection data
road[idx, ]

# Intersection       lat       lon
# 24     DUCHJURDLJ 164.09897 260.50476
# 21     EXRQAWKCKQ 202.20218 178.14160
# 38     NQSTQUXZUF 341.12904   7.55647
# 3      MDTSSWSFVR  62.83737 118.75232
# 38.1   NQSTQUXZUF 341.12904   7.55647
# 24.1   DUCHJURDLJ 164.09897 260.50476
# 40     PEQOUTLIBR 357.45814 155.44159
# 60     TVJOCWZULB 342.14584 234.12673
# 28     MBQQVURJXR 111.19420 215.96506
# 98     FVRXXXJZTO 129.10932 321.22990
emilliman5
  • 5,816
  • 3
  • 27
  • 37
  • >Since we do not know how location data for the intersections and taxis is represented in the graph I cannot provide any code. Though I did explicitly state that these are expressed in lat-long coord pairs, I was looking for a general example nevertheless. Also, wouldn't this be a very inefficient way of computing this problem, by calculating the distance between all other nodes and choosing the shortest? – Anthony Niemiec Feb 20 '18 at 21:20
  • This example is very general as it will take any coordinates (2,3, 4, 5, ..., k) and find the closest neighbor. As to efficiency, that depends on what you mean. This is not going to be very memory efficient but it is time efficient (matrix math is very fast)compared to some sort of loop (which would be more memory efficient). You haven't given any specifics on data size, or efficiency requirements so I provided the most straight-forward solution I could. I will reiterate that this is a geography(GIS) problem not a graph problem, I'm sure any number of GIS packages will have fancier methods – emilliman5 Feb 20 '18 at 21:44
  • Thanks for the tip on GIS packages, but that's really the only answer I seek; I'm not asking for actual code or even peusocode, just the name of a GIS package or a GIS package function that would carry out some "find nearest neighbor" algorithm; that's why I didn't include code or my original data, because I'm not actually looking for that sort of answer. Also, my mistake, I did mean computationally efficient as in big-Oh, thanks for clearing up both questions for people who might read this in the future. – Anthony Niemiec Feb 21 '18 at 02:38
0

R has a package named RANN which has a single function nn2: this function lets you pass in a matrix of points you wish to find a neighbor for, i.e. your observed Taxi lat-long pickup points, and a second matrix of points you with to find the neighbors in, i.e. your network's street intersections. You may even set a flag searchtype="radius" to search for neighbors up to a certain distance; otherwise, it is reported that no neighbors (or a number smaller than k neighbors) were found.

Thus, a line of code you may run may be: nearestNeighborIDs <- nn2(data=networkStreetIntersections, query=taxiPickupLocations, searchtype="radius", radius= ...). This returns a comprehensive listing of each Taxi pickup location and the street intersection it is closest to in the supplied street network.

RNN documentation and nn2 manual page:

https://cran.r-project.org/web/packages/RANN/index.html https://cran.r-project.org/web/packages/RANN/RANN.pdf

-- The below answer may be useful for future readers who wish to find the k nearest neighbors for ALL points in a SINGLE matrix:

In R's spdep package (package manual: https://cran.r-project.org/web/packages/spdep/spdep.pdf), there is a function named knearneigh. This function generates the k nearest neighbors to a point; if you set k=1, you will find the nearest point, which may be interpreted as a street intersection.

General usage: knearneigh(x, k=1, longlat = NULL, RANN=TRUE), where x is stated to be your matrix of point coordinates (or a SpatialPoints object, which may be created with the sp package) https://www.rdocumentation.org/packages/spdep/versions/0.7-4/topics/knearneigh

Anthony Niemiec
  • 37
  • 3