bbox experiments

[mdsumner]

From @mdsumner on February 7, 2017 4:28

I've been thinking similarly about the bounding box culls for st_intersect, is it worth having "feature-level bbox" as a fully fledged POLYGON sf used to pre-filter the combinations tested in full.

There is also scope for more general decomposition of objects for specialized optimizations (convex parts, triangles). I was working on benchmarks for this, which led to the motivation for #209. I think intersection is not improved by decomposition, but intersection-overlay definitely is.

library(sf)
example(st_read)
library(tibble)
npts <- 1e5
library(dplyr)
library(tibble)
pts <- st_as_sf(setNames(as_tibble(geosphere::randomCoordinates(npts)), c("x", "y")) %>% mutate(a = row_number()), 
                coords = c("x", "y"), crs = st_crs(nc))
#plot(st_geometry(pts), pch = ".")

tbox <- function(x) {
  as_tibble(do.call(rbind, lapply(st_geometry(x), st_bbox))) 
}

tbox(nc)

get_points <- function(x) {
  setNames(as_tibble(do.call(rbind, lapply(st_geometry(x), function(x) unclass(x)))), c("x_", "y_"))
}

prefilter_bbox <- function(x, y) {
  y_bb <- tbox(y) %>% mutate(y_id = row_number())
  
  xpoints <- get_points(x) ##sc::sc_coord(x)
  xpoints <- mutate(xpoints, x_id = as.character(row_number()))
  y_bb <- bind_rows(replicate(nrow(xpoints), y_bb, simplify = FALSE), .id = "x_id") 
  tab <- inner_join(xpoints, y_bb)
  tab %>% filter(x_ >= xmin, x_ <= xmax, y_ >= ymin, y_ <= ymax ) %>% 
    select(x_id, y_id) %>% mutate(x_id = as.integer(x_id))
}
tofilter <- prefilter_bbox(pts, nc)
st_intersects(pts[tofilter$x_id, ], nc[tofilter$y_id, ])

Copied from original issue: r-spatial/sfdct#10

[mdsumner]

see extents branch in spex https://github.com/mdsumner/spex/tree/extents