From ba835b4f5e33f404b7bed9369a1b425a67b312c5 Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Mon, 16 Jan 2023 14:27:06 -0500 Subject: meander fill: initial version --- lib/stitches/meander_fill.py | 104 +++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 104 insertions(+) create mode 100644 lib/stitches/meander_fill.py (limited to 'lib/stitches/meander_fill.py') diff --git a/lib/stitches/meander_fill.py b/lib/stitches/meander_fill.py new file mode 100644 index 00000000..2ac3cd03 --- /dev/null +++ b/lib/stitches/meander_fill.py @@ -0,0 +1,104 @@ +from shapely.geometry import MultiPoint, Point +from shapely.ops import nearest_points +import networkx as nx + +from .. import tiles +from ..debug import debug +from ..utils.list import poprandom + + +def meander_fill(fill, shape, starting_point, ending_point): + tile = get_tile(fill.meander_pattern) + if not tile: + return [] + + graph = tile.to_graph(shape) + start, end = find_starting_and_ending_nodes(graph, starting_point, ending_point) + + return generate_meander_path(graph, start, end) + + +def get_tile(tile_name): + all_tiles = {tile.name: tile for tile in tiles.all_tiles()} + + try: + return all_tiles.get(tile_name, all_tiles.popitem()[1]) + except KeyError: + return None + + +def find_starting_and_ending_nodes(graph, starting_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. + return nx.shortest_path(graph, start, end) + + +def generate_meander_path(graph, start, end): + 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: + edge = poprandom(edges_to_consider) + edges_to_consider.extend(replace_edge(meander_path, edge, graph, graph_nodes)) + + edge_pairs = list(zip(path[:-1], path[1:])) + while edge_pairs: + edge1, edge2 = poprandom(edge_pairs) + edges_to_consider.extend(replace_edge_pair(meander_path, edge1, edge2, graph, graph_nodes)) + + return meander_path + + +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) + 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) + 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 -- cgit v1.2.3 From 847e133f97d570e2967dfa7dcfc16a212dc2bbbc Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Tue, 17 Jan 2023 21:44:23 -0500 Subject: meander fill: more work --- lib/stitches/meander_fill.py | 72 ++++++++++++++++++++++++++++++++++++-------- 1 file changed, 59 insertions(+), 13 deletions(-) (limited to 'lib/stitches/meander_fill.py') diff --git a/lib/stitches/meander_fill.py b/lib/stitches/meander_fill.py index 2ac3cd03..cb6e3f4e 100644 --- a/lib/stitches/meander_fill.py +++ b/lib/stitches/meander_fill.py @@ -1,21 +1,33 @@ +import networkx as nx from shapely.geometry import MultiPoint, Point from shapely.ops import nearest_points -import networkx as nx +from .running_stitch import running_stitch from .. import tiles from ..debug import debug +from ..stitch_plan import Stitch +from ..utils import smooth_path +from ..utils.geometry import Point as InkStitchPoint from ..utils.list import poprandom +from ..utils.prng import iter_uniform_floats -def meander_fill(fill, shape, starting_point, ending_point): +def meander_fill(fill, 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 [] - graph = tile.to_graph(shape) - start, end = find_starting_and_ending_nodes(graph, starting_point, ending_point) + debug.log(f"tile name: {tile.name}") - return generate_meander_path(graph, start, end) + # debug.log_line_strings(ensure_geometry_collection(shape.boundary).geoms, 'Meander shape') + graph = tile.to_graph(shape, fill.meander_scale, fill.meander_padding) + # debug.log_graph(graph, 'Meander graph') + # debug.log(f"graph connected? {nx.is_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), fill) def get_tile(tile_name): @@ -27,7 +39,16 @@ def get_tile(tile_name): return None -def find_starting_and_ending_nodes(graph, starting_point, ending_point): +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: + ending_point = starting_point + else: + ending_point = Point(ending_point) + all_points = MultiPoint(list(graph)) starting_node = nearest_points(starting_point, all_points)[1].coords[0] @@ -49,7 +70,8 @@ def find_initial_path(graph, start, end): return nx.shortest_path(graph, start, end) -def generate_meander_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) @@ -59,15 +81,16 @@ def generate_meander_path(graph, start, end): meander_path = path_edges while edges_to_consider: while edges_to_consider: - edge = poprandom(edges_to_consider) + edge = poprandom(edges_to_consider, rng) edges_to_consider.extend(replace_edge(meander_path, edge, graph, graph_nodes)) - edge_pairs = list(zip(path[:-1], path[1:])) + edge_pairs = list(zip(meander_path[:-1], meander_path[1:])) while edge_pairs: - edge1, edge2 = poprandom(edge_pairs) + edge1, edge2 = poprandom(edge_pairs, rng) edges_to_consider.extend(replace_edge_pair(meander_path, edge1, edge2, graph, graph_nodes)) + break - return meander_path + return path_to_points(meander_path) def replace_edge(path, edge, graph, graph_nodes): @@ -81,8 +104,9 @@ def replace_edge(path, edge, graph, graph_nodes): 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}") + # debug.log(f"found new path of length {len(new_path)} at position {i}") return new_path @@ -98,7 +122,29 @@ def replace_edge_pair(path, edge1, edge2, graph, graph_nodes): 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}") + # debug.log(f"found new pair path of length {len(new_path)} at position {i}") return new_path + + +@debug.time +def post_process(points, 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) + stitches = [Stitch(point) for point in stitches] + + return stitches + + +def path_to_points(path): + points = [start for start, end in path] + if path: + points.append(path[-1][1]) + + return points -- cgit v1.2.3 From 4935d59f5dfbf3c4a8a0733b1aa6380cd11aefb4 Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Sat, 28 Jan 2023 21:35:24 -0500 Subject: wip --- lib/stitches/meander_fill.py | 3 +++ 1 file changed, 3 insertions(+) (limited to 'lib/stitches/meander_fill.py') diff --git a/lib/stitches/meander_fill.py b/lib/stitches/meander_fill.py index cb6e3f4e..81efa398 100644 --- a/lib/stitches/meander_fill.py +++ b/lib/stitches/meander_fill.py @@ -20,6 +20,7 @@ def meander_fill(fill, shape, shape_index, starting_point, ending_point): debug.log(f"tile name: {tile.name}") + # from ..utils.geometry import ensure_geometry_collection # debug.log_line_strings(ensure_geometry_collection(shape.boundary).geoms, 'Meander shape') graph = tile.to_graph(shape, fill.meander_scale, fill.meander_padding) # debug.log_graph(graph, 'Meander graph') @@ -67,6 +68,8 @@ def find_initial_path(graph, start, end): # 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) -- cgit v1.2.3 From 5a95e1d004862331cf54de9c90b6a6d965428e8a Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Sat, 28 Jan 2023 22:09:34 -0500 Subject: add lambda unwrapping to debug --- lib/stitches/meander_fill.py | 9 ++++----- 1 file changed, 4 insertions(+), 5 deletions(-) (limited to 'lib/stitches/meander_fill.py') diff --git a/lib/stitches/meander_fill.py b/lib/stitches/meander_fill.py index 81efa398..6b3df0e3 100644 --- a/lib/stitches/meander_fill.py +++ b/lib/stitches/meander_fill.py @@ -7,7 +7,7 @@ from .. import tiles from ..debug import debug from ..stitch_plan import Stitch from ..utils import smooth_path -from ..utils.geometry import Point as InkStitchPoint +from ..utils.geometry import Point as InkStitchPoint, ensure_geometry_collection from ..utils.list import poprandom from ..utils.prng import iter_uniform_floats @@ -20,11 +20,10 @@ def meander_fill(fill, shape, shape_index, starting_point, ending_point): debug.log(f"tile name: {tile.name}") - # from ..utils.geometry import ensure_geometry_collection - # debug.log_line_strings(ensure_geometry_collection(shape.boundary).geoms, 'Meander shape') + debug.log_line_strings(lambda: ensure_geometry_collection(shape.boundary).geoms, 'Meander shape') graph = tile.to_graph(shape, fill.meander_scale, fill.meander_padding) - # debug.log_graph(graph, 'Meander graph') - # debug.log(f"graph connected? {nx.is_connected(graph)}") + debug.log_graph(graph, 'Meander graph') + debug.log(lambda: f"graph connected? {nx.is_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) -- cgit v1.2.3 From 8dde33d867afce7ea4aa212dfce60e9e526bbc1c Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Sun, 5 Feb 2023 22:58:17 -0500 Subject: make meander interruptible --- lib/stitches/meander_fill.py | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'lib/stitches/meander_fill.py') diff --git a/lib/stitches/meander_fill.py b/lib/stitches/meander_fill.py index 6b3df0e3..5f399158 100644 --- a/lib/stitches/meander_fill.py +++ b/lib/stitches/meander_fill.py @@ -10,6 +10,7 @@ from ..utils import smooth_path from ..utils.geometry import Point as InkStitchPoint, ensure_geometry_collection from ..utils.list import poprandom from ..utils.prng import iter_uniform_floats +from ..utils.threading import check_stop_flag def meander_fill(fill, shape, shape_index, starting_point, ending_point): @@ -83,11 +84,15 @@ def generate_meander_path(graph, start, end, rng): 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) edges_to_consider.extend(replace_edge_pair(meander_path, edge1, edge2, graph, graph_nodes)) break -- cgit v1.2.3 From 9ea61ef3f33b76f199843fff82d1d624903aa11d Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Wed, 8 Feb 2023 14:39:25 -0500 Subject: remove buffer concept --- lib/stitches/meander_fill.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/stitches/meander_fill.py') diff --git a/lib/stitches/meander_fill.py b/lib/stitches/meander_fill.py index 5f399158..ca3b7d69 100644 --- a/lib/stitches/meander_fill.py +++ b/lib/stitches/meander_fill.py @@ -22,7 +22,7 @@ def meander_fill(fill, shape, shape_index, starting_point, ending_point): 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_padding) + graph = tile.to_graph(shape, fill.meander_scale) debug.log_graph(graph, 'Meander graph') debug.log(lambda: f"graph connected? {nx.is_connected(graph)}") start, end = find_starting_and_ending_nodes(graph, shape, starting_point, ending_point) -- cgit v1.2.3 From 9ccf8b9b7780b997c1f801a87dafd99f86f048a1 Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Fri, 17 Feb 2023 21:13:13 -0500 Subject: better smoothing algorithm --- lib/stitches/meander_fill.py | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'lib/stitches/meander_fill.py') diff --git a/lib/stitches/meander_fill.py b/lib/stitches/meander_fill.py index ca3b7d69..2cd235fb 100644 --- a/lib/stitches/meander_fill.py +++ b/lib/stitches/meander_fill.py @@ -6,7 +6,7 @@ from .running_stitch import running_stitch from .. import tiles from ..debug import debug from ..stitch_plan import Stitch -from ..utils import smooth_path +from ..utils.smoothing import smooth_path from ..utils.geometry import Point as InkStitchPoint, ensure_geometry_collection from ..utils.list import poprandom from ..utils.prng import iter_uniform_floats -- cgit v1.2.3 From ae43fb96830d9f747f890d1985a9c5ed4741f893 Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Sat, 18 Feb 2023 17:44:42 -0500 Subject: avoid NetworkXNoPath error by connecting graph --- lib/stitches/meander_fill.py | 32 ++++++++++++++++++++++++++------ 1 file changed, 26 insertions(+), 6 deletions(-) (limited to 'lib/stitches/meander_fill.py') diff --git a/lib/stitches/meander_fill.py b/lib/stitches/meander_fill.py index 2cd235fb..6278b0ad 100644 --- a/lib/stitches/meander_fill.py +++ b/lib/stitches/meander_fill.py @@ -1,3 +1,5 @@ +from itertools import combinations + import networkx as nx from shapely.geometry import MultiPoint, Point from shapely.ops import nearest_points @@ -5,11 +7,11 @@ from shapely.ops import nearest_points from .running_stitch import running_stitch from .. import tiles from ..debug import debug -from ..stitch_plan import Stitch -from ..utils.smoothing import smooth_path +from ..utils.clamp_path import clamp_path_to_polygon from ..utils.geometry import Point as InkStitchPoint, 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 @@ -24,11 +26,11 @@ def meander_fill(fill, shape, shape_index, starting_point, ending_point): debug.log_line_strings(lambda: ensure_geometry_collection(shape.boundary).geoms, 'Meander shape') graph = tile.to_graph(shape, fill.meander_scale) debug.log_graph(graph, 'Meander graph') - debug.log(lambda: f"graph connected? {nx.is_connected(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), fill) + return post_process(generate_meander_path(graph, start, end, rng), shape, fill) def get_tile(tile_name): @@ -40,6 +42,24 @@ def get_tile(tile_name): 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] @@ -137,14 +157,14 @@ def replace_edge_pair(path, edge1, edge2, graph, graph_nodes): @debug.time -def post_process(points, fill): +def post_process(points, 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) - stitches = [Stitch(point) for point in stitches] + stitches = clamp_path_to_polygon(stitches, shape) return stitches -- cgit v1.2.3 From d278f6a54a2a316e70271ad04bd206e49a93fa5f Mon Sep 17 00:00:00 2001 From: Lex Neva Date: Sat, 18 Feb 2023 22:24:58 -0500 Subject: add tiles json and internationalization --- lib/stitches/meander_fill.py | 6 +++--- 1 file changed, 3 insertions(+), 3 deletions(-) (limited to 'lib/stitches/meander_fill.py') diff --git a/lib/stitches/meander_fill.py b/lib/stitches/meander_fill.py index 6278b0ad..964a7a41 100644 --- a/lib/stitches/meander_fill.py +++ b/lib/stitches/meander_fill.py @@ -33,11 +33,11 @@ def meander_fill(fill, shape, shape_index, starting_point, ending_point): return post_process(generate_meander_path(graph, start, end, rng), shape, fill) -def get_tile(tile_name): - all_tiles = {tile.name: tile for tile in tiles.all_tiles()} +def get_tile(tile_id): + all_tiles = {tile.id: tile for tile in tiles.all_tiles()} try: - return all_tiles.get(tile_name, all_tiles.popitem()[1]) + return all_tiles.get(tile_id, all_tiles.popitem()[1]) except KeyError: return None -- cgit v1.2.3