RapidPolygonLookup: Efficient spatial polygon search using kd-trees.

In RapidPolygonLookup: POLYGON LOOKUP USING KD TREES

Description

Given spatial partitions such as census blocks, ZIP codes or police district boundaries, we are frequently faced with the need to spatially aggregate data. Unless efficient data structures are used, this can be a daunting task. The operation point.in.polygon() from the package sp is computationally expensive. Here, we exploit kd-trees as efficient nearest neighbor search algorithm to dramatically reduce the effective number of polygons being searched. Points that are left unmapped are put through a linear search to find the associated polygon.

Usage

RapidPolygonLookup(XY, polygons, poly.list = NULL, k = 10, N = nrow(XY), 
    poly.id = "fips", poly.id.colname = "census.block", keep.data = TRUE, 
    verbose = 0)

Arguments

XY	data frame containing X-Y or (lon-lat, long-lat, longitude-latitude) columns
polygons	polygons to crop and add poly centres
poly.list	polygon list with three elements: data, polys, and poly.centers as output from function CropSpatialPolygonsDataFrame()
k	maximum number of near neighbours to compute. The default value is set to 10
N	number of rows of XY to search
poly.id	column name in 'poly.list$data' containing the polygon identifier
poly.id.colname	desired column name in the output data frame containing the polygon identifier
keep.data	retain polygon list and centers for future referece
verbose	level of verbosity

Value

The original points augmented with polygon ID are returned along with the poly centers and other call information

Author(s)

Markus Loecher <[e-mail]> and Madhav Kumar <[e-mail]>

Examples

data(sf.crime.2012, envir = environment())
data(sf.polys, envir = environment())
cat(nrow(sf.crime.2012), "rows in SF crime \n")

XY.kdtree <- RapidPolygonLookup(sf.crime.2012[,c("X","Y")], poly.list= sf.polys, 
                                  k= 10, N= 1000, 
                                  poly.id= "fips", poly.id.colname= "census.block", 
                                  keep.data= TRUE, verbose= TRUE)

XY.kdtree.DF <- XY.kdtree$XY
table(XY.kdtree.DF$rank, useNA= "always")
hist(XY.kdtree.DF$rank, xlab = "rank of neighbor")

RapidPolygonLookup documentation built on May 2, 2019, 7:08 a.m.