kicad-developers team mailing list archive

[Alex <alex.21789@xxxxxxxxx>]

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.

Thanks,
Alex