[OSGeo-UK] Bin packing problem

[Antony Scott]

Hello all

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:
- iterate through a batch of polygons
- 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)
- ability to create visual representation of the result is nice to have but not essential

There's lots of stuff out there on bin packing, but can't find much in the GIS sphere. Any ideas appreciated!

many thanks
Antony

Antony Scott
Senior Associate (GIS)
Direct line

: +44 (0)1934 864 844

Switchboard

: +44 (0)1934 863 650

Mobile

: +44 (0)7866 455515

E-mail address

: antony.scott at sustain.co.uk<mailto:antony.scott at sustain.co.uk>

Website

: http://www.sustain.co.uk<http://www.sustain.co.uk/>





Sustain is a leading carbon reduction company. Our clients have saved 

3,489,948 lifetime tonnes of CO2 through working with us (January 2011)



------------------------------------------------------------



Sustain Ltd.  Registered in England No. 3384793

Barley Wood Stables, Long Lane, Wrington, Bristol BS40 5SA, UK



------------------------------------------------------------



This e-mail and any attachments are strictly confidential 

and intended solely for the addressee.  If you are not the 

intended recipient of this document then you must 

immediately inform the sender and delete this e-mail and 

any attachments from your system.



E-mail transmissions cannot be guaranteed to be secure or 

error free as information could be intercepted, corrupted, 

lost, destroyed, arrive late or incomplete.  The sender

does not accept liability for any errors or omissions in

the content of this message which arise as a result of 

e-mail transmission.



------------------------------------------------------------































-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/uk/attachments/20110224/da5c6720/attachment.html