如何在空间节点网络中查找全部内部单元格？

核心思路 #

内部单元格是图中由4个节点围成的封闭凸四边形环，需满足：无内部节点、不属于外围边界。实现步骤如下：

• 建立节点ID到Node对象的映射，提取节点空间坐标
• 筛选所有长度为4的简单环（四边形）
• 对每个环进行三层校验：凸四边形、无内部节点、非外围边界

代码实现 #

先修正示例代码的语法错误，再实现目标函数：

import uuid
from dataclasses import dataclass
from itertools import combinations

import networkx as nx
from shapely.geometry import Point, Polygon


@dataclass
class Node:
    x: float
    y: float
    node_id: uuid.UUID

# 修正示例节点创建的语法错误
example_node = Node(x=0, y=1, node_id=uuid.uuid4())
G = nx.Graph()
G.add_node(example_node.node_id.hex, data=example_node)
# 可继续添加更多节点与连接关系


def get_graph_cells(G: nx.Graph) -> list[list[Node]]:
    """
    返回所有内部单元格，每个单元格由围成它的Node列表组成
    """
    # 1. 建立节点ID到Node对象的映射，生成节点的空间Point对象
    id_to_node = {node_id: attrs['data'] for node_id, attrs in G.nodes(data=True)}
    node_points = {node_id: Point(node.x, node.y) for node_id, node in id_to_node.items()}

    # 2. 筛选所有4节点构成的简单环（去重避免同一环的不同起始/方向重复）
    four_node_cycles = []
    seen_cycles = set()
    for cycle in nx.simple_cycles(G):
        if len(cycle) == 4:
            sorted_cycle = tuple(sorted(cycle))
            if sorted_cycle not in seen_cycles:
                seen_cycles.add(sorted_cycle)
                four_node_cycles.append(sorted_cycle)

    # 3. 校验并筛选内部单元格
    internal_cells = []
    for cycle_ids in four_node_cycles:
        cycle_nodes = [id_to_node[node_id] for node_id in cycle_ids]
        cycle_coords = [(node.x, node.y) for node in cycle_nodes]
        polygon = Polygon(cycle_coords)

        # 校验1：必须是有效凸四边形
        if not polygon.is_valid or not polygon.convex_hull.equals(polygon):
            continue

        # 校验2：内部无其他节点
        has_internal_node = False
        for node_id, point in node_points.items():
            if node_id not in cycle_ids and polygon.contains(point):
                has_internal_node = True
                break
        if has_internal_node:
            continue

        # 校验3：不属于外围单元格（环的边不连接度数<4的边界节点）
        is_perimeter = False
        for u, v in combinations(cycle_ids, 2):
            if G.has_edge(u, v):
                if G.degree(u) < 4 or G.degree(v) < 4:
                    is_perimeter = True
                    break
        if is_perimeter:
            continue

        # 按围绕质心的角度排序，保证节点顺序为顺时针/逆时针
        centroid = polygon.centroid
        sorted_nodes = sorted(cycle_nodes, key=lambda n: Point(n.x, n.y).angle(centroid))
        internal_cells.append(sorted_nodes)

    return internal_cells

关键说明 #

• 环的去重：通过排序环的节点ID，避免同一单元格因遍历顺序不同被重复记录
• 凸性校验：确保单元格是规则的四边形，排除凹边形或自相交的无效环
• 内部节点检查：利用Shapely的多边形包含关系，排除包含其他节点的环
• 外围排除：网格内部节点度数通常为4，边界节点度数小于4，以此区分内外环

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