在 networkx 图中的单个单元格中填充颜色

Question

我用 networkx 构建了一个图，看起来像这样：Graph

我想用指定的颜色填充每个单元格。该图由 nx.draw_networkx_edges() （returns 一个 LineCollection）绘制。我在这里发现了一个类似的问题 (Fill area between lines)，但是评论中的解决方案对我不起作用。

我还使用了 plt.fill_between 和更简单的图表并手动设置值：

plt.fill_between([1, 2], [2, 2], color='yellow')
plt.fill_between([1.75, 2, 3], [1.25, 2, 2], color='purple')
plt.fill_between([0, 1, 1.25], [2, 2, 1.25], color='red')
plt.fill_between([0.75, 1.25, 1.75, 2.25], [0.75, 1.25, 1.25, 0.75], color='blue')
plt.fill_between([2, 2.25, 3], [0, 0.75, 1], color='pink')
plt.fill_between([0, 0.75, 1], [1, 0.75, 0], color='green')

结果很不错 (result)，但问题是，填充取决于单元格填充时的顺序，这会使算法变得复杂，我猜。

有谁知道更好更简单的解决方案吗？

编辑：我试图将图形转换为 Voronoi 图以尝试@JohanC 的解决方案，但运行时间相当长，而且较大图形的解决方案并不准确。为了计算质心，我使用了这个 Center of Polygon

def find_Centroid(v):
    sum_A = 0
    sum_x = 0
    sum_y = 0
    for i in range(len(v)):
        next = i+1 if i != len(v)-1 else 0
        sum_A += v[i][0]*v[next][1] - v[next][0]*v[i][1]
        sum_x += (v[i][0] + v[next][0]) * (v[i][0]*v[next][1] - v[next][0]*v[i][1])
        sum_y += (v[i][1] + v[next][1]) * (v[i][0]*v[next][1] - v[next][0]*v[i][1])
    A = 1/2 * sum_A
    Cx = 1/(6*A) * sum_x
    Cy = 1/(6*A) * sum_y

    return Cx, Cy

# Get all cells of Graph (I think that takes most of the time)
cycle = nx.minimum_cycle_basis(SVG)

centroids = list()

# calculate all centroids of the cells
for c in cycle:
    subG = SVG.subgraph(c)
    sortedCycle = sortGraphNodes(subG)
    centroid = find_Centroid(sortedCycle)
    SVG.add_node((centroid[0], centroid[1]))
    centroids.append(centroid)

vor = Voronoi(centroids)
voronoi_plot_2d(vor)
plt.show()

Result small graph Result large graph

Answer 1

使用显示填充更简单图形的问题中的第一个代码块，我构建了一个示例网络。下面列出了边缘：

edges = [((1, 2), (2, 2)),
         ((1, 2), (0, 2)),
         ((1, 2), (1.25, 1.25)),
         ((2, 2), (1.75, 1.25)),
         ((2, 2), (3, 2)),
         ((1.75, 1.25), (1.25, 1.25)),
         ((1.75, 1.25), (2.25, 0.75)),
         ((3, 2), (3, 1)),
         ((0, 2), (0, 1)),
         ((1.25, 1.25), (0.75, 0.75)),
         ((0.75, 0.75), (0, 1)),
         ((0.75, 0.75), (1, 0)),
         ((2.25, 0.75), (2, 0)),
         ((2.25, 0.75), (3, 1)),
         ((2, 0), (1, 0)),
         ((2, 0), (3, 0)),
         ((3, 1), (3, 0)),
         ((0, 1), (0, 0)),
         ((1, 0), (0, 0))]

有了这个网络，我们不需要使用任何 Voronoi 图表（虽然很顺眼）来填充网络的细胞。

求解的基础是使用最小循环网络的基础迭代器，然后更正每个用于跟踪网络中实际边缘的循环（请参阅 documentation for minimum cycle basis “节点不一定按顺序返回它们出现在循环中").

解决方案如下，假设edges 从上面：

import matplotlib.pyplot as plt
import networkx as nx

G = nx.Graph()
for edge in edges:
    G.add_edge(edge[0], edge[1])

pos = {x: x for x in G.nodes}
options = {
    "node_size": 10,
    "node_color": "lime",
    "edgecolors": "black",
    "linewidths": 1,
    "width": 1,
    "with_labels": False,
}
nx.draw_networkx(G, pos, **options)

# Fill all cells of graph
for cycle in nx.minimum_cycle_basis(G):
    full_cycle = cycle.copy()
    cycle_path = [full_cycle.pop(0)]
    while len(cycle_path) < len(cycle):
        for nb in G.neighbors(cycle_path[-1]):
            if nb in full_cycle:
                idx = full_cycle.index(nb)
                cycle_path.append(full_cycle.pop(idx))
                break
    plt.fill(*zip(*cycle_path))
plt.show()

结果图如下所示：

该算法比 Voronoi / centroid 更好地缩放问题编辑中列出的方法，但受到影响来自大型网络的相同低效率 (O(m^2n)，根据中的参考 documentation for minimum cycle basis).

在 networkx 图中的单个单元格中填充颜色

Fill color in single cells in a networkx graph

python

matplotlib

networkx