Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

add_rect() in online packers doesn't return solution #27

Open
lordmauve opened this issue Aug 3, 2019 · 31 comments
Open

add_rect() in online packers doesn't return solution #27

lordmauve opened this issue Aug 3, 2019 · 31 comments

Comments

@lordmauve
Copy link

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
Copy link
Owner

secnot commented Aug 4, 2019

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
Copy link

moi90 commented Feb 28, 2021

@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
Copy link
Owner

secnot commented Mar 1, 2021

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
Copy link

moi90 commented Mar 1, 2021

Yes, please, that would be great!

@moi90
Copy link

moi90 commented Mar 2, 2021

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
Copy link
Owner

secnot commented Mar 2, 2021

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
Copy link
Owner

secnot commented Mar 2, 2021

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
Copy link

moi90 commented Mar 2, 2021

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
Copy link

moi90 commented Mar 2, 2021

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

@secnot
Copy link
Owner

secnot commented Mar 2, 2021

Perhaps you only wan't to remove one specific bin

@moi90
Copy link

moi90 commented Mar 2, 2021

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
Copy link
Owner

secnot commented Mar 2, 2021

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
Copy link

moi90 commented Mar 2, 2021

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
Copy link
Owner

secnot commented Mar 2, 2021

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

@moi90
Copy link

moi90 commented Mar 2, 2021

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
Copy link
Owner

secnot commented Mar 2, 2021

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
Copy link

moi90 commented Mar 2, 2021

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

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

@secnot
Copy link
Owner

secnot commented Mar 2, 2021

My mistake, that was my intention

@lordmauve
Copy link
Author

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
Copy link
Owner

secnot commented Mar 2, 2021

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
Copy link
Author

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
Copy link
Owner

secnot commented Mar 2, 2021

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
Copy link

moi90 commented Mar 2, 2021

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
Copy link
Owner

secnot commented Mar 2, 2021

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
Copy link

moi90 commented Mar 2, 2021

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
Copy link
Owner

secnot commented Mar 2, 2021

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
Copy link
Owner

secnot commented Mar 2, 2021

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

@moi90
Copy link

moi90 commented Mar 3, 2021

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
Copy link

moi90 commented Mar 11, 2021

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
Copy link
Owner

secnot commented Mar 11, 2021

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
Copy link

moi90 commented Mar 12, 2021

No problem, thanks for implementing that!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

3 participants