<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML dir=ltr><HEAD>
<META content="text/html; charset=us-ascii" http-equiv=Content-Type>
<STYLE title=owaParaStyle>P {
MARGIN-TOP: 0px; MARGIN-BOTTOM: 0px
}
</STYLE>
<META name=GENERATOR content="MSHTML 8.00.7600.16722"></HEAD>
<BODY ocsi="x">
<DIV dir=ltr align=left><SPAN class=653413610-24022011><FONT color=#0000ff
size=2 face=Arial>Antony,</FONT></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=653413610-24022011><FONT color=#0000ff
size=2 face=Arial></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=653413610-24022011><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">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 class=653413610-24022011><FONT color=#0000ff
size=2 face=Arial></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=653413610-24022011><A
href="https://devel.nuclex.org/framework/wiki/RectanglePacking#no1">https://devel.nuclex.org/framework/wiki/RectanglePacking#no1</A></SPAN></DIV>
<DIV dir=ltr align=left><SPAN class=653413610-24022011><FONT color=#0000ff
size=2 face=Arial></FONT></SPAN> </DIV>
<DIV dir=ltr align=left><SPAN class=653413610-24022011><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 class=OutlookMessageHeader align=left><SPAN
class=653413610-24022011><FONT color=#0000ff size=2
face=Arial> </FONT></SPAN></DIV>
<DIV dir=ltr lang=en-us class=OutlookMessageHeader align=left><SPAN
class=653413610-24022011> </SPAN></DIV>
<DIV dir=ltr lang=en-us class=OutlookMessageHeader align=left>
<HR tabIndex=-1>
</DIV>
<DIV dir=ltr lang=en-us class=OutlookMessageHeader align=left><FONT size=2
face=Tahoma><B>From:</B> uk-bounces@lists.osgeo.org
[mailto:uk-bounces@lists.osgeo.org] <B>On Behalf Of </B>Antony
Scott<BR><B>Sent:</B> 24 February 2011 10:04<BR><B>To:</B>
uk@lists.osgeo.org<BR><B>Subject:</B> [OSGeo-UK] Bin packing
problem<BR></FONT><BR></DIV>
<DIV></DIV>
<DIV dir=ltr><FONT color=#000000 size=2 face=Tahoma>Hello all</FONT></DIV>
<DIV dir=ltr><FONT size=2 face=tahoma></FONT> </DIV>
<DIV dir=ltr><FONT size=2 face=tahoma>We've been doing some work on estimating
the number of solar PV panels that can be fitted on defined roof surfaces, which
seems to be what's known as a bin packing problem. Given that we have polygons
for the roofs (thousands of them), does anyone have any knowledge of tools or
algorithms which would be capable of integration with eg QGIS or PostGIS which
would:</FONT></DIV>
<DIV dir=ltr><FONT size=2 face=tahoma>- iterate through a batch of
polygons</FONT></DIV>
<DIV dir=ltr><FONT size=2 face=tahoma>- for each, determine the maximum number
of fixed-dimension rectangles which could be fitted inside the polygon, working
to a set of rules (eg border, orientation, alignement)</FONT></DIV>
<DIV dir=ltr><FONT size=2 face=tahoma>- ability to create visual representation
of the result is nice to have but not essential</FONT></DIV>
<DIV dir=ltr><FONT size=2 face=tahoma></FONT> </DIV>
<DIV dir=ltr><FONT size=2 face=tahoma>There's lots of stuff out there on bin
packing, but can't find much in the GIS sphere. Any ideas
appreciated!</FONT></DIV>
<DIV dir=ltr><FONT size=2 face=tahoma></FONT> </DIV>
<DIV dir=ltr><FONT size=2 face=tahoma>many thanks</FONT></DIV>
<DIV dir=ltr><FONT size=2 face=tahoma>Antony</FONT></DIV>
<DIV dir=ltr><FONT size=2 face=tahoma></FONT> </DIV>
<DIV dir=ltr><FONT size=2 face=tahoma>
<P class=MsoNormal><SPAN
style="FONT-FAMILY: 'Arial','sans-serif'; FONT-SIZE: 10pt">Antony
Scott<BR><B>Senior Associate (GIS)</B></SPAN><SPAN
style="FONT-FAMILY: 'Times New Roman','serif'; FONT-SIZE: 12pt"></SPAN></P>
<TABLE style="WIDTH: 375pt" class=MsoNormalTable border=0 cellSpacing=0
cellPadding=0 width=500>
<TBODY>
<TR>
<TD
style="PADDING-BOTTOM: 0cm; PADDING-LEFT: 0cm; WIDTH: 75pt; PADDING-RIGHT: 0cm; PADDING-TOP: 0cm"
width=100>
<P class=MsoNormal><SPAN
style="FONT-FAMILY: 'Arial','sans-serif'; FONT-SIZE: 10pt">Direct
line</SPAN><SPAN
style="FONT-FAMILY: 'Arial','sans-serif'; FONT-SIZE: 10pt"></SPAN></P></TD>
<TD
style="PADDING-BOTTOM: 0cm; PADDING-LEFT: 0cm; WIDTH: 300pt; PADDING-RIGHT: 0cm; PADDING-TOP: 0cm"
width=400>
<P class=MsoNormal><SPAN
style="FONT-FAMILY: 'Arial','sans-serif'; FONT-SIZE: 10pt">: +44 (0)1934
864 844</SPAN><SPAN
style="FONT-FAMILY: 'Arial','sans-serif'; FONT-SIZE: 10pt"></SPAN></P></TD></TR>
<TR>
<TD
style="PADDING-BOTTOM: 0cm; PADDING-LEFT: 0cm; WIDTH: 75pt; PADDING-RIGHT: 0cm; PADDING-TOP: 0cm"
width=100>
<P class=MsoNormal><SPAN
style="FONT-FAMILY: 'Arial','sans-serif'; FONT-SIZE: 10pt">Switchboard</SPAN><SPAN
style="FONT-FAMILY: 'Arial','sans-serif'; FONT-SIZE: 10pt"></SPAN></P></TD>
<TD
style="PADDING-BOTTOM: 0cm; PADDING-LEFT: 0cm; WIDTH: 300pt; PADDING-RIGHT: 0cm; PADDING-TOP: 0cm"
width=400>
<P class=MsoNormal><SPAN
style="FONT-FAMILY: 'Arial','sans-serif'; FONT-SIZE: 10pt">: +44 (0)1934
863 650</SPAN><SPAN
style="FONT-FAMILY: 'Arial','sans-serif'; FONT-SIZE: 10pt"></SPAN></P></TD></TR>
<TR>
<TD
style="PADDING-BOTTOM: 0cm; PADDING-LEFT: 0cm; WIDTH: 75pt; PADDING-RIGHT: 0cm; PADDING-TOP: 0cm"
width=100>
<P class=MsoNormal><SPAN
style="FONT-FAMILY: 'Arial','sans-serif'; FONT-SIZE: 10pt">Mobile</SPAN><SPAN
style="FONT-FAMILY: 'Arial','sans-serif'; FONT-SIZE: 10pt"></SPAN></P></TD>
<TD
style="PADDING-BOTTOM: 0cm; PADDING-LEFT: 0cm; WIDTH: 300pt; PADDING-RIGHT: 0cm; PADDING-TOP: 0cm"
width=400>
<P class=MsoNormal><SPAN
style="FONT-FAMILY: 'Arial','sans-serif'; FONT-SIZE: 10pt">: +44 (0)7866
455515</SPAN><SPAN
style="FONT-FAMILY: 'Arial','sans-serif'; FONT-SIZE: 10pt"></SPAN></P></TD></TR>
<TR>
<TD
style="PADDING-BOTTOM: 0cm; PADDING-LEFT: 0cm; WIDTH: 75pt; PADDING-RIGHT: 0cm; PADDING-TOP: 0cm"
width=100>
<P class=MsoNormal><SPAN
style="FONT-FAMILY: 'Arial','sans-serif'; FONT-SIZE: 10pt">E-mail
address</SPAN><SPAN
style="FONT-FAMILY: 'Arial','sans-serif'; FONT-SIZE: 10pt"></SPAN></P></TD>
<TD
style="PADDING-BOTTOM: 0cm; PADDING-LEFT: 0cm; WIDTH: 300pt; PADDING-RIGHT: 0cm; PADDING-TOP: 0cm"
width=400>
<P class=MsoNormal><SPAN
style="FONT-FAMILY: 'Arial','sans-serif'; FONT-SIZE: 10pt">: <A
href="mailto:antony.scott@sustain.co.uk"><SPAN
style="COLOR: blue">antony.scott@sustain.co.uk</SPAN></A></SPAN><SPAN
style="FONT-FAMILY: 'Arial','sans-serif'; FONT-SIZE: 10pt"></SPAN></P></TD></TR>
<TR>
<TD
style="PADDING-BOTTOM: 0cm; PADDING-LEFT: 0cm; WIDTH: 75pt; PADDING-RIGHT: 0cm; PADDING-TOP: 0cm"
width=100>
<P class=MsoNormal><SPAN
style="FONT-FAMILY: 'Arial','sans-serif'; FONT-SIZE: 10pt">Website</SPAN><SPAN
style="FONT-FAMILY: 'Arial','sans-serif'; FONT-SIZE: 10pt"></SPAN></P></TD>
<TD
style="PADDING-BOTTOM: 0cm; PADDING-LEFT: 0cm; WIDTH: 300pt; PADDING-RIGHT: 0cm; PADDING-TOP: 0cm"
width=400>
<P class=MsoNormal><SPAN
style="FONT-FAMILY: 'Arial','sans-serif'; FONT-SIZE: 10pt">: <A
href="http://www.sustain.co.uk/" target=_blank><SPAN
style="COLOR: blue">http://www.sustain.co.uk</SPAN></A></SPAN><SPAN
style="FONT-FAMILY: 'Arial','sans-serif'; FONT-SIZE: 10pt"></SPAN></P></TD></TR></TBODY></TABLE>
<P class=MsoNormal> </P></FONT></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>
<P><FONT face=Arial color=#003366 size=1>This e-mail message and any attached
file is the property of the sender and is sent in confidence to the addressee
only.</FONT></P>
<P><FONT face=Arial color=#003366 size=1>Internet communications are not secure
and RPS is not responsible for their abuse by third parties, any alteration or
corruption in transmission or for any loss or damage caused by a virus or by any
other means.</FONT></P><FONT face=Arial color=#003366 size=1>RPS Planning and
Development Limited, company number: 02947164 (England). Registered office:
Centurion Court, 85 Milton Park Abingdon Oxfordshire OX14 4RY.<BR><BR>RPS Group
Plc web link: <A
href="http://www.rpsgroup.com/">http://www.rpsgroup.com</A></FONT>
<P></P>
</BODY></HTML>