We are given a huge set of points in 2D plane. We need to find, for each point the closest point within the set. For instance suppose the initial set is as follows:
foo <- data.frame(x=c(1,2,4,4,10),y=c(1,2,4,4,10))
The output should be like this:
ClosesPair(foo)
2
1
4
3
3 # (could be 4 also)
Any idea?
Here is an example; all wrapped into a single function. You might want to split it a bit for optimization.
Of cause, it does not handle ties very well.
The traditional approach is to preprocess the data and put it in a data structure, often a K-d tree, for which the "nearest point" query is very fast.
There is an implementation in the
nnclust
package.Use the package
spatstat
. It's got builtin functions to do this sort of stuff.