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

Question

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

3

这是一组带有(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))

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

最小生成树是在具有分类为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,
)

可以看出，我已经找到了最小的距离，并且只添加了一条边。

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

- Nick

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- ThomasIsCoding · Accepted Answer

您可以尝试以下代码。

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

你将获得: