3

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)
    }
  }

example plot

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.

nico
  • 50,859
  • 17
  • 87
  • 112
  • 1
    Maybe you should check out the dbscan clustering algorithm. It might get you where you want to go. There is a `dbscan` package implemented with `rcpp`: http://cran.mirrors.hoobly.com/web/packages/dbscan/index.html. – lmo Jul 21 '17 at 18:13
  • 2
    what about chucking it into igraph, and then using graph tools `g <- graph_from_adjacency_matrix(neighbour, mode="undirected", diag=FALSE)` [and then](https://stackoverflow.com/questions/30407769/get-connected-components-using-igraph-in-r) – user20650 Jul 21 '17 at 22:34
  • 1
    @lmo I did not think of dbscan, but that sounds like a very good idea! I'll try it when back to work on Monday! – nico Jul 22 '17 at 10:56
  • @user20650 I tried playing around with `igraph` in the past but not 100% sure how adjacency matrices are computed. I will need to read a bit about it! Thanks for the suggestion though – nico Jul 22 '17 at 10:56
  • @nico ; in this case your neighbour matrix is the adjacency matrix. To see the clusters pulls out the correct nodes plot the labels: `plot(pts$PosX, pts$PosY, type="n", cex = 2, xlab = "X", ylab = "Y", bty = "n", las = 1); text(pts$PosX, pts$PosY, label=1:num.points, cex=0.75)` . Then create graph: `g <- graph_from_adjacency_matrix(neighbour, mode="undirected", diag=FALSE)`. Then clusters `cl = components(g) ; lapply(seq_along(cl$csize)[cl$csize > 1], function(x) V(g)[cl$membership %in% x])` . This picks out the connected nodes (and matches the plot) – user20650 Jul 22 '17 at 12:05

0 Answers0