find_ordered_nn {GpGp}

Find ordered nearest neighbors.

Description

Given a matrix of locations, find the m nearest neighbors to each location, subject to the neighbors coming previously in the ordering. The algorithm uses the kdtree algorithm in the FNN package, adapted to the setting where the nearest neighbors must come from previous in the ordering.

Usage

find_ordered_nn(locs, m, lonlat = FALSE, st_scale = NULL)

Arguments

locs

A matrix of locations. Each row of locs contains a location, which can be a point in Euclidean space R^d, a point in space-time R^d x T, a longitude and latitude (in degrees) giving a point on the sphere, or a longitude, latitude, and time giving a point in the sphere-time domain.

m

Number of neighbors to return

lonlat

TRUE/FALSE whether locations are longitudes and latitudes.

st_scale

factor by which to scale the spatial and temporal coordinates for distance calculations. The function assumes that the last column of the locations is the temporal dimension, and the rest of the columns are spatial dimensions. The spatial dimensions are divided by st_scale[1], and the temporal dimension is divided by st_scale[2], before distances are calculated. If st_scale is NULL, no scaling is used. We recommend setting st_scale manually so that each observation gets neighbors that hail multiple directions in space and time.

Value

An matrix containing the indices of the neighbors. Row i of the returned matrix contains the indices of the nearest m locations to the i'th location. Indices are ordered within a row to be increasing in distance. By convention, we consider a location to neighbor itself, so the first entry of row i is i, the second entry is the index of the nearest location, and so on. Because each location neighbors itself, the returned matrix has m+1 columns.

Examples

locs <- as.matrix( expand.grid( (1:40)/40, (1:40)/40 ) )     
ord <- order_maxmin(locs)        # calculate an ordering
locsord <- locs[ord,]            # reorder locations
m <- 20
NNarray <- find_ordered_nn(locsord,20)  # find ordered nearest 20 neighbors
ind <- 100
# plot all locations in gray, first ind locations in black,
# ind location with magenta circle, m neighhbors with blue circle
plot( locs[,1], locs[,2], pch = 16, col = "gray" )
points( locsord[1:ind,1], locsord[1:ind,2], pch = 16 )
points( locsord[ind,1], locsord[ind,2], col = "magenta", cex = 1.5 )
points( locsord[NNarray[ind,2:(m+1)],1], 
    locsord[NNarray[ind,2:(m+1)],2], col = "blue", cex = 1.5 )