I have a regular grid with a cell width of 200 meters (available as raster and vector data set). Each cell has a value from 0 to 2000.

I now want to draw circles around these cells in such a way that the sum of values inside the coverage of the circle reaches a maximum of 2000. The radius of the circle can be unlimited, but should not exceed 20,000 meters. The circles may touch or overlap and there's no limit in circles, but there should be as little circles as possible.

I am aware that this will be an iterative procedure. I just have no idea how to approach this. I have R, QGIS, PostGIS and Python at my disposal.

Maybe there is some kind of clustering here that already does what I want it to do. Probably you could also use rectangles as a basis for the calculation, the radius is quite similar.

Edit Maybe another idea is to grow squares from (n+1)^2 cells instead of circles...

Example image

  • So you want to find the minimum number of circles to cover the whole rectangular area with the constraint that the sum of cells under any circle is < 2000? – Spacedman Mar 21 '19 at 18:24
  • @Spacedman Exactly. – Martin Weber Mar 21 '19 at 19:32
  • Just some more thoughts - the worst solution would be one circle per grid cell, and the best solution would have N circles where N is the smallest integer such that sum(grid cells)/N < 2000. I think its computationally hard (ie near impossible) to find the optimum solution before the universe dies but heuristic approaches involving optimisation techniques like simulated annealing might get going in the right direction... – Spacedman Mar 22 '19 at 8:42
  • @Spacedman Yeah, I also thought about this. It's similar to label placement (simulated annealing is pretty common there). Okay, this will need lots of reading, I guess. – Martin Weber Mar 24 '19 at 16:33

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.