kicad-developers team mailing list archive

[Tomasz Wlostowski <tomasz.wlostowski@xxxxxxx>]

On 20/11/2020 10:02, Alex wrote:
> Hi everyone,
> 
> I started doing some C++11 modernization and Standard Library insertion
> in the rectangular placement segment of the PCBNew, and in the process I
> went down the rabbit hole of documentation for the algorithm. Out of
> curiosity I adjusted the Greater algorithm from only sorting on the
> longest side, to first sorting by longest side, and then sorting by
> shortest side.
> 
> I found that this small adjustment seemed to increase packing density
> enough that when presented with 500 rectangles of randomly generated
> size of (15x15) - (85x85) fit into surfaces of (255 x 255), the total
> number of required surfaces went from ~28 to ~26. The catch is that the
> initial sorting of the algorithm takes a little longer.
> 
> Always the skeptic, I would like to know if there is currently a
> methodology or recommendation for incorporating a benchmark test for
> both space and time performance. At minimum, I can use Google Benchmark,
> but I'd like to know if I should place the tests in the same folder, or
> if there is another place for this kind of stuff.
> 

Alex,

Do you mean the rect packing algorithm used by the autoplacer?

Tom