r - 在二维窗口中有效搜索

Question

考虑一个矩阵，该矩阵指定每条线一个二维区域，另一个矩阵指定一个平面中的点:

xmin <- c(3, 14, 25, 61)
xmax <- c(5, 18, 27, 65)
ymin <- c(33, 12, 83, 2)
ymax <- c(35, 16, 90, 6)
regions <- cbind(xmin, xmax, ymin, ymax)

x <- c(7, 26, 4, 16)
y <- c(4, 85, 30, 13)
points <- cbind(x, y)

在 regions中获取包含 points中每个点的索引的最快方法是什么？

我要实现的一个示例是:

apply(points, 1, function(x){
    which(regions[,'xmin'] < x[1] & regions[,'xmax'] > x[1] & regions[,'ymin'] < x[2] & regions[,'ymax'] > x[2])
})

但是随着 regions和 points中的行数都接近1E5，这变得相当慢，我正在寻找一种适当的矢量化方法...

提前致谢...

最好的
汤玛士

编辑:

对于任何有兴趣的人，我都使用Rcpp在C++中编写了一个函数，该函数可将性能提高大约50倍。我不太精通C++，所以可能做得更好...

cppFunction('
    IntegerVector findInRegion(NumericVector x, NumericVector y, NumericVector xmin, NumericVector xmax, NumericVector ymin, NumericVector ymax){
        int pointSize = x.size();
        int regionSize = xmin.size();
        IntegerVector ans(pointSize);
        for(int i = 0; i < pointSize; i++){
            ans[i] = NA_INTEGER;
        }

        for(int i = 0; i < pointSize; i++){
            for(int j = 0; j < regionSize; j++){
                if(x[i] > xmin[j]){
                    if(x[i] < xmax[j]){
                        if(y[i] > ymin[j]){
                            if(y[i] < ymax[j]){
                                ans[i] = j+1;
                            };
                        };
                    };
                };
            };
        };
        return ans;
    }
')

findRegion <- function(points, regions){
    if(!all(c('x', 'y') %in% colnames(points))){
        stop('points must contain columns named \'x\' and \'y\'')
    }
    if(!all(c('xmin', 'xmax', 'ymin', 'ymax') %in% colnames(regions))){
        stop('regions must contain columns named \'xmin\', \'xmax\', \'ymin\' and \'ymax\'')
    }
    findInRegion(points[, 'x'], points[,'y'], regions[, 'xmin'], regions[, 'xmax'], regions[, 'ymin'], regions[, 'ymax'])
}

此功能的一个缺点是它假定一个点只能属于一个区域。

Answer 1

这是另一种解决方案，将R-tree索引(一种用于存储边界框的数据库索引)与SQLite一起使用。
事实证明，它比Simon的速度(7秒)稍慢，可能是因为数据已复制到磁盘上。

# Sample data: data.frames, rather than matrices
regions <- data.frame(id=1:length(xmin), xmin, xmax, ymin, ymax)
points  <- data.frame(x, y)

library(RSQLite)
con <- dbConnect("SQLite", dbname = "/tmp/a.sqlite") 
dbGetQuery( con, "CREATE VIRTUAL TABLE regions USING rtree (id, xmin, xmax, ymin, ymax)" )
dbWriteTable( con, "regions", regions, row.names = FALSE, append = TRUE )
dbWriteTable( con, "points",  points, row.names = TRUE )
res <- dbGetQuery( con, "
  SELECT points.row_names, regions.id
  FROM   points, regions
  WHERE  xmin <= x AND x <= xmax
  AND    ymin <= y AND y <= ymax
" )