0

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

Improve this question
4
  • 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
    Commented Mar 21, 2019 at 18:24
  • @Spacedman Exactly.
    – Martin Weber
    Commented Mar 21, 2019 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
    Commented Mar 22, 2019 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
    Commented Mar 24, 2019 at 16:33

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.