Как набрать точки, находящиеся на определенном расстоянии от R?

Question

У меня есть пространство параметров, заданное (x, y) с x значениями от 1:5 и y значениями от 1:8. Скажем, мой текущий пункт p находится по адресу (2,5) (он окрашен в красный цвет). Моя цель - попытаться вытащить все точки в пределах одного расстояния от точки p (точки в синем).

Мне было интересно, был ли эффективный способ сделать это. Скажем, мои переменные хранятся следующим образом:

xrange <- 1:5 
yrange <- 1:8 
grid <- expand.grid(xrange,yrange) 
p <- data.frame(x=2,y=5) 

Я хотел бы сохранить другие пункты ниже p таким образом:

res <- data.frame(x=c(1,1,1,2,2,3,3,3),y=c(4,6,4,5,6,4,5,6)) 
res <- rbind(p,res) 
> res 
    x y 
1 2 5 
2 1 4 
3 1 6 
4 1 4 
5 2 5 
6 2 6 
7 3 4 
8 3 5 
9 3 6 

Конечная цель состоит в том, чтобы иметь пространство параметров, которое более 2-х мерных. Поэтому в конечном итоге мне бы хотелось найти все точки, которые имеют некоторое эвклидовое расстояние s, и аналогичным образом получить результирующий фреймворк с каждым столбцом, являющимся параметром в пространстве параметров, и каждая строка является точкой с координатами (x,y,z,..,etc) из ее столбцов.

EDIT Я попытался выполнить следующую реализацию, если мне нужен круг или эвклидовое расстояние s, и это похоже на работу. Я не уверен, насколько эффективным является решение.

eucdist <- function(z,p){ 

     return(dist(rbind(z, p))) 
    } 

# in this case s=1 since that is the <= condition 
res <- do.call(rbind,lapply(1:nrow(grid),function(m) if(eucdist(as.numeric(grid[m,]),as.numeric(p[1,])) <= 1){return(grid[m,])})) 

Дополнительная информация: на данный момент мое пространство параметров дискретизировано, как показано на рисунке выше. В конечном итоге некоторые параметры будут непрерывно смешиваться с дискретными параметрами. Спасибо огромное!

Answer 1

евклидово расстояние каждой точки на сетке от целевой точки p может быть эффективно вычислена с:

dist <- sqrt(rowSums(mapply(function(x,y) (x-y)^2, grid, p))) 

В основном внутренний mapply вызова приведет к матрице того же размера, как grid но есть квадрат расстояния этой точки от целевой точки в этом измерении; rowSums и sqrt эффективно вычислить эвклидовое расстояние.

В этом случае вы в том числе что-нибудь с sqrt(2) евклидово расстояние от точки цели:

grid[dist < 1.5,] 
# Var1 Var2 
# 16 1 4 
# 17 2 4 
# 18 3 4 
# 21 1 5 
# 22 2 5 
# 23 3 5 
# 26 1 6 
# 27 2 6 
# 28 3 6 

Использование mapply (работающего над размерами) и rowSums делает это гораздо эффективнее, чем подход, который перебирает индивидуальный точек на сетке, вычисляя расстояние до целевой точки. Чтобы убедиться в этом, рассмотрим несколько больший пример с 1000 случайно распределенных точек в трех измерениях:

set.seed(144) 
grid <- data.frame(x=rnorm(1000), y=rnorm(1000), z=rnorm(1000)) 
p <- data.frame(x=rnorm(1), y=rnorm(1), z=rnorm(1)) 
lim <- 1.5 
byrow <- function(grid, p, lim) grid[apply(grid, 1, function(x) sqrt(sum((x-p)^2))) < lim,] 
vectorized <- function(grid, p, lim) grid[sqrt(rowSums(mapply(function(x,y) (x-y)^2, grid, p))) < lim,] 
identical(byrow(grid, p, lim), vectorized(grid, p, lim)) 
[1] TRUE 
library(microbenchmark) 
# Unit: microseconds 
#      expr  min   lq  mean  median   uq  max neval 
#  byrow(grid, p, lim) 446792.71 473428.137 500680.0431 495824.7765 521185.093 579999.745 10 
# vectorized(grid, p, lim) 855.33 881.981 954.1773 907.3805 1081.658 1108.679 10 

векторизованных подход в 500 раз быстрее, чем подход, который петлями через ряды.

Этот подход может быть использован в тех случаях, когда у вас есть много больше очков (1 миллион в этом примере):

set.seed(144) 
grid <- data.frame(x=rnorm(1000000), y=rnorm(1000000), z=rnorm(1000000)) 
p <- data.frame(x=rnorm(1), y=rnorm(1), z=rnorm(1)) 
lim <- 1.5 
system.time(vectorized(grid, p, lim)) 
# user system elapsed 
# 3.466 0.136 3.632 

Answer 2

Вот как это сделать с пакетом FNN.Результат отличается от того, что у вас есть, потому что ваше решение имеет (1 4) и (2 5) два раза. Решение также работает с данными о границе. У вас будет только 6 ближайших соседей, если ваш x или y равен 1 или по краю вашей матрицы.

library(FNN) 
x <-2 
y <- 5 
pt <-grid[grid$Var1==x & grid$Var2==y ,] #target point 
distance <-knnx.dist(grid,pt,k=9) #distance from pt 
k <-length(distance[distance<2]) #distance is less than 2. Useful for border data 
nearest <-knnx.index(grid,pt,k=k) #find index of k nearest neighbors 

grid[nearest,] 

    Var1 Var2 
22 2 5 
23 3 5 
27 2 6 
21 1 5 
17 2 4 
26 1 6 
28 3 6 
18 3 4 
16 1 4 

Я вижу, что вы также запросили более высокие размеры. Он по-прежнему будет работать после следующих изменений:

x <-2 
y <- 5 
z <-3 
pt <-grid[grid$Var1==x & grid$Var2==y & grid$Var3==z ,] #3-dimensional point 
distance <-knnx.dist(grid,pt,k=27) #increase to k=27 
k <-length(distance[distance<2]) 
nearest <-knnx.index(grid,pt,k=k) 
grid[nearest,]