对 R 中的点矩阵进行排序以获得用于在 x-y 图上绘制直线的顺序向量

Question

我有一个凸包的点列表，作为矩阵，如下所示：

      [,1] [,2]
 [1,]   23   18
 [2,]    7    1
 [3,]   14   18
 [4,]   24    1
 [5,]   24   23
 [6,]   10   11
 [7,]   13   14
 [8,]    9    7
 [9,]    9   10
[10,]   12   11
[11,]   12   13

我还有这些点的 x-y 坐标列表（UPD：船体中的每个整数对应于 x 和 y 索引）。现在我想用一个 lines() 调用来绘制凸包。我如何 'unwind' 点矩阵，使其看起来像这样：c(23, 18, 14, 13, 12, 11, 10, 9, 7, 1, 24)?

Answer 1

您想要从顶点 1 开始的图形路径吗？包 igraph 可以做到这一点。

library(igraph)

g <- graph_from_data_frame(mat)
p <- all_simple_paths(g, from = V(g)[1], mode = "all")

下面给出列表p中所有路径的长度。我们正在寻找最长的。

lengths(p)
#[1]  2  3  4  5  6  7  8  9 10 11  2  3  4  5  6  7  8  9 10 11

从上面的长度可以看出，它们是相同的路径，但起始顶点不同，最长的是列表的最后一个和中间的那个p。

p[[length(p)/2]]
#+ 11/11 vertices, named, from 0bc39f7:
# [1] 23 24 1  7  9  10 11 12 13 14 18
p[[length(p)]]
#+ 11/11 vertices, named, from 0bc39f7:
# [1] 23 18 14 13 12 11 10 9  7  1  24

数据

x <- textConnection('
23   18
7    1
14   18
24    1
24   23
10   11
13   14
9    7
9   10
12   11
12   13
')
mat <- read.table(x)
close(x)

Answer 2

UPD：这是我想出的（正确的）解决方案：

require(data.table)
find.nodes <- function(nodes) {
  exit.nodes <- which(duplicated(nodes[,1]))
  nodes <- cbind(nodes[exit.nodes, ncol(nodes):1], nodes[exit.nodes-1])
  setorder(nodes)
  return(nodes)
}
nodes <- rbind(hull, hull[, 2:1], use.names=FALSE)
setorder(nodes)
nodes <- find.nodes(nodes)
while (nrow(nodes) > 2) {
  nodes <- find.nodes(nodes)
}
nodes <- nodes[1,]
nodes <- unique(as.integer(nodes))
nodes <- c(nodes, nodes[1])
nodes

Unit: milliseconds
               expr      min       lq      mean   median       uq     max neval
   igraph.fun(hull) 0.875800 0.910251 0.9785159 0.921701 0.952600 97.3383 10000
 setnodes.fun(hull) 1.931201 1.989401 2.1007707 2.011601 2.054401 23.4761 10000

它比 igraph 解决方案慢。
顺便说一句，igraph::convex.hull$resverts 似乎输出了一些奇怪的结果。

对 R 中的点矩阵进行排序以获得用于在 x-y 图上绘制直线的顺序向量

Sort matrix of points in R to get a sequential vector for plotting the line on x-y plot

r

matrix

plot

line

convex-hull