Rewrite center-packing algorithm and ditch packery

[dhowe]

[mushon]

👍

[ice-fly]

A cutting plane method seems to be the best out there This paper has a parallel algorithm which will be faster than packery's algo. Adding one ad at a time is slow... parrallel algorithms ftw. HyperLogLog is also appropriate for this visualization use case to guess the number of distinct ads and set a boundary/scale.

That being said, Without using that parallel algorithm you could still do some subdivision of labor by using cutting planes to create sectors with hamming distance 3: take the first rectangle, cut sectors from it's edges. take 3 sectors with hamming distance 3, and just stuff whatever's in the ad list until reaching the outside radius (even if it overflows the sector into one of the hamming distance 2 sectors thats okay because they are all atleast hamming distance 1 sectors from each other) then just fill the gaps later using your the normal 4 sided algorithm.

During the hamming 3 sectors the code only has to check 2 sides (and the outside radius) instead of 4 sides for intersection and the code doesn't have to search for ads that are the right aspect ratio. So from the first rectangle 8 sectors Hamming codes say there's 2 sectors with hamming 3 distance. those two have 1/2 the intersection checks. saving you 1/16th of computational complexity. Recursively doing that will get you fractional improvements. (but if your going to do all that work you might as well make it parallel)

[dhowe]

Any interest in contributing this feature ??

[mushon]

Interest = yes. Capacity = less.

If there are any specific questions I would love to help. Maybe we can even do a zoom session when it makes sense. Let me know, and thanks for keeping me in the loop.

M.