Repository files navigation

This package is an updated version of theRANNpackage, making use of the Rcpp package.For basic use, there is little difference with original RANNpackage although there are some small (typically 5-10%) speedups for certainquery/target size combinations.RANN2 also includes experimentalfunctionality viaWANN objects to:

• keep ANN points in memory to avoid repeated copying
• keep the ANN k-d tree in memory to avoid repeated building
• separate building the k-d tree from allocating the points
• permit very fast self queries
• permit queries of the points from one ANN tree against a second tree

Currently there isn't a released version onCRAN,although we are considering a submission when the package develops sufficientlydistinct functionality from the original RANN package.

You can use thedevtools package to install the development version:

if (!require("devtools")) install.packages("devtools")devtools::install_github("jefferis/RANN2")

Note: Windows users needRtools anddevtools to install this way.

The expectation is that for 90% of users thenn2 function should be the onlyway that the library is used. This takes a target matrix of R points, copies them intoan array used by ANN and builds a k-d tree. It then iterates over the querypoints, searching the tree one at a time.

RANN2 addsWANN objects, which allow fine control of when the k-d tree isbuilt and removed.

data(kcpoints)w1=WANN(kcpoints[[1]])library(microbenchmark)microbenchmark(w1sq<-w1$selfQuery(k=1,eps=0))microbenchmark(nn2(kcpoints[[1]],k=1))w2=WANN(kcpoints[[2]])# NB must pass the Cpp object not the reference class objectw1$queryWANN(w2$.CppObject)

WANN objects will primarily be useful if you make repeated queries. You can alsodelay building the k-d tree:

w1=WANN(kcpoints[[1]])w1$querySelf(k=1,eps=0)w1$build_tree()w1$delete_tree()

if only a fraction of the objects will need to be searched; the tree willautomatically be built when it is queried. You can also explicitly controlwhen the tree is built or deleted (for memory management). The tree is wrappedin an R reference class (R5) object which imposes a significant performancepenalty for building small trees (< ~ 1000 points).

By default ANN usesdoubles for both points and returned distances. You cansave space by changing this if you want. To do to this you must recompile aftersetting eitherANN_COORD_TYPE orANN_DIST_TYPE insrc/MAKEVARS orMAKEVARS.win as appropriate. e.g.

PKG_CPPFLAGS=-I. -IANN -DRANN -DANN_COORD_TYPE=float

would switch to the use of floats for the main ANN coordinate type. Note howeverthat the k-d tree itself appears to occupy ~ 2x the space of the underlyingdouble coordinates.

This package compiles a static library for ANN and provides the headers for it.Developers can directly include them in their C++ code / Rcpp based package.

DESCRIPTION file:

    LinkingTo: RANN2

src/Makevars file:

    PKG_IMPORT=RANN2    PKG_HOME=`${R_HOME}/bin/Rscript -e'cat(system.file(package=\"$(PKG_IMPORT)\"))'`    PKG_LIBS=-L$(PKG_HOME)/lib -l$(PKG_IMPORT)

src/Makevars.win file:

    PKG_IMPORT=RANN2    PKG_HOME=`${R_HOME}/bin/Rscript -e'cat(system.file(package=\"$(PKG_IMPORT)\"))'`    PKG_LIBS+=-L$(PKG_HOME)/lib -l$(PKG_IMPORT)    PKG_CPPFLAGS+=-DDLL_EXPORTS

YourC++ file:

#include<ANN.h>

For usage example:src/nn.cpp