如何计算点之间的最近距离？

Question

这是一个 tmp 点集，坐标为 (x, y)，类别为 0 或 1。

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

我需要找到 category = 1 点的最小生成树，然后将每个点与 category = 0 连接（添加边）到最近的 category = 1 点。

最小生成树建立在具有 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,
)

预期结果在图的中心。

我目前的尝试是：

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

可以看到我找到了最小距离，只加了一条边。

问题。如何为所有可能的点定义条件？

Answer 1

您可以试试下面的代码

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

你会得到

如何计算点之间的最近距离？

How to compute nearest distance between points?

r

matrix

igraph