1import time
2import numpy as np
3
4from ..constants import log
5from ..constants import tol_path as tol
6
7
8class RectangleBin:
9    """
10    2D BSP tree node.
11    http://www.blackpawn.com/texts/lightmaps/
12    """
13
14    def __init__(self, bounds=None, size=None):
15        """
16        Create a rectangular bin.
17
18        Parameters
19        ------------
20        bounds : (4,) float or None
21          (minx, miny, maxx, maxy)
22        size : (2,) float or None
23          Alternative method to set bounds
24          (X size, Y size)
25        """
26        self.child = [None, None]
27        self.occupied = False
28
29        # bounds: (minx, miny, maxx, maxy)
30        if bounds is not None:
31            self.bounds = np.asanyarray(bounds,
32                                        dtype=np.float64)
33        elif size is not None:
34            self.bounds = np.append([0.0, 0.0],
35                                    size).astype(np.float64)
36        else:
37            raise ValueError('need to pass size or bounds!')
38
39    @property
40    def extents(self):
41        """
42        Bounding box size.
43
44        Returns
45        ----------
46        extents: (2,) float, edge lengths of bounding box
47        """
48        extents = np.subtract(*self.bounds.reshape((2, 2))[::-1])
49        return extents
50
51    def insert(self, rectangle):
52        """
53        Insert a rectangle into the bin.
54
55        Parameters
56        -------------
57        rectangle: (2,) float, size of rectangle to insert
58        """
59        rectangle = np.asanyarray(rectangle, dtype=np.float64)
60
61        for child in self.child:
62            if child is not None:
63                attempt = child.insert(rectangle)
64                if attempt is not None:
65                    return attempt
66
67        if self.occupied:
68            return None
69
70        # compare the bin size to the insertion candidate size
71        size_test = self.extents - rectangle
72
73        # this means the inserted rectangle is too big for the cell
74        if np.any(size_test < -tol.zero):
75            return None
76
77        # since the cell is big enough for the current rectangle, either it
78        # is going to be inserted here, or the cell is going to be split
79        # either way, the cell is now occupied.
80        self.occupied = True
81
82        # this means the inserted rectangle fits perfectly
83        # since we already checked to see if it was negative, no abs is needed
84        if np.all(size_test < tol.zero):
85            return self.bounds[0:2]
86
87        # since the rectangle fits but the empty space is too big,
88        # we need to create some children to insert into
89        # first, we decide which way to split
90        vertical = size_test[0] > size_test[1]
91        length = rectangle[int(not vertical)]
92        child_bounds = self.split(length, vertical)
93
94        self.child[0] = RectangleBin(bounds=child_bounds[0])
95        self.child[1] = RectangleBin(bounds=child_bounds[1])
96
97        return self.child[0].insert(rectangle)
98
99    def split(self, length, vertical=True):
100        """
101        Returns two bounding boxes representing the current
102        bounds split into two smaller boxes.
103
104        Parameters
105        -------------
106        length:   float, length to split
107        vertical: bool, if True will split box vertically
108
109        Returns
110        -------------
111        box: (2,4) float, two bounding boxes consisting of:
112                          [minx, miny, maxx, maxy]
113        """
114        # also know as [minx, miny, maxx, maxy]
115        [left, bottom, right, top] = self.bounds
116        if vertical:
117            box = [[left, bottom, left + length, top],
118                   [left + length, bottom, right, top]]
119        else:
120            box = [[left, bottom, right, bottom + length],
121                   [left, bottom + length, right, top]]
122        return box
123
124
125def pack_rectangles(rectangles, sheet_size, shuffle=False):
126    """
127    Pack smaller rectangles onto a larger rectangle, using a binary
128    space partition tree.
129
130    Parameters
131    ----------
132    rectangles : (n, 2) float
133      An array of (width, height) pairs
134      representing the rectangles to be packed.
135    sheet_size : (2,) float
136      Width, height of rectangular sheet
137    shuffle : bool
138      Whether or not to shuffle the insert order of the
139      smaller rectangles, as the final packing density depends
140      on insertion order.
141
142    Returns
143    ---------
144    density : float
145      Area filled over total sheet area
146    offset :  (m,2) float
147      Offsets to move rectangles to their packed location
148    inserted : (n,) bool
149      Which of the original rectangles were packed
150    consumed_box : (2,) float
151      Bounding box size of packed result
152    """
153    offset = np.zeros((len(rectangles), 2))
154    inserted = np.zeros(len(rectangles), dtype=np.bool)
155    box_order = np.argsort(np.sum(rectangles**2, axis=1))[::-1]
156    area = 0.0
157    density = 0.0
158
159    if shuffle:
160        shuffle_len = int(np.random.random() * len(rectangles)) - 1
161        box_order[0:shuffle_len] = np.random.permutation(
162            box_order[0:shuffle_len])
163
164    sheet = RectangleBin(size=sheet_size)
165    for index in box_order:
166        insert_location = sheet.insert(rectangles[index])
167        if insert_location is not None:
168            area += np.prod(rectangles[index])
169            offset[index] += insert_location
170            inserted[index] = True
171
172    consumed_box = np.max((offset + rectangles)[inserted], axis=0)
173    density = area / np.product(consumed_box)
174
175    return density, offset[inserted], inserted, consumed_box
176
177
178def pack_paths(paths, sheet_size=None):
179    """
180    Pack a list of Path2D objects into a rectangle.
181
182    Parameters
183    ------------
184    paths: (n,) Path2D
185      Geometry to be packed
186
187    Returns
188    ------------
189    packed : trimesh.path.Path2D
190      Object containing input geometry
191    inserted : (m,) int
192      Indexes of paths inserted into result
193    """
194    from .util import concatenate
195
196    if sheet_size is not None:
197        sheet_size = np.sort(sheet_size)[::-1]
198
199    quantity = []
200    for path in paths:
201        if 'quantity' in path.metadata:
202            quantity.append(path.metadata['quantity'])
203        else:
204            quantity.append(1)
205
206    # pack using exterior polygon (will OBB)
207    polygons = [i.polygons_closed[i.root[0]] for i in paths]
208
209    # pack the polygons using rectangular bin packing
210    inserted, transforms = multipack(polygons=polygons,
211                                     quantity=quantity,
212                                     sheet_size=sheet_size)
213
214    multi = []
215    for i, T in zip(inserted, transforms):
216        multi.append(paths[i].copy())
217        multi[-1].apply_transform(T)
218
219    # append all packed paths into a single Path object
220    packed = concatenate(multi)
221
222    return packed, inserted
223
224
225def multipack(polygons,
226              sheet_size=None,
227              iterations=50,
228              density_escape=.95,
229              spacing=0.094,
230              quantity=None):
231    """
232    Pack polygons into a rectangle by taking each Polygon's OBB
233    and then packing that as a rectangle.
234
235    Parameters
236    ------------
237    polygons : (n,) shapely.geometry.Polygon
238      Source geometry
239    sheet_size : (2,) float
240      Size of rectangular sheet
241    iterations : int
242      Number of times to run the loop
243    density_escape : float
244      When to exit early (0.0 - 1.0)
245    spacing : float
246      How big a gap to leave between polygons
247    quantity : (n,) int, or None
248      Quantity of each Polygon
249
250    Returns
251    -------------
252    overall_inserted : (m,) int
253      Indexes of inserted polygons
254    packed : (m, 3, 3) float
255      Homogeonous transforms from original frame to packed frame
256    """
257
258    from .polygons import polygons_obb
259
260    if quantity is None:
261        quantity = np.ones(len(polygons), dtype=np.int64)
262    else:
263        quantity = np.asanyarray(quantity, dtype=np.int64)
264    if len(quantity) != len(polygons):
265        raise ValueError('quantity must match polygons')
266
267    # find the oriented bounding box of the polygons
268    obb, rectangles = polygons_obb(polygons)
269
270    # pad all sides of the rectangle
271    rectangles += 2.0 * spacing
272    # move the OBB transform so the polygon is centered
273    # in the padded rectangle
274    for i, r in enumerate(rectangles):
275        obb[i][0:2, 2] += r * .5
276
277    # for polygons occurring multiple times
278    indexes = np.hstack([np.ones(q, dtype=np.int64) * i
279                         for i, q in enumerate(quantity)])
280    # stack using advanced indexing
281    obb = obb[indexes]
282    rectangles = rectangles[indexes]
283
284    # store timing
285    tic = time.time()
286    overall_density = 0.0
287
288    # if no sheet size specified, make a large one
289    if sheet_size is None:
290        max_dim = np.max(rectangles, axis=0)
291        sum_dim = np.sum(rectangles, axis=0)
292        sheet_size = [sum_dim[0], max_dim[1] * 2]
293
294    log.debug('packing %d polygons', len(polygons))
295    # run packing for a number of iterations, shuffling insertion order
296    for i in range(iterations):
297        (density,
298         offset,
299         inserted,
300         sheet) = pack_rectangles(rectangles,
301                                  sheet_size=sheet_size,
302                                  shuffle=(i != 0))
303        if density > overall_density:
304            overall_density = density
305            overall_offset = offset
306            overall_inserted = inserted
307            if density > density_escape:
308                break
309
310    toc = time.time()
311    log.debug('packing finished %i iterations in %f seconds',
312              i + 1,
313              toc - tic)
314    log.debug('%i/%i parts were packed successfully',
315              np.sum(overall_inserted),
316              quantity.sum())
317    log.debug('final rectangular density is %f.', overall_density)
318
319    # transformations to packed positions
320    packed = obb[overall_inserted]
321    # apply the offset and inter- polygon spacing
322    packed.reshape(-1, 9)[:, [2, 5]] += overall_offset + spacing
323
324    return indexes[overall_inserted], packed
325