adamreis/watermelon — pull request #12 by Aalk4308 (2014-11-01 19:49:59+00:00)
Title: Best known packing

Added a packing implementation that uses the reference site with the best known packings for squares up to (50x50). That's already 17mb of data. It would be easy to add more if we care about even larger fields.

NOTE: We should patch the solution constructor to handle the case when a packing algorithm returns an empty or null list.

At the moment, it just chops of the biggest square possible from the rectangular field, looks up and places the circles for the best known packing, removes those that intersect trees, and fills in any remaining space with a physical packing. (Remaining space exists because the field was a rectangle and because, having naively removed those intersecting trees, we may actually be able to squeeze some that we removed back in.)

The current implementation does not (yet) try to be intelligent in aligning the best known packing with trees so as to reduce their impact. That would be pretty tricky and probably not that valuable anyway.

The current implementation also does not (yet) try different orientations of the best known packing (rotating it or flipping on an axis), which could reduce the impact of trees in some cases. That would be pretty easy to add though.

git warned me that it repalced \n\r with \r at the end of the text files, but I hope it will still allow it to work when you pull it.