[R-sig-Geo] Parallel processing a list of SpatialPoints

[David Wang]

Hello,


I have a list of SpatialPointsDataFrame objects that represent feature centers along the time axis. For example, let's say the list is centers. centers[[1]] are the points at t = 1, centers[[2]] are the points at t = 2, and so on. Now for every point at t, I need to link it to, if any, the nearest point within a search radius at the next time step t + 1. The procedure is applied to all time steps, and the result are tracks that connect selected feature centers in time. I have implemented a solution using igraph package, with every center represented by a vertex and every link by an edge. This way, tracks are simply connected components of the graph. Now because the number of centers and links are quite large, the algorithm takes a while to run. But since finding the nearest neighbors between t and t + 1 and between t + 1 and t + 2 are independent, I think parallel processing should be possible, although I haven't figured out how. Does anyone here happen to have a pointer or two? I work on a multicore PC. Here is my code snippet:


g <- graph.empty(directed = TRUE)
for (k in seq_along(centers)) {
  pts <- centers[[k]]
  g <- add_vertices(g, nv = length(pts), id = k, attr = as.data.frame(pts))
  if (length(V(g)[id == (k - 1)]) > 0 & length(V(g)[id == k]) > 0) {
    v1 <- V(g)[id == (k - 1)]
    v2 <- V(g)[id == k]
    rd <- rdist(cbind(v1$x, v1$y), cbind(v2$x, v2$y))
    for (i in 1:nrow(rd)) {
      if (min(rd[i, ]) < maxDist) {
        e <- c(V(g)[id == (k - 1)][i], V(g)[id == k][which.min(rd[i, ])])
        g <- add_edges(g, e)
      }
    }
  }
}
tracks <- groups(components(g)) # vertex ids along each track


Thanks,

David

	[[alternative HTML version deleted]]