Indexes the bounding box of each geometry so that queries can skip the rows that cannot match.
Details
The tree is a packed Hilbert R-tree, the same structure FlatGeobuf stores on disk. You build it once and it is immutable, so it pays off when you query a set of geometries repeatedly.
Every query is a bounding box test, not an exact one. Two geometries whose
boxes overlap need not themselves intersect, so treat results as candidates
and confirm with ga_intersects() when exactness matters. You narrow to
candidates first so you can run the exact test on a handful of rows rather
than all of them.
Rows with a null or empty geometry have no bounding box, so new() leaves
them out of the tree and a query never returns them. Row numbers always
refer to positions in the original array.
write() saves the index to a file and RTree$read() opens it again, so
you build it once and reuse it across sessions. With mmap = TRUE,
read() maps the file instead of reading it, so the index opens at once
and each query loads only the parts of the tree it visits.
Methods
Method new
Build the index. Use node_size to set how many entries share a tree
node; with larger values you build faster and query slower. Use sort
to pick the packing order, either "hilbert" or "str".
Method read
Read an index that write() saved
Arguments
paththe file
write()savedmmapwhether to map the file rather than read it into memory
Method write
Save the index to a file
details
write() saves the tree with the row each entry came from, so
RTree$read() restores an index that answers every query the same
way. The tree keeps the layout of the JavaScript flatbush library.
Method search
Which rows have a bounding box overlapping each geometry
Returns one list of candidate row numbers per element of geometry,
row for row with the query array. This is the shape a spatial join
needs.
details
search() accepts anything with a bounding box: a point array, a
polygon array, or the box array ga_envelope() produces. It takes boxes
as they are and reduces everything else to its envelope first.
This is a bounding box test, not an exact one, so each list holds
candidates to confirm with ga_intersects() or another predicate.
search() returns a null rather than an empty list for a null or empty
query geometry.
Method neighbors
Which rows are nearest each geometry, closest first
Arguments
geometrya GeoArrow array to look up
kthe most rows to return per query, or
NULLfor no limitmax_distancethe furthest to search, or
NULLfor no limit
details
neighbors() measures distance from the centre of each query geometry
to the bounding box of the indexed one, so it returns candidates to
confirm with ga_dist_euclidean_pairwise() when exactness matters. Use
k to cap how many rows it returns per row and max_distance to cap
how far it searches.
Because neighbors() takes an array rather than one point at a time,
you can do a nearest neighbour join in one call.
Examples
nc <- as.data.frame(read_shapefile(
system.file("shape/nc.shp", package = "sf")
))
idx <- RTree$new(nc$geometry)
# candidate rows whose box meets each county, still to confirm exactly
head(as.vector(idx$search(nc$geometry)), 3)
#> <list_of<double>[3]>
#> [[1]]
#> [1] 1 2 18 19 22
#>
#> [[2]]
#> [1] 1 2 3 18
#>
#> [[3]]
#> [1] 2 3 10 18 23 25
#>
# the three counties nearest each centroid
head(as.vector(idx$neighbors(ga_centroid(nc$geometry), k = 3)), 3)
#> <list_of<double>[3]>
#> [[1]]
#> [1] 1 18 19
#>
#> [[2]]
#> [1] 2 18 1
#>
#> [[3]]
#> [1] 3 23 18
#>
# save the index and open it again without reading the whole file
path <- tempfile(fileext = ".gaix")
idx$write(path)
#> NULL
saved <- RTree$read(path, mmap = TRUE)
head(as.vector(saved$search(nc$geometry)), 3)
#> <list_of<double>[3]>
#> [[1]]
#> [1] 1 2 18 19 22
#>
#> [[2]]
#> [1] 1 2 3 18
#>
#> [[3]]
#> [1] 2 3 10 18 23 25
#>