<html dir="ltr"><head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<meta name="GENERATOR" content="MSHTML 8.00.6001.19019">
<style title="owaParaStyle"><!--P {
MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px
}
--></style>
</head>
<body ocsi="x">
<div dir="ltr"><font color="#000000" size="2" face="Tahoma">Barry, Matthew</font></div>
<div dir="ltr"><font size="2" face="tahoma"></font> </div>
<div dir="ltr"><font size="2" face="tahoma">Thanks - roofs are any shape - with dormers, rooflights, chimney stacks...</font></div>
<div dir="ltr"><font size="2" face="tahoma"></font> </div>
<div dir="ltr"><font size="2" face="tahoma">Maybe we should design a Tetris-style interface and crowd-source it? ;-)</font></div>
<div dir="ltr"><font size="2" face="tahoma"></font> </div>
<div dir="ltr"><font size="2" face="tahoma">Antony</font></div>
<div style="DIRECTION: ltr" id="divRpF29033">
<hr tabindex="-1">
<font size="2" face="Tahoma"><b>From:</b> uk-bounces@lists.osgeo.org [uk-bounces@lists.osgeo.org] On Behalf Of Barry Rowlingson [b.rowlingson@lancaster.ac.uk]<br>
<b>Sent:</b> 24 February 2011 10:58<br>
<b>To:</b> Matthew Snape<br>
<b>Cc:</b> uk@lists.osgeo.org<br>
<b>Subject:</b> Re: [OSGeo-UK] Bin packing problem<br>
</font><br>
</div>
<div></div>
<div><br>
<br>
<div class="gmail_quote">On Thu, Feb 24, 2011 at 10:42 AM, Matthew Snape <span dir="ltr">
<<a href="mailto:SnapeM@rpsgroup.com">SnapeM@rpsgroup.com</a>></span> wrote:<br>
<blockquote style="BORDER-LEFT: rgb(204,204,204) 1px solid; MARGIN: 0pt 0pt 0pt 0.8ex; PADDING-LEFT: 1ex" class="gmail_quote">
<div>
<div dir="ltr" align="left"><span><font color="#0000ff" size="2" face="Arial">Antony,</font></span></div>
<div dir="ltr" align="left"><span><font color="#0000ff" size="2" face="Arial"></font></span> </div>
<div dir="ltr" align="left"><span><font color="#0000ff" size="2" face="Arial">I asked a similar question on GIS stack exchange last month:
<a href="http://gis.stackexchange.com/questions/4828/algorithm-to-place-maximum-number-of-points-within-constrained-area-at-a-minimum" target="_blank">
http://gis.stackexchange.com/questions/4828/algorithm-to-place-maximum-number-of-points-within-constrained-area-at-a-minimum</a>. Unfortunately I never found anything GIS specific. I did find this:</font></span></div>
<div dir="ltr" align="left"><span><font color="#0000ff" size="2" face="Arial"></font></span> </div>
<div dir="ltr" align="left"><span><a href="https://devel.nuclex.org/framework/wiki/RectanglePacking#no1" target="_blank">https://devel.nuclex.org/framework/wiki/RectanglePacking#no1</a></span></div>
<div dir="ltr" align="left"><span><font color="#0000ff" size="2" face="Arial"></font></span> </div>
<div dir="ltr" align="left"><span><font color="#0000ff" size="2" face="Arial">Are the roofs assumed to be rectangular, or can they be any shape?</font></span></div>
<div dir="ltr" lang="en-us" align="left"><span><font color="#0000ff" size="2" face="Arial"></font></span> </div>
<div dir="ltr" lang="en-us" align="left"><span></span> </div>
</div>
</blockquote>
<div><br>
The python version of the 'Cygon' algorithm referenced there could easily be turned into a QGIS plugin of course. I've got it running as a standalone python module.<br>
<br>
Good 2d bin-packing algorithms are worth millions to shipping companies, and Amazon....<br>
<br>
This is of course a very hard problem, and by the time we have a quick solution we'll probably have roll-on solar panels that can be cut to an exact size :)<br>
<br>
Barry<br>
</div>
</div>
</div>
<br><P><SPAN style="FONT-FAMILY: 'Calibri','sans-serif'; FONT-SIZE: 11pt; mso-fareast-font-family: Calibri; mso-ansi-language: EN-GB; mso-fareast-language: EN-GB; mso-bidi-language: AR-SA; mso-fareast-theme-font: minor-latin; mso-bidi-font-family: 'Times New Roman'"><FONT color=#000000 size=3 face=Arial>Sustain is a leading carbon reduction company. Our clients have saved</FONT></SPAN></P>
<P><SPAN style="FONT-FAMILY: 'Calibri','sans-serif'; FONT-SIZE: 11pt; mso-fareast-font-family: Calibri; mso-ansi-language: EN-GB; mso-fareast-language: EN-GB; mso-bidi-language: AR-SA; mso-fareast-theme-font: minor-latin; mso-bidi-font-family: 'Times New Roman'"><FONT color=#000000 size=3 face=Arial><FONT color=#99cc33><B>3,489,948</B> </FONT><FONT color=#000000>lifetime tonnes of CO<SUB>2</SUB></FONT> through working with us (January 2011)</FONT></SPAN></P>
<P>
<HR align=left color=#000000 SIZE=1 width=500 noShade>
<P></P>
<P><FONT size=2>Sustain Ltd. Registered in England No. 3384793 <BR>Barley Wood Stables, Long Lane, Wrington, Bristol BS40 5SA, UK</FONT></P>
<HR align=left color=#000000 SIZE=1 width=500 noShade>
<P><FONT size=2>This e-mail and any attachments are strictly confidential and intended solely for the <BR>addressee. If you are not the intended recipient of this document then you must <BR>immediately inform the sender and delete this e-mail and any attachments from <BR>your system.</FONT></P>
<P><FONT size=2>E-mail transmissions cannot be guaranteed to be secure or error free as information <BR>could be intercepted, corrupted, lost, destroyed, arrive late or incomplete. The sender <BR>does not accept liability for any errors or omissions in the content of this message <BR>which arise as a result of e-mail transmission.</FONT></P>
<HR align=left color=#000000 SIZE=1 width=500 noShade>
<br></body>
</html>