Re: [Kicad-developers] Tiling Algorithm Improvements
@Tom 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 wrote: > 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 > ___ Mailing list: https://launchpad.net/~kicad-developers Post to : kicad-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp
Re: [Kicad-developers] Tiling Algorithm Improvements
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 ___ Mailing list: https://launchpad.net/~kicad-developers Post to : kicad-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp
Re: [Kicad-developers] 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. Best- Seth On Fri, Nov 20, 2020 at 1:03 AM 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. > > Thanks, > Alex > ___ > Mailing list: https://launchpad.net/~kicad-developers > Post to : kicad-developers@lists.launchpad.net > Unsubscribe : https://launchpad.net/~kicad-developers > More help : https://help.launchpad.net/ListHelp > -- [image: KiCad Services Corporation Logo] Seth Hillbrand *Lead Developer* +1-530-302-5483 Long Beach, CA www.kipro-pcb.comi...@kipro-pcb.com ___ Mailing list: https://launchpad.net/~kicad-developers Post to : kicad-developers@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp
[Kicad-developers] Tiling Algorithm Improvements
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@lists.launchpad.net Unsubscribe : https://launchpad.net/~kicad-developers More help : https://help.launchpad.net/ListHelp
