网络节点求和：如何实现适配任意多边形的通用函数？

背景与网格模型实现 #

我在学习Valeriepieris圆问题（寻找能容纳全球一半人口的最小圆）时，做了简化模拟：构建一个由1000个节点组成的矩形网格无向图，每个节点仅与直接邻居相连，节点分配随机值模拟人口。

实现代码：

library(igraph)

width <- 30
height <- 20
num_nodes <- width * height

# 创建网格坐标
x <- rep(1:width, each = height)
y <- rep(1:height, times = width)

g <- make_empty_graph(n = num_nodes, directed = FALSE)

# 根据坐标获取节点索引的函数
get_node_index <- function(i, j) (i - 1) * height + j

# 添加邻接边
edges <- c()
for(i in 1:width) {
   for(j in 1:height) {
      current_node <- get_node_index(i, j)
    
      # 连接右侧邻居
      if(i < width) edges <- c(edges, current_node, get_node_index(i + 1, j))
    
      # 连接下方邻居
      if(j < height) edges <- c(edges, current_node, get_node_index(i, j + 1))
   }
}

g <- add_edges(g, edges)

V(g)$x <- x
V(g)$y <- y

# 绘制节点索引图和人口值图
par(mfrow=c(1,2))

V(g)$name <- 1:num_nodes
plot(g, vertex.size = 7, vertex.label = V(g)$name, vertex.label.cex = 0.6, main = "带节点索引的网格图")

V(g)$value <- sample(1:100, num_nodes, replace = TRUE)
plot(g, vertex.size = 7, vertex.label = V(g)$value, vertex.label.cex = 0.6, main = "带人口值的网格图")

正方形区域的人口求和实现 #

由于圆形处理难度较高，我先实现了4节点组成的正方形区域，目标是找出人口总和最大的正方形：

library(dplyr)
squares <- list()
square_id <- 1

for(i in 1:(width-1)) {
for(j in 1:(height-1)) {
    top_left <- get_node_index(i, j)
    top_right <- get_node_index(i+1, j)
    bottom_left <- get_node_index(i, j+1)
    bottom_right <- get_node_index(i+1, j+1)
    
        square <- c(top_left, top_right, bottom_left, bottom_right)
        squares[[square_id]] <- square
        square_id <- square_id + 1
    }
}

result_df <- data.frame(
    square_id = seq_along(squares),
    nodes_id_selected = sapply(squares, function(s) paste(s, collapse = ", ")),
    value = sapply(squares, function(s) sum(V(g)$value[s]))
)

print(head(result_df %>% arrange(-value)))

输出示例：

square_id  nodes_id_selected value
       334 351, 371, 352, 372   365
        51     53, 73, 54, 74   350

技术问询与解决方案 #

问题 #

能否将该方法推广到任意边数的形状（如三角形、六边形等）？是否可以编写通用函数来完成任意形状的节点求和与比较？

解答 #

完全可以推广到任意规则或半规则形状，核心思路是定义形状的相对坐标模板，再遍历网格中所有合法的形状位置，最后计算每个形状的节点值总和并排序。

通用实现步骤

1. 定义形状模板：用相对坐标（相对于形状的"锚点"，比如左上角顶点或中心）描述形状包含的节点。例如：

   • 2x2正方形模板：list(c(0,0), c(1,0), c(0,1), c(1,1))（锚点为(i,j)，其他节点为锚点坐标加相对值）
   • 直角三角形模板：list(c(0,0), c(1,0), c(0,1))
   • 正六边形模板（以中心为锚点）：list(c(0,0), c(1,0), c(1,-1), c(0,-1), c(-1,-1), c(-1,0))

2. 编写通用遍历函数：输入网格宽高、形状模板、节点值向量，输出所有合法形状的求和结果。

通用函数示例代码

library(dplyr)

# 通用形状求和函数
calculate_shape_sums <- function(width, height, shape_template, node_values) {
  # 计算锚点的合法范围，确保形状所有节点都在网格内
  min_i <- max(1, 1 - min(sapply(shape_template, function(p) p[1])))
  max_i <- min(width, width - max(sapply(shape_template, function(p) p[1])))
  min_j <- max(1, 1 - min(sapply(shape_template, function(p) p[2])))
  max_j <- min(height, height - max(sapply(shape_template, function(p) p[2])))
  
  results <- list()
  result_id <- 1
  
  # 遍历所有合法锚点
  for(i in min_i:max_i) {
    for(j in min_j:max_j) {
      # 获取形状所有节点的索引
      shape_nodes <- sapply(shape_template, function(p) {
        get_node_index(i + p[1], j + p[2])
      })
      # 计算人口总和
      total_value <- sum(node_values[shape_nodes])
      # 存储结果
      results[[result_id]] <- list(
        shape_id = result_id,
        anchor = c(i,j),
        node_ids = shape_nodes,
        total_value = total_value
      )
      result_id <- result_id + 1
    }
  }
  
  # 转换为数据框并按总和降序排序
  results_df <- bind_rows(results) %>%
    mutate(node_ids_str = sapply(node_ids, paste, collapse = ", ")) %>%
    arrange(desc(total_value))
  
  return(results_df)
}

# 定义不同形状模板
# 2x2正方形模板（锚点为左上角）
square_template <- list(c(0,0), c(1,0), c(0,1), c(1,1))
# 直角三角形模板（锚点为直角顶点）
triangle_template <- list(c(0,0), c(1,0), c(0,1))
# 正六边形模板（锚点为中心）
hexagon_template <- list(c(0,0), c(1,0), c(1,-1), c(0,-1), c(-1,-1), c(-1,0))

# 使用正方形模板计算
square_results <- calculate_shape_sums(width, height, square_template, V(g)$value)
print(head(square_results))

# 使用三角形模板计算
triangle_results <- calculate_shape_sums(width, height, triangle_template, V(g)$value)
print(head(triangle_results))

关键说明

• 形状灵活性：只要能通过相对坐标定义的形状（包括不规则形状如L型）都能适配。
• 边界校验：函数自动计算锚点的合法范围，避免形状超出网格边界。
• 圆形适配：如果要近似处理圆形，可以定义"圆形模板"——以锚点为中心，包含所有距离锚点在设定阈值内的节点，本质仍是相对坐标的集合。

内容的提问来源于stack exchange，提问作者farrow90