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

here is a solution using a virtual layer instead of python – JGH Jul 26 '22 at 12:48 — JGH, Jul 26 '22 at 12:48

BERA · Accepted Answer · 2022-07-26T16:45:57.987

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

Generating horizontally ordered ids for irregular grid

1 Answers1