In the green area of the raster I have to fit as many square polygons as possible, of three different sizes:

  • 3x3 cell size
  • 2x2 cell size
  • 1x1 cell size

With the fact that the approach should be greedy, so first fitting the biggest polygons, then the middle sized, and then if there is any space left, the smallest size. It does not have to be an exact approach but at least an approximation.

Considering this is just a test area for the algorithm, which should eventually perform this search on bigger real case rasters, where basically we have objects of three different sizes and are trying to place them in the allowed zones of the raster.

Having said that, I am aware it's not at all an easy task. I am using Qgis with R scripting to try to formulate this search.

Raster image from R

EDIT: By moving a 3x3 window square and suming up the cell values, it can be determined where are the possible locations for the squares:

raster matrix

So, wherever there is a 9 means the square can fit, but the squares cannot overlap so now the question is how to find the best combination of 9 cells that do not overlap

  • Scan from top left to bottom right. When you find a 3x3 green spot, fill it. Continue. That gets you a number of 3x3 fills in linear time, but is it optimal? Can we prove that? Is there an optimal solution and what's the complexity of finding it? I don't think the complexity can be that bad since there's only a finite number of cells in the raster... – Spacedman Aug 24 '17 at 11:38
  • I now have code that does the above, ie scan and find space for squares. But I'm not sure it constitutes an answer unless I know what you really want is an optimum solution (if such exists...) – Spacedman Aug 24 '17 at 13:54
  • Is a square what we see that looks like pixels ? In that case, the square area seems to be of 200x200 units, no ? 3x3 suare area would make a great number of squares... – gisnside Aug 24 '17 at 15:58
  • @Spacedman Yes exactlly what I managed to do, by moving the 3x3 square and summing up the values of the cells. If the sum is 9, that means the square can fit. After fitting all possible 3x3, mark those locations as 9, repeat the process with 2x2, and same for 1x1. But depending on where you start the search, different solutions are possible and how to prove the optimality – Dragana Aug 24 '17 at 20:54
  • 1
    Please share your code! If it’s big, perhaps a link to a gist? – Simbamangu Aug 29 '17 at 5:51

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.