I’ve build a graph with networkx, that looks like this: Graph
I want to fill every singel cell with a specified color. The Graph was drawn by nx.draw_networkx_edges() (returns a LineCollection). I found a similar question here (Fill area between lines), but the solution in the comments, doesn’t worked for me.
I’ve also used plt.fill_between with a simpler graph and manually set the values:
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')
And it turns out pretty good (result), but the problem with that is, that the filling depends on the order when the cells get filled and that would make the algorithm for it way to complicated, I guess.
Does anyone knows a better and simpler solution?
Edit: I tried to convert the Graph into a Voronoi-Diagram to try the solution of @JohanC, but the runtime is pretty long and the solution for larger graphs isn’t exact. For the calculation of the centroids I used this 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
Advertisement
Answer
Using the first code block from the question that shows filling the simpler graph, I constructed an example network. The edges are listed below:
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))]
With this network, we do not need to use any Voronoi diagram (although very pleasing to they eye) to fill the cells of the network.
The basis for the solution is to use the minimum cycle basis iterator for the network, and then correct each cycle for following actual edges in the network (see documentation for minimum cycle basis “nodes are not necessarily returned in a order by which they appear in the cycle”).
The solution becomes the following, assuming edges
from above:
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()
The resulting graph looks like this:
This algorithm scales better than the Voronoi / centroid approach listed in the edit to the question, but suffers from the same inefficiencies for large networks (O(m^2n), according to the reference in the documentation for minimum cycle basis).