How to compute nearest distance between points?

Question

This is a tmp set of points with (x, y) coordinates and 0 or 1 categories.

tmp <- structure(list(cx = c(146.60916, 140.31737, 145.92917, 167.57799, 
166.77618, 137.64381, 172.12157, 175.32881, 175.06154, 135.50566, 
177.46696, 148.06731), cy = c(186.29814, 180.55231, 210.6084, 
210.34111, 185.48505, 218.89375, 219.69554, 180.67421, 188.15775, 
209.27205, 209.27203, 178.00151), category = c(1, 0, 1, 1, 1, 
0, 0, 0, 0, 0, 0, 0)), class = "data.frame", row.names = c(NA, 
-12L))

I need to find the minimum spanning tree for category = 1 points, then to join (add edge) each point with category = 0 to its nearest category = 1 point.

The minimum spanning tree is built on points with the category = 1.

ones    <- tmp[tmp$category == 1,]       
n       <- dim(ones)[1]    

d       <- matrix(0, n, n) 
d       <- as.matrix(dist(cbind(ones$cx, ones$cy)))

g1        <- graph.adjacency(d, weighted=TRUE, mode="undirected")
V(g1)$name <- tmp[tmp$category == 1,]$Name
mylayout = as.matrix(cbind(ones$cx, -ones$cy))

mst <- minimum.spanning.tree(g1) # Find a minimum spanning tree

plot(mst, layout=mylayout, 
         vertex.size      = 10,
         vertex.label     = V(g1)$name,
         vertex.label.cex =.75, 
         edge.label.cex  = .7,
)

Expected result is in center of figure.

My current attempt is:

n       <- dim(tmp)[1]    
d       <- matrix(0, n, n) 
d       <- as.matrix(dist(cbind(tmp$cx, tmp$cy)))


d[tmp$category %*% t(tmp$category) == 1] = Inf
d[!sweep(d, 2, apply(d, 2, min), `==`)] <- 0


g2        <- graph.adjacency(d, weighted=TRUE, mode="undirected")
mylayout = as.matrix(cbind(tmp$cx, -tmp$cy))
V(g2)$name <- tmp$Name

plot(g2, layout=mylayout, 
         vertex.size      = 10,
         vertex.label     = V(g2)$name,
         vertex.label.cex =.75,
         edge.label       = round(E(g2)$weight, 3), 
         edge.label.cex  = .7,
)

One can see that I have found the minimum dist and add one edge only.

Question. How to define condition for all possible points?

user_12158757 · Answer

You can try the code below

# two categories of point data frames
pts1 <- subset(tmp, category == 1)
pts0 <- subset(tmp, category == 0)

# generate minimum spanning tree `gmst`
gmst <- mst(graph_from_adjacency_matrix(as.matrix(dist(pts1[1:2])), mode = "undirected", weighted = TRUE))

# distance matrix between `pts0` and `pts1`
pts0_pts1 <- as.matrix(dist(tmp[1:2]))[row.names(pts0), row.names(pts1)]

# minimum distances of `pts0` to `pts1`
idx <- max.col(-pts0_pts1)
df0 <- data.frame(
  from = row.names(pts0),
  to = row.names(pts1)[idx],
  weight = pts0_pts1[cbind(1:nrow(pts0), idx)]
)

# aggregate edges lists and produce final result
g <- graph_from_data_frame(rbind(get.data.frame(gmst), df0), directed = FALSE) %>%
  set_vertex_attr(name = "color", value = names(V(.)) %in% names(V(gmst)))

mylayout <- as.matrix(tmp[names(V(g)), 1:2]) %*% diag(c(1, -1))
plot(g, edge.label = round(E(g)$weight, 1), layout = mylayout)

and you will get

How to compute nearest distance between points?

1 Answers