1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
|
from itertools import combinations
import networkx as nx
from inkex import errormsg
from shapely.geometry import LineString, MultiPoint, Point
from shapely.ops import nearest_points
from .. import tiles
from ..debug import debug
from ..i18n import _
from ..utils.clamp_path import clamp_path_to_polygon
from ..utils.geometry import Point as InkStitchPoint
from ..utils.geometry import ensure_geometry_collection
from ..utils.list import poprandom
from ..utils.prng import iter_uniform_floats
from ..utils.smoothing import smooth_path
from ..utils.threading import check_stop_flag
from .running_stitch import running_stitch
def meander_fill(fill, shape, original_shape, shape_index, starting_point, ending_point):
debug.log(f"meander pattern: {fill.meander_pattern}")
tile = get_tile(fill.meander_pattern)
if not tile:
return []
debug.log(f"tile name: {tile.name}")
debug.log_line_strings(lambda: ensure_geometry_collection(shape.boundary).geoms, 'Meander shape')
graph = tile.to_graph(shape, fill.meander_scale, fill.meander_angle)
if not graph:
label = fill.node.label or fill.node.get_id()
errormsg(_('%s: Could not build graph for meander stitching. Try to enlarge your shape or '
'scale your meander pattern down.') % label)
return []
debug.log_graph(graph, 'Meander graph')
ensure_connected(graph)
start, end = find_starting_and_ending_nodes(graph, shape, starting_point, ending_point)
rng = iter_uniform_floats(fill.random_seed, 'meander-fill', shape_index)
return post_process(generate_meander_path(graph, start, end, rng), shape, original_shape, fill)
def get_tile(tile_id):
all_tiles = {tile.id: tile for tile in tiles.all_tiles()}
try:
return all_tiles.get(tile_id, all_tiles.popitem()[1])
except KeyError:
return None
def ensure_connected(graph):
"""If graph is unconnected, add edges to make it connected."""
# TODO: combine this with possible_jumps() in lib/stitches/utils/autoroute.py
possible_connections = []
for component1, component2 in combinations(nx.connected_components(graph), 2):
points1 = MultiPoint([Point(node) for node in component1])
points2 = MultiPoint([Point(node) for node in component2])
start_point, end_point = nearest_points(points1, points2)
possible_connections.append(((start_point.x, start_point.y), (end_point.x, end_point.y), start_point.distance(end_point)))
if possible_connections:
for start, end in nx.k_edge_augmentation(graph, 1, avail=possible_connections):
check_stop_flag()
graph.add_edge(start, end)
def find_starting_and_ending_nodes(graph, shape, starting_point, ending_point):
if starting_point is None:
starting_point = shape.exterior.coords[0]
starting_point = Point(starting_point)
if ending_point is None:
# pick a spot on the opposite side of the shape
projection = (shape.exterior.project(starting_point, normalized=True) + 0.5) % 1.0
ending_point = shape.exterior.interpolate(projection, normalized=True)
else:
ending_point = Point(ending_point)
all_points = MultiPoint(list(graph))
starting_node = nearest_points(starting_point, all_points)[1].coords[0]
ending_node = nearest_points(ending_point, all_points)[1].coords[0]
if starting_node == ending_node:
# We need a path to start with, so pick a new ending node
all_points = all_points.difference(Point(starting_node))
ending_node = nearest_points(ending_point, all_points)[1].coords[0]
return starting_node, ending_node
def find_initial_path(graph, start, end):
# We need some path to start with. We could use
# nx.all_simple_paths(graph, start, end) and choose the first one.
# However, that tends to pick a really "orderly" path. Shortest
# path looks more random.
# TODO: handle if this can't find a path
return nx.shortest_path(graph, start, end)
@debug.time
def generate_meander_path(graph, start, end, rng):
path = find_initial_path(graph, start, end)
path_edges = list(zip(path[:-1], path[1:]))
graph.remove_edges_from(path_edges)
graph_nodes = set(graph) - set(path)
edges_to_consider = list(path_edges)
meander_path = path_edges
while edges_to_consider:
while edges_to_consider:
check_stop_flag()
edge = poprandom(edges_to_consider, rng)
edges_to_consider.extend(replace_edge(meander_path, edge, graph, graph_nodes))
edge_pairs = list(zip(meander_path[:-1], meander_path[1:]))
while edge_pairs:
check_stop_flag()
edge1, edge2 = poprandom(edge_pairs, rng)
new_edges = replace_edge_pair(meander_path, edge1, edge2, graph, graph_nodes)
if new_edges:
edges_to_consider.extend(new_edges)
break
debug.log_graph(graph, "remaining graph", "#FF0000")
points = path_to_points(meander_path)
debug.log_line_string(LineString(points), "meander path", "#00FF00")
return points
def replace_edge(path, edge, graph, graph_nodes):
subgraph = graph.subgraph(graph_nodes | set(edge))
new_path = None
for new_path in nx.all_simple_edge_paths(subgraph, edge[0], edge[1], 7):
if len(new_path) > 1:
break
if new_path is None or len(new_path) == 1:
return []
i = path.index(edge)
path[i:i + 1] = new_path
graph.remove_edges_from(new_path)
# do I need to remove the last one too?
graph_nodes.difference_update(start for start, end in new_path)
# debug.log(f"found new path of length {len(new_path)} at position {i}")
return new_path
def replace_edge_pair(path, edge1, edge2, graph, graph_nodes):
subgraph = graph.subgraph(graph_nodes | {edge1[0], edge2[1]})
new_path = None
for new_path in nx.all_simple_edge_paths(subgraph, edge1[0], edge2[1], 10):
if len(new_path) > 2:
break
if new_path is None or len(new_path) <= 2:
return []
i = path.index(edge1)
path[i:i + 2] = new_path
graph.remove_edges_from(new_path)
# do I need to remove the last one too?
graph_nodes.difference_update(start for start, end in new_path)
# debug.log(f"found new pair path of length {len(new_path)} at position {i}")
return new_path
@debug.time
def post_process(points, shape, original_shape, fill):
debug.log(f"smoothness: {fill.smoothness}")
# debug.log_line_string(LineString(points), "pre-smoothed", "#FF0000")
smoothed_points = smooth_path(points, fill.smoothness)
smoothed_points = [InkStitchPoint.from_tuple(point) for point in smoothed_points]
stitches = running_stitch(smoothed_points, fill.running_stitch_length, fill.running_stitch_tolerance)
if fill.clip:
stitches = clamp_path_to_polygon(stitches, original_shape)
return stitches
def path_to_points(path):
points = [start for start, end in path]
if path:
points.append(path[-1][1])
return points
|
