diff options
author | Jack Ha <j.ha@ultimaker.com> | 2017-03-09 12:21:25 +0300 |
---|---|---|
committer | Jack Ha <j.ha@ultimaker.com> | 2017-03-09 12:21:25 +0300 |
commit | 9d6dd1580b94cc27d2937cd0ee94c550ad607a0f (patch) | |
tree | 583c59fd27aa1164036ea7f49762d19fb1b9cf3d /cura/Arrange.py | |
parent | 3be6a0966bf3fdfcf55b1df61f7d27fd2c5d64ad (diff) |
WIP Added first arranger functions. CURA-3239
Diffstat (limited to 'cura/Arrange.py')
-rwxr-xr-x | cura/Arrange.py | 154 |
1 files changed, 154 insertions, 0 deletions
diff --git a/cura/Arrange.py b/cura/Arrange.py new file mode 100755 index 0000000000..986f9110c1 --- /dev/null +++ b/cura/Arrange.py @@ -0,0 +1,154 @@ +import numpy as np + +## Some polygon converted to an array +class ShapeArray: + def __init__(self, arr, offset_x, offset_y, scale = 1): + self.arr = arr + self.offset_x = offset_x + self.offset_y = offset_y + self.scale = scale + + @classmethod + def from_polygon(cls, vertices, scale = 1): + # scale + vertices = vertices * scale + # offset + offset_y = int(np.amin(vertices[:, 0])) + offset_x = int(np.amin(vertices[:, 1])) + # normalize to 0 + vertices[:, 0] = np.add(vertices[:, 0], -offset_y) + vertices[:, 1] = np.add(vertices[:, 1], -offset_x) + shape = [int(np.amax(vertices[:, 0])), int(np.amax(vertices[:, 1]))] + arr = cls.array_from_polygon(shape, vertices) + return cls(arr, offset_x, offset_y) + + ## Return indices that mark one side of the line, used by array_from_polygon + # Uses the line defined by p1 and p2 to check array of + # input indices against interpolated value + + # Returns boolean array, with True inside and False outside of shape + # Originally from: http://stackoverflow.com/questions/37117878/generating-a-filled-polygon-inside-a-numpy-array + @classmethod + def _check(cls, p1, p2, base_array): + """ + """ + if p1[0] == p2[0] and p1[1] == p2[1]: + return + idxs = np.indices(base_array.shape) # Create 3D array of indices + + p1 = p1.astype(float) + p2 = p2.astype(float) + + if p2[0] == p1[0]: + sign = np.sign(p2[1] - p1[1]) + return idxs[1] * sign + + if p2[1] == p1[1]: + sign = np.sign(p2[0] - p1[0]) + return idxs[1] * sign + + # Calculate max column idx for each row idx based on interpolated line between two points + + max_col_idx = (idxs[0] - p1[0]) / (p2[0] - p1[0]) * (p2[1] - p1[1]) + p1[1] + sign = np.sign(p2[0] - p1[0]) + return idxs[1] * sign <= max_col_idx * sign + + @classmethod + def array_from_polygon(cls, shape, vertices): + """ + Creates np.array with dimensions defined by shape + Fills polygon defined by vertices with ones, all other values zero + + Only works correctly for convex hull vertices + """ + base_array = np.zeros(shape, dtype=float) # Initialize your array of zeros + + fill = np.ones(base_array.shape) * True # Initialize boolean array defining shape fill + + # Create check array for each edge segment, combine into fill array + for k in range(vertices.shape[0]): + fill = np.all([fill, cls._check(vertices[k - 1], vertices[k], base_array)], axis=0) + + # Set all values inside polygon to one + base_array[fill] = 1 + + return base_array + + +class Arrange: + def __init__(self, x, y, offset_x, offset_y, scale=1): + self.shape = (y, x) + self._priority = np.zeros((x, y), dtype=np.int32) + self._occupied = np.zeros((x, y), dtype=np.int32) + self._scale = scale # convert input coordinates to arrange coordinates + self._offset_x = offset_x + self._offset_y = offset_y + + ## Fill priority, take offset as center. lower is better + def centerFirst(self): + self._priority = np.fromfunction( + lambda i, j: abs(self._offset_x-i)+abs(self._offset_y-j), self.shape) + + ## Return the amount of "penalty points" for polygon, which is the sum of priority + # 999999 if occupied + def check_shape(self, x, y, shape_arr): + x = int(self._scale * x) + y = int(self._scale * y) + offset_x = x + self._offset_x + shape_arr.offset_x + offset_y = y + self._offset_y + shape_arr.offset_y + occupied_slice = self._occupied[ + offset_y:offset_y + shape_arr.arr.shape[0], + offset_x:offset_x + shape_arr.arr.shape[1]] + if np.any(occupied_slice[np.where(shape_arr.arr == 1)]): + return 999999 + prio_slice = self._priority[ + offset_y:offset_y + shape_arr.arr.shape[0], + offset_x:offset_x + shape_arr.arr.shape[1]] + return np.sum(prio_slice[np.where(shape_arr.arr == 1)]) + + ## Slower but better (it tries all possible locations) + def bestSpot2(self, shape_arr): + best_x, best_y, best_points = None, None, None + min_y = max(-shape_arr.offset_y, 0) - self._offset_y + max_y = self.shape[0] - shape_arr.arr.shape[0] - self._offset_y + min_x = max(-shape_arr.offset_x, 0) - self._offset_x + max_x = self.shape[1] - shape_arr.arr.shape[1] - self._offset_x + for y in range(min_y, max_y): + for x in range(min_x, max_x): + penalty_points = self.check_shape(x, y, shape_arr) + if best_points is None or penalty_points < best_points: + best_points = penalty_points + best_x, best_y = x, y + return best_x, best_y, best_points + + ## Faster + def bestSpot(self, shape_arr): + min_y = max(-shape_arr.offset_y, 0) - self._offset_y + max_y = self.shape[0] - shape_arr.arr.shape[0] - self._offset_y + min_x = max(-shape_arr.offset_x, 0) - self._offset_x + max_x = self.shape[1] - shape_arr.arr.shape[1] - self._offset_x + + for prio in range(200): + tryout_idx = np.where(self._priority == prio) + for idx in range(len(tryout_idx[0])): + x = tryout_idx[0][idx] + y = tryout_idx[1][idx] + projected_x = x - self._offset_x + projected_y = y - self._offset_y + if projected_x < min_x or projected_x > max_x or projected_y < min_y or projected_y > max_y: + continue + # array to "world" coordinates + penalty_points = self.check_shape(projected_x, projected_y, shape_arr) + if penalty_points != 999999: + return projected_x, projected_y, penalty_points + return None, None, None # No suitable location found :-( + + def place(self, x, y, shape_arr): + x = int(self._scale * x) + y = int(self._scale * y) + offset_x = x + self._offset_x + shape_arr.offset_x + offset_y = y + self._offset_y + shape_arr.offset_y + occupied_slice = self._occupied[ + offset_y:offset_y + shape_arr.arr.shape[0], + offset_x:offset_x + shape_arr.arr.shape[1]] + occupied_slice[np.where(shape_arr.arr == 1)] = 1 |