Simple test case
pzach01 opened this issue · 17 comments
Hey, this package is a good idea. However, I tried running a simple test case with one very large bin and a number of items. The solver fails to put them in the bin. I might be missing something though. Test case and result is below:
#TEST CASE:
from py3dbp import Packer, Bin, Item
packer = Packer()
packer.add_bin(Bin('very-very-large-box', 10000.6875, 10000.75, 10000.0, 2000000.0))
packer.add_item(Item('50g [powder 1]', 1.1, 1.9685, 1.9685, 1))
packer.add_item(Item('50g [powder 2]', 1.1, 1.9685, 1.9685, 2))
packer.add_item(Item('50g [powder 3]', 1.1, 1.9685, 1.9685, 3))
packer.add_item(Item('250g [powder 4]', 1.1, 3.9370, 1.9685, 4))
packer.add_item(Item('250g [powder 5]', 7.8740, 3.9370, 1.9685, 5))
packer.add_item(Item('250g [powder 6]', 7.8740, 3.9370, 1.9685, 6))
packer.add_item(Item('250g [powder 7]', 7.8740, 3.9370, 1.9685, 7))
packer.add_item(Item('250g [powder 8]', 7.8740, 3.9370, 1.9685, 8))
packer.add_item(Item('250g [powder 9]', 7.8740, 3.9370, 1.9685, 9))
packer.add_item(Item('50g [powder 10]', 3.9370, 1.9685, 1.9685, 10))
packer.add_item(Item('50g [powder 11]', 3.9370, 1.9685, 1.9685, 11))
packer.add_item(Item('50g [powder 12]', 3.9370, 1.9685, 1.9685, 12))
packer.add_item(Item('250g [powder 12]', 7.8740, 3.9370, 1.9685, 13))
packer.add_item(Item('250g [powder 13]', 7.8740, 3.9370, 1.9685, 14))
packer.add_item(Item('250g [powder 14]', 7.8740, 3.9370, 1.9685, 15))
packer.add_item(Item('250g [powder 15]', 7.8740, 3.9370, 1.9685, 16))
packer.add_item(Item('250g [powder 16]', 1.1, 3.9370, 1.9685, 17))
packer.add_item(Item('250g [powder 17]', 1.8740, 3.9370, 1.9685, 18))
packer.pack()
for b in packer.bins:
print(":::::::::::", b.string())
print("FITTED ITEMS:")
for item in b.items:
print("====> ", item.string())
print("UNFITTED ITEMS:")
for item in b.unfitted_items:
print("====> ", item.string())
print("***************************************************")
print("***************************************************")
RESULT
::::::::::: very-very-large-box(10000.6875x10000.75x10000.0, max_weight:2000000.0) vol(1000143755156.25)
FITTED ITEMS:
====> 50g [powder 1](1.1x1.9685x1.9685, weight: 1) pos([0, 0, 0]) rt(0) vol(4.26)
====> 50g [powder 2](1.1x1.9685x1.9685, weight: 2) pos([1.1, 0, 0]) rt(0) vol(4.26)
====> 50g [powder 3](1.1x1.9685x1.9685, weight: 3) pos([0, 1.9685, 0]) rt(0) vol(4.26)
====> 250g [powder 4](1.1x3.937x1.9685, weight: 4) pos([1.1, 1.9685, 0]) rt(0) vol(8.52)
====> 250g [powder 16](1.1x3.937x1.9685, weight: 17) pos([0, 3.937, 0]) rt(0) vol(8.52)
====> 250g [powder 17](1.874x3.937x1.9685, weight: 18) pos([2.2, 0, 0]) rt(0) vol(14.52)
====> 50g [powder 10](3.937x1.9685x1.9685, weight: 10) pos([1.1, 5.9055, 0]) rt(0) vol(15.26)
====> 50g [powder 11](3.937x1.9685x1.9685, weight: 11) pos([0, 0, 1.9685]) rt(0) vol(15.26)
====> 50g [powder 12](3.937x1.9685x1.9685, weight: 12) pos([3.937, 0, 1.9685]) rt(0) vol(15.26)
====> 250g [powder 5](7.874x3.937x1.9685, weight: 5) pos([5.037, 5.9055, 0]) rt(0) vol(61.02)
====> 250g [powder 6](7.874x3.937x1.9685, weight: 6) pos([7.874, 0, 1.9685]) rt(0) vol(61.02)
====> 250g [powder 7](7.874x3.937x1.9685, weight: 7) pos([0, 1.9685, 1.9685]) rt(0) vol(61.02)
====> 250g [powder 8](7.874x3.937x1.9685, weight: 8) pos([5.037, 9.8425, 0]) rt(0) vol(61.02)
====> 250g [powder 9](7.874x3.937x1.9685, weight: 9) pos([7.874, 3.937, 1.9685]) rt(0) vol(61.02)
====> 250g [powder 12](7.874x3.937x1.9685, weight: 13) pos([0, 5.9055, 1.9685]) rt(0) vol(61.02)
====> 250g [powder 13](7.874x3.937x1.9685, weight: 14) pos([0, 9.8425, 1.9685]) rt(0) vol(61.02)
====> 250g [powder 14](7.874x3.937x1.9685, weight: 15) pos([7.874, 9.8425, 1.9685]) rt(0) vol(61.02)
UNFITTED ITEMS:
====> 250g [powder 15](7.874x3.937x1.9685, weight: 16) pos([0, 0, 0]) rt(0) vol(61.02)
I replaced the floating point values with integers and it appears to solve correctly. Hope this helps to diagnose the issue.
Good clue, Jon. Forgive me if I am stating the obvious but I suspect the issue is related to this: https://docs.python.org/3/tutorial/floatingpoint.html
I changed auxiliary methods line 16 from
return ix < (d1[x]+d2[x])/2 and iy < (d1[y]+d2[y])/2
to this:
return round(ix, 6) < round((d1[x]+d2[x])/2, 6) and round(iy, 6) < round((d1[y]+d2[y])/2, 6)
It seems to solve correctly with some position round-off error. I don't necessarily propose this as a solution but it might help diagnose the issue further.
Thanks @pzach01. Yes, I also got all items to fit using the Decimal module in auxiliary_methods.py, with precision set to 60 digits, like this:
from decimal import *
getcontext().prec = 60
def rect_intersect(item1, item2, x, y):
d1 = item1.get_dimension()
d2 = item2.get_dimension()
cx1 = Decimal(item1.position[x]) + Decimal(d1[x])/Decimal(2)
cy1 = Decimal(item1.position[y]) + Decimal(d1[y])/Decimal(2)
cx2 = Decimal(item2.position[x]) + Decimal(d2[x])/Decimal(2)
cy2 = Decimal(item2.position[y]) + Decimal(d2[y])/Decimal(2)
ix = max(cx1, cx2) - min(cx1, cx2)
iy = max(cy1, cy2) - min(cy1, cy2)
return ix < Decimal(d1[x]+d2[x])/Decimal(2) and iy < Decimal(d1[y]+d2[y])/Decimal(2)
Using different precision levels yields very different packing results, however. For example, using 25 digits of precision (setting getcontext().prec to 25), makes nearly half of the items not fit:
::::::::::: very-very-large-box(10000.6875x10000.75x10000.0, max_weight:2000000.0) vol(1000143755156.25)
FITTED ITEMS:
====> 250g [powder 5](7.874x3.937x1.9685, weight: 5) pos([0, 0, 0]) rt(0) vol(61.02)
====> 250g [powder 6](7.874x3.937x1.9685, weight: 6) pos([0, 3.937, 0]) rt(0) vol(61.02)
====> 250g [powder 7](7.874x3.937x1.9685, weight: 7) pos([0, 7.874, 0]) rt(0) vol(61.02)
====> 250g [powder 8](7.874x3.937x1.9685, weight: 8) pos([0, 11.811, 0]) rt(0) vol(61.02)
====> 250g [powder 9](7.874x3.937x1.9685, weight: 9) pos([0, 0, 1.9685]) rt(0) vol(61.02)
====> 250g [powder 12](7.874x3.937x1.9685, weight: 13) pos([0, 3.937, 1.9685]) rt(0) vol(61.02)
====> 250g [powder 13](7.874x3.937x1.9685, weight: 14) pos([0, 7.874, 1.9685]) rt(0) vol(61.02)
====> 250g [powder 14](7.874x3.937x1.9685, weight: 15) pos([0, 11.811, 1.9685]) rt(0) vol(61.02)
====> 250g [powder 17](1.874x3.937x1.9685, weight: 18) pos([7.874, 0, 0]) rt(0) vol(14.52)
UNFITTED ITEMS:
====> 250g [powder 15](7.874x3.937x1.9685, weight: 16) pos([0, 0, 0]) rt(0) vol(61.02)
====> 50g [powder 10](3.937x1.9685x1.9685, weight: 10) pos([0, 0, 0]) rt(0) vol(15.26)
====> 50g [powder 11](3.937x1.9685x1.9685, weight: 11) pos([0, 0, 0]) rt(0) vol(15.26)
====> 50g [powder 12](3.937x1.9685x1.9685, weight: 12) pos([0, 0, 0]) rt(0) vol(15.26)
====> 250g [powder 4](1.1x3.937x1.9685, weight: 4) pos([0, 0, 0]) rt(0) vol(8.52)
====> 250g [powder 16](1.1x3.937x1.9685, weight: 17) pos([0, 0, 0]) rt(0) vol(8.52)
====> 50g [powder 1](1.1x1.9685x1.9685, weight: 1) pos([0, 0, 0]) rt(0) vol(4.26)
====> 50g [powder 2](1.1x1.9685x1.9685, weight: 2) pos([0, 0, 0]) rt(0) vol(4.26)
====> 50g [powder 3](1.1x1.9685x1.9685, weight: 3) pos([0, 0, 0]) rt(0) vol(4.26)
Changing the floating point precision seems to cause the positions of the packed items to vary significantly.
In main.py, I added the decimal function to the width, height depth properties and tweaked the string method. I think this looks good; @jon-abbott can you verify? If this looks like a winner maybe it should be extended to the Bin class as well. The changes are below:
from .constants import RotationType, Axis
from .auxiliary_methods import intersect
from decimal import *
getcontext().prec = 6
getcontext().rounding = ROUND_UP
START_POSITION = [0, 0, 0]
class Item:
def init(self, name, width, height, depth, weight):
self.name = name
self.width = Decimal(width)
self.height = Decimal(height)
self.depth = Decimal(depth)
self.weight = weight
self.rotation_type = 0
self.position = START_POSITION
self.volume = self.get_volume()
def string(self):
return "%s(%fx%fx%f, weight: %s) pos(%f, %f, %f) rt(%s) vol(%s)" % (
self.name, self.width, self.height, self.depth, self.weight,
self.position[0], self.position[1], self.position[2], self.rotation_type, self.volume
)
@pzach01, that change causes the output on mine to show lots of digits after the decimal point (example: 7.87399999999999966604491419275291264057159423828125). That was after ensuring the precision is set to six digits in both main.py and auxiliary_methods.py. Not sure what else to try for now... but am subscribed to follow the discussion.
Remove the changes to auxiliary_methods. The only modification is to main.py.
I did that, and the first time I run it in Jupyter Notebook, the volumes shown are six significant digits (e.g. 61.0235), but the second time I run it, the precision is reverting to the Decimal default (e.g. 61.02337795299999223555978389) for some reason. I'm just re-running the same cell.
hmmm, I don't know. I don't know why the results would vary from trial to trial. I am getting repeatable and seemingly correct results running in vs code.
Would it make sense to multiply out to x digits, I needed precision of 3, with Jon's initial suggestion I ended up multiplying all my data points by a 1000 and then doing a division at the end, definitely not the optimal solution but it did work.
@nchaudh03 , yes, I think this is a reasonable workaround. The documentation should be updated if this is the preferred workflow. I had success modifying the Item class as shown above.
I also encountered an issue with floating point comparisons
Even with a simple example like the following
packer.add_bin(Bin('large-envelope', 15.0, 12.0, 2.0, 15.0))
packer.add_item(Item('test', 12.0, 10.0, 0.7, 1.0))
packer.add_item(Item('test2', 12.0, 10.0, 0.7, 1.0))
At, "rect_intersect" in auxillary methods it would compare two floats which should be exactly the same (0.7) in the return line. After analysis with decimal as said by @jon-abbott , the floats were becoming 0.69999999999999984456877655247808434069156646728515625 and 0.6999999999999999555910790149937383830547332763671875 for example. So one would return True.
I feel this is probably a python issue, I've only just found out about this issue and had never encountered it before. I guess the best fix is to round, or ceil floats.
I am testing this on a Vagrant virtual development environment, running CentOS 7. I wonder if the instability of devbox is introducing these issues.
@corbinjurgens , I had success modifying the Item class in main.py like this:
from .constants import RotationType, Axis
from .auxiliary_methods import intersect
from decimal import *
getcontext().prec = 6
getcontext().rounding = ROUND_UP
START_POSITION = [0, 0, 0]
class Item:
def init(self, name, width, height, depth, weight):
self.name = name
self.width = Decimal(width)
self.height = Decimal(height)
self.depth = Decimal(depth)
self.weight = weight
self.rotation_type = 0
self.position = START_POSITION
self.volume = self.get_volume()
def string(self):
return "%s(%fx%fx%f, weight: %s) pos(%f, %f, %f) rt(%s) vol(%s)" % (
self.name, self.width, self.height, self.depth, self.weight,
self.position[0], self.position[1], self.position[2], self.rotation_type, self.volume
)
I intend to try your workaround and see if it can work for me. I will post results again
Looks like this fix wont help me as Decimal simply isn't working as intended (unless I'm missing something), so this must be a issue with Python itself. I tried your advice with my test, and it didn't work. After testing I found:
For example, the following code:
from decimal import *
getcontext().prec = 6
getcontext().rounding = ROUND_UP
print(getcontext())
print(Decimal(0.7))
Results in
Context(prec=6, rounding=ROUND_UP, Emin=-999999999, Emax=999999999, capitals=1, flags=[], traps=[Overflow, InvalidOperation, DivisionByZero])
0.6999999999999999555910790149937383830547332763671875
And just to show, the results of rect_intersect at the 0.7 digit that causes the issue
iy < (d1[y]+d2[y])/2
is becoming
0.6999999999999999555910790145 < 0.699999999999999955591079015
Which I believe is less decimal places than was appearing for me before.
My fix will be just working in millimeters (as we aren't restricted to any specific measurement in this code), and only using integers
I will be using this 3d bin pack code heavily dependent on other code anyway, so I decided to make a wrapper for the bin packer, that way I can leave the pip install untouched.
Feel free to use this and change the self.Measurement and self.Weight to any numer that represents your desired decimal place level based on what you are inputting. In my case I input cm/kg and it changes it to mm/g
Also, it will floor Bin and ceil Item measureents, so that if there is a difference of 1 fraction its better to be safe and not allow it to fit.
from py3dbp import Packer, Bin, Item
import math
class binpackwrap(object):
"""3d Bin back py3dbp wrapper"""
def __init__(self, app):
super(binpackwrap, self).__init__()
self.app = app
self.Measurement = 10
self.Weight = 1000
def Item(self, name, width, height, depth, weight):
# Name (string or not is ok), Width mm, Height mm, Depth mm, Weight g
return Item(name, math.ceil(width * self.Measurement), math.ceil(height * self.Measurement), math.ceil(depth * self.Measurement), math.ceil(weight * self.Weight) )
def Bin(self, name, width, height, depth, max_weight):
# Name (string or not is ok), Width mm, Height mm, Depth mm, Weight g
return Bin(name, math.floor(width * self.Measurement), math.floor(height * self.Measurement), math.floor(depth * self.Measurement), math.floor(max_weight * self.Weight) )
def test(self):
packer = Packer()
packer.add_bin(self.Bin('large-envelope', 15.0, 12.0, 4.0, 15))
packer.add_item(self.Item('test', 15.0, 10.0, 0.7, 1))
packer.add_item(self.Item('test2', 15.0, 10.0, 0.7, 1))
packer.pack()
for b in packer.bins:
print(":::::::::::")
print(b.string())
print("FITTED ITEMS:")
for item in b.items:
print("====> ", item.string())
print("UNFITTED ITEMS:")
for item in b.unfitted_items:
print("====> ", item.string())
print("***************************************************")
print("***************************************************")
Hi @pzach01 @jon-abbott @nchaudh03 @corbinjurgens , i uploaded a new version (v1.1) to handle the limit of decimals that in theory fix the origin of this issue.
Please take a look of the new version and if there are a new problem let us know by creating a new ticket.
Greetings!!