I am looking to try and find the optimal fit for a number of rectangular shaped polygons into a larger irregular shaped polygon and I haven't found much information about how this could be achieved in PostGIS. I have found a solution using ArcGIS Desktop at Fitting known size polygons into irregular polygons using ArcGIS Desktop? However, I don't have a licence.

Doing some research it looks like I will need to use some kind of bin packing algorithm, however most of these algorithms deal with fitting small regular rectangles or squares into a large rectangle or square.

  • I don't think you have provided enough information for anyone to have a stab at this. What does "a number" mean, are they all the same shape, how does the larger irregular polygon look? It would certainly be possible to port the Python from the excellent to Postgis, although you may have to make use of plpgsql or run multiple loops using generate_series with different rotations. As you will note from the Wikipedia bin packing article, the problem is NP Hard and "optimal" depends considerably on how many objects you have and the compute resources available. – John Powell May 7 at 8:09
  • I understand, I wasn't looking for a specific answer, I guess I didn't make that clear. I was more interested to see if there was any resources that dealt with these kind of problems specific to PostGIS. It looks like that's not the case. So I will either solve the problem using plpgsql or just vanilla python. – Trashmonk May 7 at 9:03
  • Yes, there is no single Postgis function that could do this alone. – John Powell May 8 at 11:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.