Search strategy for sets of neighboring points

Given a set of 3D point coordinates, 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 in which 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)
    }
  }

      

approximate schedule

I would like to identify sets of points that are related to each other, either directly or through other points.

I'm trying to figure out what doesn't rely on slow loops for

, but I can't seem to find an obvious solution, so any idea would be appreciated.

+3


source to share





All Articles