add_rect() in online packers doesn't return solution

[lordmauve]

I am using the online packer and calling add_rect() when needed. However, the return value is inconsitent and never complete. The only way to get the full solution seems to be to iterate all bins which is O(n) for n rects packed so far. The solution is available and could be returned, but...

• BBF returns bool indicating whether packing succeeded.
• BNF and BBF return a rect if successful or None otherwise - but not the bin ID it was packed into.

I would suggest changing the return value for all three to a tuple of the form (bin_id, rect).

[secnot]

You are right it increases the complexity if you need to check the result after adding each rectangle, and I suppose anyone using and online mode does it just for that reason.

Also add_rect return values are inconsistent when using online mode.

It looks like it is an easy fix, I'll try to test and update the package next week

Thank you

[moi90]

@secnot Did you succeed? I'm interested in using the online packing feature. I would like to add rects continously and every time a bin gets closed, I'd like to remove it from the packer and add a new empty one. Is that possible with the current implementation?

[secnot]

I fixed it, but didn't commit because the change in the interface broke some unrelated software, so I left it for a future revision.

If you really need the functionality I can commit into a branch.

[moi90]

Yes, please, that would be great!

[moi90]

Maybe we don't need to break the API at all. A pop_closed or something could be added to the packer that pops and returns closed bins from the closed bins deque. This should do the desired thing and not break anything, or am I overlooking something? Should I start a pull request?

[secnot]

I couldn't find the previous fix so I'm now fixing add_rect(), and then a callback to receive closed bin notifications or pop_closed as you sugest.

[secnot]

I will finish it today, the TODO list is more or less:

• Generate unique identifier for each bin created
• add_rect() must return (bin_id, rectangle) or (None, None) in all modes
• Iterator over closed bins
• Pop(bin_id) to extract one of the closed bins

[moi90]

Great, I'm looking forward to your solution! But if you don't find the time, I can also work on it.

I would like to use it in a generator that consumes rects and produces packed bins:

# rects: (possibly) infinite generator of rects
for rect in rects:
    packer.add_rect()

    # See if a bin was closed by adding the rect
    bin = packer.pop_closed()
    if bin is not None:
        yield bin
        # Add a new empty bin
        packer.add_bin(...)

In my special case, pop_closed would be more convenient, but a callback would work as well. It is important not to create memory leaks, so closed bins must be removed.

[moi90]

I wouldn't do Pop(bin_id), just pop(). Why waste time on a lookup?

[secnot]

Perhaps you only wan't to remove one specific bin

[moi90]

I my case I would need to do something like bin_id = next(packer.iter_bins()); packer.pop(bin_id) instead of just packer.pop(). Is there a specific use case that calls for a more flexible (but less efficient) two-step solution?

[secnot]

Now that i have written it I can't see many cases where pop(bin_id) would be useful, a simple pop() should be enough and not require an ordereddict

[moi90]

Yes, I would make the general case fast. If a user wants to mess with individual bins by ID, one could implement get_bin() and del_bin() or something like that (or even implement the whole MutableMapping interface).

[secnot]

Are you using python3?, I have been programming golang a month straight, and jut realized that I have added type annotations everywhere ...

[moi90]

Yes, Python3. Type annotations are great :) Guessing from your .travis.yml, you support 3.4 onward. I think you can drop support for Python3.4, so this shouldn't be a problem.

[secnot]

First version committed in branch fix-online-mode , I think you can test it for now:

• pop_closed raises IndexError when no bins are available following deque behavior
• the bin parameter 'bid' is now bid_prefix, if provided the id is a string bid_prefix+uuid4() otherwise just an uuid4()
• type hinting is not finished yet
• Needs a few more tests

Will continue this afternoon.

[moi90]

Cool! I can't wait to try it out.

I suggest using self._closed_bins.popleft() instead of pop so it is FIFO.

[secnot]

My mistake, that was my intention

[lordmauve]

Why uuid4 and not just sequential integer IDs? It's surely unnecessary to need global unique identifiers, and they're much more expensive to compute.

[secnot]

Whenever possible I assign unpredictable IDs, there are many subtle errors and exploits that can arise otherwise, for example if you use integers the id could be incremented by error somewhere and the result would be wrong and very difficult to debug.

There is also security concerns, if the IDs are exposed by an external API, being able to predict them could be exploited.

You could use random integers but the range is not big enough to assure there are no collisions, and it is safer to return strings that aren't modified as easily.

For rectpack in particular:

• Sequential ids would require a global counter per packer instead of a BinFactory assigning the ids.
• Sequential IDs are confusing when the bins returned doesn't have sequential ids.
• Using global unique IDs makes simpler handling several packers returning bins.
• The number of bins is much smaller than the number of rectangles in almost all cases, so the performance hit is small
• Any computer can generate 100K UUID4 per second without problems

I have been bitten by sequential IDs enough times to have strong opinions :), using random integers is not much better.

[lordmauve]

Unpredictable IDs certainly have their uses, but this is far outside the scope of the library. This library just needs to provide algorithm implementations that are as efficient as possible, and other developers who are building on top of it and who might be exposing it over an API can deal with security considerations. In my case I'm using rectangle packing algorithms to pack sprites into texture atlases, so I just need it to be as fast as possible. UUIDs are 50x slower than integers:

$ python3 -m timeit -s "from uuid import uuid4" "uuid4()"
100000 loops, best of 5: 3.43 usec per loop
$ python3 -m timeit -s "from itertools import count; c = count()" "next(c)"
5000000 loops, best of 5: 68.1 nsec per loop

I have been bitten by sequential IDs enough times to have strong opinions

But clearly in a context involving security and predictability. You can't be afraid of using sequential indices in an algorithmic context. Integer IDs are fundamental - they're the indices of a list, for example.

Anyway, I dropped rectpack and implemented my own rectangle packing for my game engine a couple of weeks after opening this issue, so I don't have a stake here. I don't think it's wise to use UUID4s here, but it doesn't affect me.

[secnot]

Ha ha ha, I don't use the library either, I just maintain it because I hate when libraries I'm using are left to rot.

Anyway I will test int and uuid4 in a few cases, if there is a big difference I will change it.

[moi90]

Ha ha ha, I don't use the library either, I just maintain it because I hate when libraries I'm using are left to rot.

@secnot That is very honorable of you, thank you very much!

[secnot]

I don't know if it's honorable or stubborn, but it is funny us discussing the best implementation for a library in which you have no stake, and mine is no to break many things.

We differ in our solution mainly because your point of view is that of a game developer, and mine industrial automation, for you performance is critical, for me avoiding bugs and errors is the most important.

[moi90]

BNF is the only bin_algo that ever closes bins, right? Then, it would be great if I could close the oldest bin myself:

def close_oldest(self):
    self._closed_bins.append(self._open_bins.popleft())

BNF produces suboptimal results (bins only half full), BBF looks nice but never closes bins. Therefore, I currently close the oldest bin manually and add a new one whenever a rect does not fit (add_rect(...) == (None, None)).

[secnot]

I also works well closing bins when more that a threshold of the surface is used, and it is not the last or two last opened.

[secnot]

Or you could set a max number of open bins, and close the oldest one when another one is opened.

[moi90]

Or you could set a max number of open bins, and close the oldest one when another one is opened.

Yes, this is exactly what I'm doing:

            packer = rectpack.newPacker(
                mode=rectpack.PackingMode.Online,
                bin_algo=rectpack.PackingBin.BBF,
                rotation=False,
            )

            for _ in range(self.n_bins):
                packer.add_bin(width=self.width, height=self.height)

            for obj_id, obj in enumerate(stream):
                ...

                # Add rectangle to packer
                rectangle = packer.add_rect(width, height, rid=obj_id)[1]
                if rectangle is None:
                    # print(f"Could not pack {width}x{height}")
                    # continue
                    # Close oldest bin
                    packer._closed_bins.append(packer._open_bins.popleft())
                    # Add a new bin
                    packer.add_bin(width=self.width, height=self.height)
                    # Try again
                    rectangle = packer.add_rect(width, height, rid=obj_id)[1]
                    if rectangle is None:
                        print(f"Could not pack {width}x{height}")

                try:
                    bin = packer.pop_closed()
                except IndexError:

                yield ... # Yield objects packed into a bin

[moi90]

What I don't like about my solution is that I have to access private properties of the packer: packer._closed_bins.append(packer._open_bins.popleft()). Therefore, I proposed the close_oldest method.

[secnot]

I have been swamped with work this week so I couldn't finish the update, but the idea is to assign each bin an unique id by the packer bid, separate from the optional user assigned id uid. Then the method close_bin can close bins by their id, or if no id is provided close the oldest one.

close_bin(bid: Optional[int] = None) -> Union[PackingAlgorithm, None]

It returns the closed bin or None if no bin was closed.

[moi90]

No problem, thanks for implementing that!