如何创建具有线性缩放特性的六边形（环形）晶格？

你的思路完全可行 #

以“涡旋式迭代添加瓦片”的方式，确实能实现O(n)线性复杂度的环形六边形晶格生成——每一步仅处理当前新增的瓦片，无需遍历整个已生成的结构，完美规避NetworkX原生方法的二次复杂度问题。

具体实现步骤 #

• 初始化核心环：先创建由6个瓦片组成的初始六边形环（对应第一张示例图），用轴向坐标（适配六边形结构的坐标系统）标记每个瓦片，同时建立核心环内部的邻接边。
• 定向迭代扩展：沿着六边形的6个固定方向依次向外扩展，每一轮只处理当前的边缘瓦片集合：
  1. 遍历当前边缘的每个瓦片，在其空缺的邻接方向添加新瓦片
  2. 仅为新瓦片建立与相邻已存在瓦片的连接，无需全局更新
  3. 更新边缘瓦片集合为刚新增的瓦片，进入下一个方向的扩展
• 坐标去重：用轴向坐标作为瓦片的唯一标识，避免重复创建相同位置的瓦片。

基于NetworkX的代码实现 #

import networkx as nx

def linear_hexagonal_ring(target_tiles):
    G = nx.Graph()
    # 六边形轴向坐标的6个邻接方向
    hex_directions = [(1, 0), (1, -1), (0, -1), (-1, 0), (-1, 1), (0, 1)]
    
    # 初始化6个瓦片的核心环
    core = [(1,0), (1,-1), (0,-1), (-1,0), (-1,1), (0,1)]
    G.add_nodes_from(core)
    # 连接核心环的相邻瓦片
    for i in range(6):
        G.add_edge(core[i], core[(i+1)%6])
    
    current_edge = core.copy()
    # 迭代扩展直到达到目标瓦片数
    while len(G.nodes) < target_tiles:
        new_edge = []
        for dir_idx in range(6):
            dx, dy = hex_directions[dir_idx]
            for tile in current_edge:
                x, y = tile
                new_tile = (x + dx, y + dy)
                if new_tile not in G:
                    G.add_node(new_tile)
                    G.add_edge(tile, new_tile)
                    new_edge.append(new_tile)
                    # 达到目标数就提前终止
                    if len(G.nodes) == target_tiles:
                        return G
        current_edge = new_edge
    return G

# 生成对应示例的结构
# 6个瓦片：linear_hexagonal_ring(6)
# 7个瓦片（添加1个后）：linear_hexagonal_ring(7)
# 17个瓦片：linear_hexagonal_ring(17)

复杂度说明 #

这个实现中，每个瓦片仅被创建和连接一次，所有操作都是常数时间，整体复杂度严格随瓦片总数n线性增长，完全符合你的需求。

示例对应结构 #

• 初始6个瓦片：
• 添加1个瓦片后的环形结构：
• 17个瓦片的最终结构：

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