← Back to team overview

kicad-developers team mailing list archive

Re: Tiling Algorithm Improvements



Yes, that's right. I was going to wait to respond until the morning, but
from as far as I can tell, this affects the Rect Packing.

I chose to start there, because it definitely seemed like it was written
with C++03 in mind.

On Mon, Nov 23, 2020, 10:49 PM 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