[R-sig-Geo] Nearest neighbor for two spatial datasets

[Roger Bivand]

On Thu, 25 Apr 2013, Kirill Müller wrote:

> Hello
>
> I am looking for a fast implementation for finding, for each object in 
> dataset A, the closest object of dataset B. A naive approach using gDistance 
> et al. considers each pair AxB, but this can be improved by using a spatial 
> index in B.
>
> Is there such an implementation for R?

Please see ?gBinarySTRtreeQuery in rgeos, but note that at present the 
query only returns intersecting envelopes (bounding boxes) for sets of 
objects, so is not exactly the kond of tree you are thinking of.

Since you mention gDistance, the geometries are planar, in which case 
querying using RANN for distances between points may hep; RANN is an 
interfacing of ANN (approximate nearest neighbour) for R. RANN builds a 
tree internally then queries on that tree. Better tree handling could be 
implemented in rgeos too if that route would make sense, but STRtreeQuery 
in GEOS is limited to overlapping envelopes:

http://geos.osgeo.org/doxygen/classgeos_1_1index_1_1strtree_1_1STRtree.html

So rgeos STRTrees only tell you if non-point objects have overlapping 
envelopes (only polygons and lines, not much help for distance), RANN kan 
handle large numbers of points, but no polygons or lines. You could look 
at libspatialindex, which hasn't been interfaced to R, to see if it 
permits distance queries rather than overlapping rectangular range 
queries.

Hope this helps,

Roger

>
> See also this question on StackOverflow: 
> http://stackoverflow.com/questions/15992158/spatial-matching-of-big-datasets
>
>
> Cheers
>
> Kirill
>
> _______________________________________________
> R-sig-Geo mailing list
> R-sig-Geo at r-project.org
> https://stat.ethz.ch/mailman/listinfo/r-sig-geo
>

-- 
Roger Bivand
Department of Economics, NHH Norwegian School of Economics,
Helleveien 30, N-5045 Bergen, Norway.
voice: +47 55 95 93 55; fax +47 55 95 95 43
e-mail: Roger.Bivand at nhh.no