从自定义 txt 地图确定多边形坐标
Determine polygon coordinates from custom txt map
我有一个 .txt 文件，看起来像这样
+----------+--------+------------------+
| | \ |
| | \ |
| | \ |
| | +------+-------+
| | | |
| | | |
+----------+-------------------+-------+
如何识别这些多边形？
对于这个例子，我希望识别 4 个多边形。
我可以读取线条并识别每个顶点 ("+") 的坐标（行、列），但我不确定如何获取边坐标。我的主要目标是拥有一组描述每个多边形边界区域的点。
如何在 R 或 Python 中执行此操作？
我并不是说这非常有效，但这至少是解决 R 中问题的一种方法。首先，这是我读入数据的方式。
raw <- r"(
+----------+--------+------------------+
| | \ |
| | \ |
| | \ |
| | +------+-------+
| | | |
| | | |
+----------+-------------------+-------+
)"
data <- do.call("rbind", strsplit(readLines(textConnection(raw)), ""))
这将创建一个数组 data，其行数和列数与输入的所有字符都相同。
基本思路是我尝试填充该区域中的每个“空白”区域，并跟踪我们在填充过程中遇到的所有角。所以首先，一个辅助函数来获取给定单元格周围的 rows/columns
allnei <- expand.grid(-1:1, -1:1)
allnei <- allnei[allnei[,1] !=0 | allnei[,2] !=0, ]
get_neighbors <- function(point, data) {
cand <- t(c(point) +t(allnei))
cand[
cand[,1]>=1 & cand[,1]<=nrow(data) &
cand[,2]>=1 & cand[,2]<=ncol(data),
TRUE
]
}
然后大部分工作发生在 fill 函数
fill <- function(point, data, corners=matrix(nrow=0, ncol=2), fill_with="1") {
if (!is.matrix(point)) {
point <- matrix(point, ncol=2)
}
cand <- get_neighbors(point, data)
data[point] <- fill_with
corner_cand <- which(data[cand] == "+")
if (length(corner_cand)) {
corners <- unique(rbind(corners, cand[corner_cand, ]))
}
empty_cand <- which(data[cand] == " " & (cand[,1]==point[,1] | cand[,2]==point[,2]))
if (length(empty_cand)>0) {
for(i in empty_cand) {
result <- fill(cand[i,], data, corners, fill_with)
data <- result$data
corners <- unique(rbind(corners, result$corners))
}
}
list(data=data, corners=corners)
}
所以从一个“空”单元格开始，我们寻找相邻的单元格并将它们标记为同一区域。我们递归地执行此操作，直到我们 运行 超出相邻的空单元格。
现在我们需要一个包装器，它会一直这样做直到没有空白区域。
find_regions <- function(data) {
regions <- list()
reg <- 1
empty <- which(data==" ", arr.ind=TRUE)
while(nrow(empty)>0) {
empty <- empty[1,]
results <- fill(empty, data, fill_with=reg)
regions <- c(regions, list(results$corners))
data <- results$data
reg <- reg+1
empty <- which(data==" ", arr.ind=TRUE)
}
list(data=data, regions=regions)
}
result <- find_regions(data)
result$regions
给出输出
[1]]
Var1 Var2
[1,] 1 1
[2,] 8 1
[3,] 8 12
[4,] 1 12
[[2]]
Var1 Var2
[1,] 1 12
[2,] 8 12
[3,] 1 21
[4,] 5 25
[5,] 5 32
[6,] 8 32
[[3]]
Var1 Var2
[1,] 5 25
[2,] 5 32
[3,] 5 40
[4,] 1 40
[[4]]
Var1 Var2
[1,] 5 32
[2,] 8 32
[3,] 5 40
[4,] 8 40
多边形顶点的所有 row/column 位置在哪里。我们可以看到
的区域
cat(paste(apply(result$data, 1, paste, collapse=""), collapse="\n"))
# +----------+--------+------------------+
# |1111111111|222222222333333333333333|
# |1111111111|222222222233333333333333|
# |1111111111|222222222223333333333333|
# |1111111111|222222222222+------+-------+
# |1111111111|2222222222222222222|4444444|
# |1111111111|2222222222222222222|4444444|
# +----------+-------------------+-------+
我还考虑过提取连接角的列表。这种方法基本上是寻找所有的角，寻找存在“墙”或连接器的方向，然后找到该方向的第一个角。然后我们跟踪所有发现的对。所以首先，这里有一个帮助函数来找到“连接”的角
find_hit <- function(corner, corners, rvec, cvec) {
best <- NA
best_dist <- Inf
for(i in 1:nrow(corners)) {
rdist <- corners[i, 1] - corner[,1]
cdist <- corners[i, 2] - corner[,2]
if(sign(rdist) == sign(rvec) & sign(cdist) == sign(cvec) &
((rvec ==0 | cvec== 0) | (rdist%/%rvec ==cdist %/%cvec))) {
dist <- rdist + cdist
if (dist < best_dist) {
best_dist <- dist
best <- i
}
}
}
best
}
这个想法是，给定一个点和一个候选点列表，我们沿着一个特定的“向量”看，看看在那个方向的尽头有一个点，return 第一个命中。我们还有一个数字助手来确保我们正在查看的点是“在边界内”
in_bounds <- (function(data) {
function(r, c) {
r > 0 & r <= nrow(data) & c > 0 & c <= ncol(data)
}
})(data)
现在我们找到所有的角并循环遍历它们以找到连接
corners <- which(data=="+", arr.ind = TRUE)
edges <- list()
for (i in 1:(nrow(corners)-1)) {
corner <- corners[i, , drop=FALSE]
rest <- corners[-(1:i), , drop=FALSE]
r <- corner[, 1]
c <- corner[, 2]
for (dr in c(-1, 0, 1)) {
for (dc in c(-1, 0, 1)) {
if (in_bounds(r+dr, c+dc) & (dr != 0| dc != 0) && data[r+dr, c+dc]!=" ") {
hit <- find_hit(corner, rest, dr, dc)
if (!is.na(hit)) {
edges <- c(edges, list(c(i, i+hit)))
}
}
}
}
}
edges
所以edges是一个列表，告诉我们哪些角是相连的。我们可以用
把它变成一个 igraph 对象
library(igraph)
dd <- as.data.frame(do.call(rbind, edges))
dd[] <- lapply(dd, as.character)
g <- graph_from_data_frame(dd, directed = FALSE)
vnames <- as.character(1:nrow(corners))
V(g)[vnames]$row <- corners[,1]
V(g)[vnames]$col <- corners[,2]
plot(g)
然后你可以用
得到row/column信息
as.data.frame(vertex_attr(g))
为了使它们处于正确的形状，您可以设置 x 和 y 属性（这里我翻转了 y 方向，因为 (0,0) 在绘图时位于左下方，但在顶部留在矩阵中）
V(g)[vnames]$y <- -corners[,1]
V(g)[vnames]$x <- corners[,2]
plot(g)
在文本字符串中搜索图形元素的方式不同于@MrFlick。我只在下面显示水平边缘搜索。您需要添加垂直和对角线搜索。
string= "+----------+--------+------------------+
| | \ |
| | \ |
| | \ |
| | +------+-------+
| | | |
| | | |
+----------+-------------------+-------+
"
#convert string to ascii numeric matrix
graph_matrix = as.matrix(do.call(rbind, lapply(strsplit(string,"\n")[[1]],utf8ToInt) ))
#scan for horizontal lines
on_line=F
edges= data.frame()
for (row in 1:dim(graph_matrix)[1]) {
for (col in 1:dim(graph_matrix)[2]) {
if (graph_matrix[row,col]==45&on_line==F) {
on_line=T
edge = c(col-1,row)
} else if (graph_matrix[row,col]!=45&on_line==T) {
on_line=F
edge = c(edge,col,row)
edges = rbind(edges,edge)
}
}
}
colnames(edges) = c("x1","y1","x2","y2")
edges
#unique vertices
non_unique = mapply(c,edges[,1:2],edges[,3:4])
unique_verts = non_unique[!duplicated(non_unique),]
unique_verts
我有一个 .txt 文件，看起来像这样
+----------+--------+------------------+
| | \ |
| | \ |
| | \ |
| | +------+-------+
| | | |
| | | |
+----------+-------------------+-------+
如何识别这些多边形？
对于这个例子，我希望识别 4 个多边形。
我可以读取线条并识别每个顶点 ("+") 的坐标（行、列），但我不确定如何获取边坐标。我的主要目标是拥有一组描述每个多边形边界区域的点。
如何在 R 或 Python 中执行此操作？
我并不是说这非常有效，但这至少是解决 R 中问题的一种方法。首先，这是我读入数据的方式。
raw <- r"(
+----------+--------+------------------+
| | \ |
| | \ |
| | \ |
| | +------+-------+
| | | |
| | | |
+----------+-------------------+-------+
)"
data <- do.call("rbind", strsplit(readLines(textConnection(raw)), ""))
这将创建一个数组 data，其行数和列数与输入的所有字符都相同。
基本思路是我尝试填充该区域中的每个“空白”区域，并跟踪我们在填充过程中遇到的所有角。所以首先，一个辅助函数来获取给定单元格周围的 rows/columns
allnei <- expand.grid(-1:1, -1:1)
allnei <- allnei[allnei[,1] !=0 | allnei[,2] !=0, ]
get_neighbors <- function(point, data) {
cand <- t(c(point) +t(allnei))
cand[
cand[,1]>=1 & cand[,1]<=nrow(data) &
cand[,2]>=1 & cand[,2]<=ncol(data),
TRUE
]
}
然后大部分工作发生在 fill 函数
fill <- function(point, data, corners=matrix(nrow=0, ncol=2), fill_with="1") {
if (!is.matrix(point)) {
point <- matrix(point, ncol=2)
}
cand <- get_neighbors(point, data)
data[point] <- fill_with
corner_cand <- which(data[cand] == "+")
if (length(corner_cand)) {
corners <- unique(rbind(corners, cand[corner_cand, ]))
}
empty_cand <- which(data[cand] == " " & (cand[,1]==point[,1] | cand[,2]==point[,2]))
if (length(empty_cand)>0) {
for(i in empty_cand) {
result <- fill(cand[i,], data, corners, fill_with)
data <- result$data
corners <- unique(rbind(corners, result$corners))
}
}
list(data=data, corners=corners)
}
所以从一个“空”单元格开始，我们寻找相邻的单元格并将它们标记为同一区域。我们递归地执行此操作，直到我们 运行 超出相邻的空单元格。
现在我们需要一个包装器，它会一直这样做直到没有空白区域。
find_regions <- function(data) {
regions <- list()
reg <- 1
empty <- which(data==" ", arr.ind=TRUE)
while(nrow(empty)>0) {
empty <- empty[1,]
results <- fill(empty, data, fill_with=reg)
regions <- c(regions, list(results$corners))
data <- results$data
reg <- reg+1
empty <- which(data==" ", arr.ind=TRUE)
}
list(data=data, regions=regions)
}
result <- find_regions(data)
result$regions
给出输出
[1]]
Var1 Var2
[1,] 1 1
[2,] 8 1
[3,] 8 12
[4,] 1 12
[[2]]
Var1 Var2
[1,] 1 12
[2,] 8 12
[3,] 1 21
[4,] 5 25
[5,] 5 32
[6,] 8 32
[[3]]
Var1 Var2
[1,] 5 25
[2,] 5 32
[3,] 5 40
[4,] 1 40
[[4]]
Var1 Var2
[1,] 5 32
[2,] 8 32
[3,] 5 40
[4,] 8 40
多边形顶点的所有 row/column 位置在哪里。我们可以看到
的区域cat(paste(apply(result$data, 1, paste, collapse=""), collapse="\n"))
# +----------+--------+------------------+
# |1111111111|222222222333333333333333|
# |1111111111|222222222233333333333333|
# |1111111111|222222222223333333333333|
# |1111111111|222222222222+------+-------+
# |1111111111|2222222222222222222|4444444|
# |1111111111|2222222222222222222|4444444|
# +----------+-------------------+-------+
我还考虑过提取连接角的列表。这种方法基本上是寻找所有的角，寻找存在“墙”或连接器的方向，然后找到该方向的第一个角。然后我们跟踪所有发现的对。所以首先，这里有一个帮助函数来找到“连接”的角
find_hit <- function(corner, corners, rvec, cvec) {
best <- NA
best_dist <- Inf
for(i in 1:nrow(corners)) {
rdist <- corners[i, 1] - corner[,1]
cdist <- corners[i, 2] - corner[,2]
if(sign(rdist) == sign(rvec) & sign(cdist) == sign(cvec) &
((rvec ==0 | cvec== 0) | (rdist%/%rvec ==cdist %/%cvec))) {
dist <- rdist + cdist
if (dist < best_dist) {
best_dist <- dist
best <- i
}
}
}
best
}
这个想法是，给定一个点和一个候选点列表，我们沿着一个特定的“向量”看，看看在那个方向的尽头有一个点，return 第一个命中。我们还有一个数字助手来确保我们正在查看的点是“在边界内”
in_bounds <- (function(data) {
function(r, c) {
r > 0 & r <= nrow(data) & c > 0 & c <= ncol(data)
}
})(data)
现在我们找到所有的角并循环遍历它们以找到连接
corners <- which(data=="+", arr.ind = TRUE)
edges <- list()
for (i in 1:(nrow(corners)-1)) {
corner <- corners[i, , drop=FALSE]
rest <- corners[-(1:i), , drop=FALSE]
r <- corner[, 1]
c <- corner[, 2]
for (dr in c(-1, 0, 1)) {
for (dc in c(-1, 0, 1)) {
if (in_bounds(r+dr, c+dc) & (dr != 0| dc != 0) && data[r+dr, c+dc]!=" ") {
hit <- find_hit(corner, rest, dr, dc)
if (!is.na(hit)) {
edges <- c(edges, list(c(i, i+hit)))
}
}
}
}
}
edges
所以edges是一个列表，告诉我们哪些角是相连的。我们可以用
library(igraph)
dd <- as.data.frame(do.call(rbind, edges))
dd[] <- lapply(dd, as.character)
g <- graph_from_data_frame(dd, directed = FALSE)
vnames <- as.character(1:nrow(corners))
V(g)[vnames]$row <- corners[,1]
V(g)[vnames]$col <- corners[,2]
plot(g)
然后你可以用
得到row/column信息as.data.frame(vertex_attr(g))
为了使它们处于正确的形状，您可以设置 x 和 y 属性（这里我翻转了 y 方向，因为 (0,0) 在绘图时位于左下方，但在顶部留在矩阵中）
V(g)[vnames]$y <- -corners[,1]
V(g)[vnames]$x <- corners[,2]
plot(g)
在文本字符串中搜索图形元素的方式不同于@MrFlick。我只在下面显示水平边缘搜索。您需要添加垂直和对角线搜索。
string= "+----------+--------+------------------+
| | \ |
| | \ |
| | \ |
| | +------+-------+
| | | |
| | | |
+----------+-------------------+-------+
"
#convert string to ascii numeric matrix
graph_matrix = as.matrix(do.call(rbind, lapply(strsplit(string,"\n")[[1]],utf8ToInt) ))
#scan for horizontal lines
on_line=F
edges= data.frame()
for (row in 1:dim(graph_matrix)[1]) {
for (col in 1:dim(graph_matrix)[2]) {
if (graph_matrix[row,col]==45&on_line==F) {
on_line=T
edge = c(col-1,row)
} else if (graph_matrix[row,col]!=45&on_line==T) {
on_line=F
edge = c(edge,col,row)
edges = rbind(edges,edge)
}
}
}
colnames(edges) = c("x1","y1","x2","y2")
edges
#unique vertices
non_unique = mapply(c,edges[,1:2],edges[,3:4])
unique_verts = non_unique[!duplicated(non_unique),]
unique_verts