← Back to team overview

kicad-developers team mailing list archive

Re: Tiling Algorithm Improvements


Hi Alex-

You are probably not getting many replies to this message as we're not
quite sure what aspect of KiCad you are looking at.  We might be able to
comment better with a bit more detail.


On Fri, Nov 20, 2020 at 1:03 AM Alex <alex.21789@xxxxxxxxx> 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.
> Thanks,
> Alex
> _______________________________________________
> Mailing list: https://launchpad.net/~kicad-developers
> Post to     : kicad-developers@xxxxxxxxxxxxxxxxxxx
> Unsubscribe : https://launchpad.net/~kicad-developers
> More help   : https://help.launchpad.net/ListHelp

[image: KiCad Services Corporation Logo]
Seth Hillbrand
*Lead Developer*
Long Beach, CA
www.kipro-pcb.com    info@xxxxxxxxxxxxx