Enable Javascript in your browser and then refresh this page, for a much enhanced experience.
Eulerian path solution in Clear category for One line Drawing by Phil15
#Inspired by https://www.geeksforgeeks.org/eulerian-path-undirected-graph/
def draw(segments):
"""For draw without lift the pen, we look for an eulerian path
in the graph whose edges are the segments, and vertices are the points."""
segment = lambda A,B: (A[0],A[1],B[0],B[1])
points = list(set.union(*[{(a,b), (c,d)} for (a,b,c,d) in segments]))
N = len(points)
graph = {point: {p for p in points if segment(point, p) in segments
or segment(p, point) in segments}
for point in points}
degrees = {point: len(graph[point]) for point in points}
odd_points = {point for point in points if degrees[point]%2==1}
if len(odd_points) > 2:#No eulerian path.
return []
adjacency_matrix = [[(0,1)[A in graph[B]]
for B in points] for A in points]
pos = points.index(odd_points.pop()) if odd_points else 0
stack, path = [], []
while stack or sum(adjacency_matrix[pos]) != 0:
if sum(adjacency_matrix[pos]) != 0:
for i in range(N):
if adjacency_matrix[pos][i] == 1:
stack.append(pos)
adjacency_matrix[pos][i], adjacency_matrix[i][pos] = 0, 0
pos = i
break
else:
path.append(pos)
pos = stack.pop(-1)
path.append(pos)
return [points[i] for i in path]
July 25, 2018
