[OSGeo-UK] Bin packing problem

[Matthew Snape]

Antony,
 
I asked a similar question on GIS stack exchange last month:
http://gis.stackexchange.com/questions/4828/algorithm-to-place-maximum-n
umber-of-points-within-constrained-area-at-a-minimum.  Unfortunately I
never found anything GIS specific.  I did find this:
 
https://devel.nuclex.org/framework/wiki/RectanglePacking#no1
 
Are the roofs assumed to be rectangular, or can they be any shape?
 
 
________________________________

From: uk-bounces at lists.osgeo.org [mailto:uk-bounces at lists.osgeo.org] On
Behalf Of Antony Scott
Sent: 24 February 2011 10:04
To: uk at lists.osgeo.org
Subject: [OSGeo-UK] Bin packing problem


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.

________________________________



This e-mail message and any attached file is the property of the sender and is sent in confidence to the addressee only.
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 other means.
 
Any advice contained in this e-mail is for information purposes only.

RPS Planning and Development Limited, company number: 02947164 (England). Registered office: Centurion Court, 85 Milton Park Abingdon Oxfordshire OX14 4RY.
RPS Group Plc web link: <http://www.rpsgroup.com>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.osgeo.org/pipermail/uk/attachments/20110224/bf8b19a5/attachment-0001.html