Problem: I have a series of nested grids. Example is below. I want to perform calculations for the smallest grid (grid with the smallest cells, green here) based on the values in the upper cells without performing an intersection method due to performance issues (my final grid has 4^10 cells).Nested grids

Example: Assume, that we have 4 grids. The biggest one, red, has only 1 cell with the value 'A' in it. At the next level we have blue grid with 4 cells and values 'X, Y, B, Z' in it, etc. At the lowest level I have pink grid with 64 cells.

I want to calculate the list of upper values for the cells at the smallest grid. So, for the selected pink cell it will be: [A, B, C, D] because [A is the the value in the upper cell at the 1st grid, B is the value in the upper call at the 2nd grid and so on]

Nested values example

Solution ideas: As I've said, the idea here is not to perform intersection method due to its obvious exponential performance issues for the grid with a HUGE number of cells (4x2^10 at 10th level in my case, so it has to intersect each cell with 4x2^9 cells at the 9th level, 4x2^8 cells at the 8th, ...)

My idea was to somehow implement cell IDs based on their place in the grid. Walking from upper left to lower right corner and setting 1,2,3 or 4 value I get IDs making possible to split it based on the level I want to get value from. The problem here is to inherit values from the upper cells.

Cell IDs

I can use GeoPandas, QGIS or PyQGIS if you write down the tutorial because I am not very familiar with PyQGIS syntax.


I'm not clear on what your calculations may look like eventually, but getting cell Ids as chains of identifiers (as in your last example) is simple QuadTree related math.

A naive implementation in Python may be:

import math

def divMod(q, n):
    return math.ceil(q/n), q%n

def cellId(x, y, z):
    id = []

    m = { (0, 0): 2, (1, 0): 1, (0, 1): 4, (1, 1): 3 }

    for _ in range(0, z):
        x, xr = divMod(x, 2)
        y, yr = divMod(y, 2)

        id.insert(0, m[(math.ceil(xr), math.ceil(yr))])

    id.insert(0, 1)
    return id

for the case when the smallest grid numbers are 1-based (note the custom divMod implementation), or

def cellId(x, y, z):
    id = []

    m = { (0, 0): 3, (1, 0): 4, (0, 1): 1, (1, 1): 2 }

    for _ in range(0, z):
        x, xr = divmod(x, 2)
        y, yr = divmod(y, 2)

        id.insert(0, m[(math.ceil(xr), math.ceil(yr))])

    id.insert(0, 1)
    return id

for 0-based grid numbering.

You'd need to round the spatial coordinates of the smallest cells to your grid numbering, then feed those cell coordinates to the functions.


I think this problem can be solved by using array and index and finding the value for each layer as an index.

  1. Let's redesign the index as a cell once it fits inside one perfect rectangle. (BBOX)

  2. You can now indexing by smallest cell.

  3. You can check the value of the next level layer based on the index.

In other words, you can think of it as converting a vector grid to raster (array).

When the smallest cell order is (0, 0) to (15, 15), the second cell is (0,0) to (3,3), the next is (0,0) to (1,1), and the last cell is (0,0).

You can think of this as converting to a 4-channel raster (4 axis numpy array) based on the smallest cell, and most of the work will be possible with only geopandas and numpy without raster conversion.

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.