def fix_face_winding(mesh):
'''
Traverse and change mesh faces in-place to make sure winding is coherent,
or that edges on adjacent faces are in opposite directions
'''
if mesh.is_winding_consistent:
log.info('mesh has consistent winding, exiting winding repair')
return
# we create the face adjacency graph:
# every node in g is an index of mesh.faces
# every edge in g represents two faces which are connected
graph_all = nx.from_edgelist(mesh.face_adjacency)
flipped = 0
faces = mesh.faces.view(np.ndarray).copy()
# we are going to traverse the graph using BFS, so we have to start
# a traversal for every connected component
for graph in nx.connected_component_subgraphs(graph_all):
start = graph.nodes()[0]
# we traverse every pair of faces in the graph
# we modify mesh.faces and mesh.face_normals in place
for face_pair in nx.bfs_edges(graph, start):
# for each pair of faces, we convert them into edges,
# find the edge that both faces share, and then see if the edges
# are reversed in order as you would expect in a well constructed mesh
face_pair = np.ravel(face_pair)
pair = faces[face_pair]
edges = faces_to_edges(pair)
overlap = group_rows(np.sort(edges,axis=1), require_count=2)
if len(overlap) == 0:
# only happens on non-watertight meshes
continue
edge_pair = edges[[overlap[0]]]
if edge_pair[0][0] == edge_pair[1][0]:
# if the edges aren't reversed, invert the order of one of the faces
flipped += 1
faces[face_pair[1]] = faces[face_pair[1]][::-1]
if flipped > 0:
mesh.faces = faces
log.info('Flipped %d/%d edges', flipped, len(mesh.faces)*3)
python类connected_component_subgraphs()的实例源码
def connectGraphComponents(graph, level=2, highway='path', connectNearest=False):
if nx.is_connected(graph):
return graph
combinations = itertools.permutations(range(nx.number_connected_components(graph)),2)
subgraphs = list(nx.connected_component_subgraphs(graph, copy=True))
rtrees = [getGraphRtree(subgraph,'nodes') for subgraph in subgraphs]
nearestComponents={}
for i, j in combinations:
if i not in nearestComponents:
nearestComponents[i] = []
smallest = i if len(subgraphs[i]) < len(subgraphs[j]) else j
biggest = j if smallest is i else i
candidates = {}
nearestNeighbors = {}
for node1, data in subgraphs[smallest].nodes(data=True):
x, y = data['longitude'], data['latitude']
hits = list(rtrees[biggest].nearest((x, y, x, y), 2, objects="raw"))
for candidate in hits:
data = json.loads(candidate)
candidates[data['id']] = Point(data['geometry']['coordinates'])
source = Point([x,y])
distance, node2 = nearestNode(source, candidates)
nearestNeighbors[distance] = node1, node2
u,v = nearestNeighbors[min(nearestNeighbors.keys())]
if connectNearest:
nearestComponents[i].append((j, min(nearestNeighbors.keys()), (u,v)))
else:
newAttributes = {'level':level, 'highway': highway,'osmid':'-1','policosm':True, 'lanes':1,'oneway': False}
graph.add_edge(u, v, newAttributes)
if connectNearest:
for i in nearestComponents.keys():
data = nearestComponents[i]
j, distance, (u,v) = sorted(data, key=lambda tup: tup[1])[0]
if not graph.has_edge(u, v):
newAttributes = {'level':level, 'highway': highway,'osmid':'-1','policosm':True, 'lanes':1,'oneway': False}
graph.add_edge(u, v, newAttributes)
return connectGraphComponents(graph, level, highway, connectNearest=connectNearest)
def connectGraphComponents(graph, level=2, highway='path', connectNearest=False):
if nx.is_connected(graph):
return graph
combinations = itertools.permutations(range(nx.number_connected_components(graph)),2)
subgraphs = list(nx.connected_component_subgraphs(graph, copy=True))
rtrees = [getGraphRtree(subgraph,'nodes') for subgraph in subgraphs]
nearestComponents={}
for i, j in combinations:
if i not in nearestComponents:
nearestComponents[i] = []
smallest = i if len(subgraphs[i]) < len(subgraphs[j]) else j
biggest = j if smallest is i else i
candidates = {}
nearestNeighbors = {}
for node1, data in subgraphs[smallest].nodes(data=True):
x, y = data['longitude'], data['latitude']
hits = list(rtrees[biggest].nearest((x, y, x, y), 2, objects="raw"))
for candidate in hits:
data = json.loads(candidate)
candidates[data['id']] = Point(data['geometry']['coordinates'])
source = Point([x,y])
distance, node2 = nearestNode(source, candidates)
nearestNeighbors[distance] = node1, node2
u,v = nearestNeighbors[min(nearestNeighbors.keys())]
if connectNearest:
nearestComponents[i].append((j, min(nearestNeighbors.keys()), (u,v)))
else:
newAttributes = {'level':level, 'highway': highway,'osmid':'-1','policosm':True, 'lanes':1,'oneway': False}
graph.add_edge(u, v, newAttributes)
if connectNearest:
for i in nearestComponents.keys():
data = nearestComponents[i]
j, distance, (u,v) = sorted(data, key=lambda tup: tup[1])[0]
if not graph.has_edge(u, v):
newAttributes = {'level':level, 'highway': highway,'osmid':'-1','policosm':True, 'lanes':1,'oneway': False}
graph.add_edge(u, v, newAttributes)
return connectGraphComponents(graph, level, highway, connectNearest=connectNearest)
def effect(self):
totalTimerStart = timeit.default_timer()
(vertices, edges) = self.parseSVG()
G = self.buildGraph(vertices, edges)
timerStart = timeit.default_timer()
self.mergeWithTolerance(G, self.options.tolerance)
timerStop = timeit.default_timer()
mergeDuration = timerStop-timerStart
"""for e in G.edges():
self.log("E "+str(e[0]) + " " + str(e[1]))
for n in G.nodes():
self.log("Degree of "+str(n) + ": " + str(G.degree(n)))"""
#Split disjoint graphs
connectedGraphs = list(nx.connected_component_subgraphs(G))
self.log("Number of disconnected graphs: " + str(len(connectedGraphs)))
paths = []
makeEulerianDuration = 0
for connectedGraph in connectedGraphs:
timerStart = timeit.default_timer()
if self.options.overwriteRule == OVERWRITE_ALLOW_NONE:
connectedGraph = self.makeEulerianGraphExtraNode(connectedGraph)
else:
connectedGraph = self.makeEulerianGraph(connectedGraph)
timerStop = timeit.default_timer()
makeEulerianDuration += timerStop-timerStart
#connectedGraph is now likely a multigraph
pathEdges = self.eulerian_circuit_hierholzer(connectedGraph)
pathEdges = self.removeSomeEdges(connectedGraph, pathEdges)
pathEdges = self.shiftEdgesToBreak(pathEdges)
paths.extend(self.edgesToPaths(pathEdges))
self.log("Path number: " + str(len(paths)))
self.log("Total path length: " + str(sum(self.pathLength(G, x) for x in paths)))
self.pathsToSVG(G, paths)
totalTimerStop = timeit.default_timer()
totalDuration = totalTimerStop-totalTimerStart
self.log("Merge duration: {:f} sec ({:f} min)".format(mergeDuration, mergeDuration/60))
self.log("Make Eulerian duration: {:f} sec ({:f} min)".format(makeEulerianDuration, makeEulerianDuration/60))
self.log("Total duration: {:f} sec ({:f} min)".format(totalDuration, totalDuration/60))
