求将多多边形图结构拆分为单个多边形的算法方案

• 初始化集合存储已访问的无向边（用排序后的节点对或唯一字符串作为边的标识，避免重复处理）。
• 遍历图中所有节点，找到存在未访问边的节点作为起点：
  1. 以起点初始化当前节点，将起点加入当前多边形路径。
  2. 循环执行以下操作直到回到起点：
     • 在当前节点的邻居中，找到第一个对应边未被访问的节点。
     • 标记该边为已访问，将邻居节点加入路径，更新当前节点为该邻居。
  3. 将完成的多边形路径加入结果列表。
• 重复上述过程，直到所有边都被标记为已访问，得到所有拆分后的多边形。

注：由于所有节点度数均为偶数，交叉节点度数大于2，该算法可保证遍历出所有不重叠的多边形面。若需区分内外阴影区域，可后续结合节点坐标计算多边形面积的符号（顺时针/逆时针），但拆分过程无需依赖坐标。

def split_into_polygons(graph):
    visited_edges = set()
    polygons = []
    
    def get_edge(u, v):
        # 返回无向边的唯一标识
        return tuple(sorted((u, v)))
    
    for start_node in graph:
        # 检查起点是否存在未访问的边
        has_unvisited = any(get_edge(start_node, neighbor) not in visited_edges for neighbor in graph[start_node])
        if not has_unvisited:
            continue
        
        current_node = start_node
        polygon = [current_node]
        
        while True:
            next_node = None
            # 寻找下一个未访问的邻居节点
            for neighbor in graph[current_node]:
                edge = get_edge(current_node, neighbor)
                if edge not in visited_edges:
                    next_node = neighbor
                    visited_edges.add(edge)
                    break
            
            if not next_node:
                break  # 理论上不会触发，因所有节点度数为偶数
            
            polygon.append(next_node)
            current_node = next_node
            
            # 回到起点，完成当前多边形
            if current_node == start_node:
                polygons.append(polygon)
                break
    
    return polygons

# 示例图的图结构（模拟）
sample_graph = {
    1: [22, 11, 10],
    2: [11, 12],
    3: [12, 15, 9],
    4: [15, 16],
    5: [16, 21, 17],
    6: [17, 20, 18],
    7: [18, 19],
    8: [22, 10],
    9: [12, 14],
    10: [1, 8],
    11: [1, 2],
    12: [2, 3, 9],
    14: [9],
    15: [3, 4],
    16: [4, 5],
    17: [5, 6],
    18: [6, 7],
    19: [7],
    20: [6],
    21: [5],
    22: [1, 8]
}

# 调用并输出结果
result = split_into_polygons(sample_graph)
print(result)

function splitIntoPolygons(graph)
    local visitedEdges = {}
    local polygons = {}
    
    local function getEdge(u, v)
        -- 返回无向边的唯一标识字符串
        return u < v and (u .. "-" .. v) or (v .. "-" .. u)
    end
    
    for startNode, _ in pairs(graph) do
        -- 检查起点是否存在未访问的边
        local hasUnvisited = false
        for _, neighbor in ipairs(graph[startNode]) do
            local edge = getEdge(startNode, neighbor)
            if not visitedEdges[edge] then
                hasUnvisited = true
                break
            end
        end
        if not hasUnvisited then
            goto continue
        end
        
        local currentNode = startNode
        local polygon = {currentNode}
        
        while true do
            local nextNode = nil
            -- 寻找下一个未访问的邻居节点
            for _, neighbor in ipairs(graph[currentNode]) do
                local edge = getEdge(currentNode, neighbor)
                if not visitedEdges[edge] then
                    nextNode = neighbor
                    visitedEdges[edge] = true
                    break
                end
            end
            
            if not nextNode then
                break
            end
            
            table.insert(polygon, nextNode)
            currentNode = nextNode
            
            -- 回到起点，完成当前多边形
            if currentNode == startNode then
                table.insert(polygons, polygon)
                break
            end
        end
        
        ::continue::
    end
    
    return polygons
end

-- 示例图的图结构（模拟）
local sampleGraph = {
    [1] = {22, 11, 10},
    [2] = {11, 12},
    [3] = {12, 15, 9},
    [4] = {15, 16},
    [5] = {16, 21, 17},
    [6] = {17, 20, 18},
    [7] = {18, 19},
    [8] = {22, 10},
    [9] = {12, 14},
    [10] = {1, 8},
    [11] = {1, 2},
    [12] = {2, 3, 9},
    [14] = {9},
    [15] = {3, 4},
    [16] = {4, 5},
    [17] = {5, 6},
    [18] = {6, 7},
    [19] = {7},
    [20] = {6},
    [21] = {5},
    [22] = {1, 8}
}

-- 调用并输出结果
local result = splitIntoPolygons(sampleGraph)
for _, poly in ipairs(result) do
    io.write("[")
    for i, node in ipairs(poly) do
        if i > 1 then io.write(", ") end
        io.write(node)
    end
    io.write("]\n")
end

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