Generating horizontally ordered ids for irregular grid

Question

How can I generate ids for an irregular shaped grid that increase from west to east and north to south (left to right, top to bottom)?

I've tried using this example and it almost works, but it does not work for an odd shaped grid - only symmetrical ones.

In the included image, the algorithm placed 9 below 8 instead of below 4 where it should be.

My Python code attempts to sort the rectangles horizontally instead of generating ids, but it is the same idea.

def sorted_horizontally(self):
    ...snip...
    faps_centroids = {k: v.geometry().centroid().asPoint() for k, v in faps.items()}
    centroids = []
    for k, v in faps_centroids.items():
        centroids.append( (v.x(), v.y()) )

    # X COORDINATE OPERATIONS
    min_centroid = min(centroids, key = lambda x: x[0])
    max_centroid = max(centroids, key = lambda x: x[0])
    min_x_centroid = min_centroid[0]
    max_x_centroid = max_centroid[0]
    x_centroids = [i[0] for i in centroids]
    x_set = set(x_centroids)
    distinct_x = len(x_set)
    range_x_centroid = max_x_centroid - min_x_centroid

    # Y COORDINATE OPERATIONS
    y_min_centroid = min(centroids, key = lambda x: x[1])
    y_max_centroid = max(centroids, key = lambda x: x[1])
    min_y_centroid = y_min_centroid[1]
    max_y_centroid = y_max_centroid[1]
    y_centroids = [i[1] for i in centroids]
    y_set = set(y_centroids)
    distinct_y = len(y_set)
    range_y_centroid = max_y_centroid - min_y_centroid

    # X VALUES
    x_values = []
    for k, v in faps_centroids.items():
        value = round( (v.x() - min_x_centroid) / (range_x_centroid/ distinct_x ) )
        x_values.append(value)
    x_values_set = sorted(list(set(x_values)))
    row_dict = {}
    for k, v in faps_centroids.items():
        value = round( (v.x() - min_x_centroid) / (range_x_centroid/ distinct_x ) )
        row_dict[k] = x_values_set.index(value) + 1
    row_dict = {k:v for k, v in sorted(row_dict.items(), key = lambda x: x[1])}

    # Y VALUES
    col_dict = {}
    y_values = []
    for k, v in faps_centroids.items():
        value = round ( (max_y_centroid - v.y()) / (range_y_centroid / distinct_y) )
        y_values.append(value)
    y_values_set = sorted(list(set(y_values)))
    for k, v in faps_centroids.items():
        value = round ( (max_y_centroid - v.y()) / (range_y_centroid / distinct_y) )
        col_dict[k] = y_values_set.index(value) + 1
    col_dict = {k:v for k, v in sorted(col_dict.items(), key = lambda x: x[1])}

    # BOTH X, Y
    final_dict = {}
    for k, v in col_dict.items():
        for kk, vv in row_dict.items():
            if k == kk:
                final_dict[k] = (vv, v)

    final_sort = sorted(final_dict, key = lambda k: (final_dict[k][1], final_dict[k][0]))
    return final_sort

Answer 1

Try this. It should work if your data is not rotated. I had to round the centroid values to zero decimals, you might have to play around with number of decimals if it doesnt work as expected:

layer = iface.activeLayer()

idfield = 'gridid' #The integer field to store grid ids in, add before executing
features = [f for f in layer.getFeatures()] #List all features
features.sort(key=lambda x: (-round(x.geometry().centroid().asPoint().y()), round(x.geometry().centroid().asPoint().x()))) #Sort the list by negative y and positive x centroid coordinates

ix = layer.fields().indexOf(idfield) #Find the index of idfield
attributemap = {f.id():{ix:e} for e,f in enumerate(features, 1)} #Number the features with enumerate
#{1: {5: 1}, 217: {5: 2},... 270: {5: 177}, 288: {5: 178}} Feature 1 will get grid id 1 in field 5, feature 288 id 178

layer.dataProvider().changeAttributeValues(attributemap) #Change/save the values