[R-sig-Geo] Nearest neighbor for two spatial datasets
Roger.Bivand at nhh.no
Thu Apr 25 14:47:39 CEST 2013
On Thu, 25 Apr 2013, Kirill Müller wrote:
> 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:
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
Hope this helps,
> See also this question on StackOverflow:
> R-sig-Geo mailing list
> R-sig-Geo at r-project.org
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
More information about the R-sig-Geo