Strategy to find sets of neighbouring points

Question

Having a set of 3D coordinates of points I would like to find "chains" of points that are closer than a certain distance.

To give you a visual example, this R code generates the following image, where points closer than 10 units are connected by a red line.

set.seed(12345)

num.points <- 150

pts <- data.frame(PosX = runif(num.points, 0, 100),
                  PosY = runif(num.points, 0, 100),
                  PosZ = runif(num.points, 0, 50))

plot(pts$PosX, pts$PosY, pch = 20, cex = 2, xlab = "X", ylab = "Y", bty = "n", las = 1)

d <- as.matrix(dist(pts))

neighbour <- matrix(d<10, ncol = ncol(d))

for(r in 2:nrow(neighbour))
  for(c in 1:(r-1))
  {
    if (neighbour[r,c] == T)
    {
      segments(pts$PosX[r], pts$PosY[r], 
               pts$PosX[c], pts$PosY[c],
               col = "red", lwd = 2)
    }
  }

I would like to identify the sets of points that are connected together, either directly or through other points.

I am trying to figure out something that does not rely on slow for loops but I can't seem to find an obvious solution, so any idea would be appreciated.

Strategy to find sets of neighbouring points

0 Answers