1from typing import List, Dict
2from collections import OrderedDict
3from math import degrees
4
5from numpy import isclose
6import networkx as nx
7
8from .common import Line
9from ..geometry.geometry import (
10 right_handed,
11 fix_degen_points,
12 inclination_angle,
13 round_segment,
14 round_point
15)
16from ..helpers.graph import get_cycles, is_cycle, is_open_walk, edges2nodes
17from ..settings.settings import defaults
18
19def _merge_shapes(
20 self,
21 n_round: int = None, **kwargs) -> "Batch":
22 """
23 Tries to merge the shapes in the batch. Returns a new batch
24 with the merged shapes as well as the shapes that could not be merged.
25
26 Args:
27 n_round (int, optional): Number of rounding digits for merging shapes. Defaults to None.
28 **kwargs: Additional keyword arguments.
29
30 Returns:
31 Batch: A new batch with the merged shapes.
32 """
33 from .batch import Batch
34 from .shape import Shape
35 n_round = defaults['n_round'] if n_round is None else n_round
36 self._set_node_dictionaries(self.all_vertices, n_round=n_round)
37 edges, segments = self._get_edges_and_segments(n_round=n_round)
38 segments = self._merge_collinears(edges, n_round=n_round)
39 d_coord_node = self.d_coord_node
40 d_node_coord = self.d_node_coord
41 edges = [[d_coord_node[coord] for coord in seg] for seg in segments]
42 nx_graph = nx.Graph()
43 nx_graph.update(edges)
44 cycles = get_cycles(edges)
45 new_shapes = []
46 if cycles:
47 for cycle in cycles:
48 if len(cycle) < 3:
49 continue
50 nodes = cycle
51 vertices = [d_node_coord[node] for node in nodes]
52 if not right_handed(vertices):
53 vertices.reverse()
54 shape = Shape(vertices, closed=True)
55 new_shapes.append(shape)
56 islands = list(nx.connected_components(nx_graph))
57 if islands:
58 for island in islands:
59 if is_cycle(nx_graph, island):
60 continue
61 if is_open_walk(nx_graph, island):
62 island = list(island)
63 edges = [
64 edge
65 for edge in list(nx_graph.edges)
66 if edge[0] in island and edge[1] in island
67 ]
68 nodes = edges2nodes(edges)
69 vertices = [d_node_coord[node] for node in nodes]
70 if not right_handed(vertices):
71 vertices.reverse()
72 shape = Shape(vertices)
73 new_shapes.append(shape)
74
75 batch = Batch(new_shapes)
76 for k, v in kwargs.items():
77 batch.set_attribs(k, v)
78
79 return batch
80
81
82def _merge_collinears(
83 self,
84 edges: List[Line],
85 angle_bin_size: float = 0.1,
86 n_round: int = 2,
87) -> List[Line]:
88 """
89 Merge collinear edges.
90
91 Args:
92 edges (List[Line]): List of edges.
93 angle_bin_size (float, optional): Bin size for grouping angles. Defaults to 0.1.
94 n_round (int, optional): Number of rounding digits. Defaults to 2.
95 Returns:
96 List[Line]: List of merged edges.
97 """
98
99
100 def merge_bin(_bin:list, d_node_coord:dict, d_coord_node: dict, n_round:int=2):
101 '''Merge collinear edges in a bin.
102
103 Args:
104 _bin (list): List of edges in a bin.
105 d_node_coord (dict): Dictionary of node id to coordinates.
106 n_round (int, optional): Number of rounding digits. Defaults to 2.
107
108 Returns:
109 list: List of merged edges.
110 '''
111 segs = [[d_node_coord[node] for node in x[i_edge]] for x in bin_]
112 incl_angle = degrees(_bin[0][0])
113 if 45 < incl_angle < 135:
114 # sort by y coordinates
115 segs.sort(key=lambda x: x[0][1])
116 else:
117 # sort by x coordinates
118 segs.sort(key=lambda x: x[0][0])
119
120 seg_ids = []
121 for seg in segs:
122 p1, p2 = seg
123 seg_ids.append([d_coord_node[p1], d_coord_node[p2]])
124
125 graph = nx.Graph()
126 graph.add_edges_from(seg_ids)
127 islands = list(nx.connected_components(graph))
128 res = []
129 for island in islands:
130 island = list(island)
131 if len(island) > 1:
132
133 island = [d_node_coord[x] for x in island]
134 if 45 < incl_angle < 135:
135 # sort by y coordinates
136 island.sort(key=lambda x: x[1])
137 else:
138 # sort by x coordinates
139 segs.sort(key=lambda x: x[0][0])
140 island.sort()
141 res.append((island[0], island[-1]))
142 else:
143 res.append(d_node_coord[island[0]])
144
145 return res
146
147 d_node_coord = self.d_node_coord
148 d_coord_node = self.d_coord_node
149 if len(edges) < 2:
150 return edges
151
152 angles_edges = []
153 i_angle, i_edge = 0, 1
154 for edge in edges:
155 edge = list(edge)
156 p1 = d_node_coord[edge[0]]
157 p2 = d_node_coord[edge[1]]
158 angle = inclination_angle(p1, p2)
159 angles_edges.append((angle, edge))
160
161 # group angles into bins
162 angles_edges.sort()
163
164 bins = []
165 bin_ = [angles_edges[0]]
166 for angle, edge in angles_edges[1:]:
167 angle1 = bin_[0][i_angle]
168 if abs(angle - angle1) <= angle_bin_size:
169 bin_.append((angle, edge))
170 else:
171 bins.append(bin_)
172 bin_ = [(angle, edge)]
173 bins.append(bin_)
174
175 res = []
176 for bin_ in bins:
177 res.extend(merge_bin(bin_, d_node_coord, d_coord_node, n_round=n_round))
178
179 return res