[OSGeo-UK] Bin packing problem

[Antony Scott]

Barry, Matthew

Thanks - roofs are any shape - with dormers, rooflights, chimney stacks...

Maybe we should design a Tetris-style interface and crowd-source it? ;-)

Antony
________________________________
From: uk-bounces at lists.osgeo.org [uk-bounces at lists.osgeo.org] On Behalf Of Barry Rowlingson [b.rowlingson at lancaster.ac.uk]
Sent: 24 February 2011 10:58
To: Matthew Snape
Cc: uk at lists.osgeo.org
Subject: Re: [OSGeo-UK] Bin packing problem



On Thu, Feb 24, 2011 at 10:42 AM, Matthew Snape <SnapeM at rpsgroup.com<mailto:SnapeM at rpsgroup.com>> wrote:
Antony,

I asked a similar question on GIS stack exchange last month:  http://gis.stackexchange.com/questions/4828/algorithm-to-place-maximum-number-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?



 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.

 Good 2d bin-packing algorithms are worth millions to shipping companies, and Amazon....

 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 :)

Barry



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/0e68d6ce/attachment.html