Finding the point in a cloud of points with the most neighbors

General
#1

Dear community,

I'm looking for a fast way to find the point with the most neighbors in a cloud of points within a given search radius.

I.e. is there a function that would be able to find the red point in the example below:

df <- crossing(x = seq(-1,1, length.out = 25), y = seq(-1,1, length.out = 25)) %>%
  filter(sqrt(x^2 + y^2) <= 0.9) %>% 
  filter(sqrt((x+0.3)^2 + y^2) >= 0.4)

df %>% 
  ggplot(aes(x = x, y = y))+
  geom_point(alpha = 0.5)+
  geom_point(x = .5, y = 0, size = 60, shape = 1, colour = 'red')+
  geom_point(x = .5, y = 0, colour = 'red')

And could this function generalize to N-dimensional cases?

Any help would be appreaciated.

Thanks

/Jannik

#2

The best approach to these types of questions are with a spatial tree structure such as a Quad Tree. The QuadTree package provides access to a C implementation of this. While it doesn’t provide circular lookup it does provide a rectangular lookup which you can use to filter down the number of candidates. I would expect that this type of functionality is also present in sf or some of its related packages but I’m not sure. If it is it is likely to be more performant