如何在循环中使用convex_hull()函数？

Question

在我的previous question中，我使用了convex_hull()函数。我们有一个图，其中所有的节点都有零度和(x，y)坐标。我们需要创建图作为凸壳的序列。如果只有一个节点有零度，我们就可以停止循环。

我的尝试是：

library(igraph)
######################################################################
set.seed(5)
n=15
g  <- graph.empty(n)
xy <- cbind(runif(n), runif(n))
in_points <- V(g)[degree(g)==0]

repeat {
cp <- convex_hull(xy[in_points, ])$resverts+1

g <- as.undirected(add_edges(g, c(t(embed(cp, 2)), cp[1], cp[length(cp)])))

in_points <- V(g)[degree(g)==0]
if (length(in_points)=1) {break}
}

plot(g, vertex.size=10, layout=xy)

可以在重复循环中看到节点3使用了两次。

预期结果是：

​

​

问题：如何正确地使用convex_hull()函数的输出来在循环中连续添加边？

Answer 1

您可以迭代地使用chull和add_edges。您只需要确保输入到add_edges的格式是正确的，并跟踪哪些节点尚未成为外部凸壳的一部分。

xy <- cbind(seq_len(n), xy)

while(nrow(xy) > 1){
  current_hull <- chull(xy[,2], xy[,3])
  current_hull <- c(current_hull, current_hull[[1]])
  g <- add_edges(g, as.vector(t(embed(xy[,1][current_hull], 2)[,2:1])))
  xy <- xy[-current_hull,,drop = FALSE]
}