Flood fill formula for Voronoi cells on QGIS?

At the moment, I'm developing a map of a fictional West Indian nation with QGIS. Everything's gone as well as can be expected with this project--except for a shortcoming that stumped me on Thursday afternoon.

The latest part of my project involves grouping areas on a Voronoi chart, based on attribute. For instance, if I choose at least two cells and set their value as 1, then every cell touching their sides must have 2 as their value; those touching the "2" cells receive 3; and so forth until they reach the chart bounds. This method, known as a "flood fill", is used in procedural generation; see it in action in this Imgur album.

When trying to select empty touching cells with this expression:

``````CASE
WHEN "Dist Lvl" = 1
THEN geomtouches(buffer(centroid(\$geometry), 100))
END
``````

Before I continue, I'd like to obtain a better code, or a Python/PyQGIS script, that can do the job faster; I struggled to draft one on paper a while ago. (Although I can efficiently use QGIS otherwise, I sometimes have trouble with the PyQGIS bit, a couple of examples aside.)

At least reading so many of these posts here in the past few years--this here is my first one--have really helped me on my way as a geofiction cartographer. So now it's your turn to help me out.

Interesting question! I've done a similar flood fill in the past, but for different purposes. I hadn't thought of using it for world building :)

I've done this in QGIS, Python and Postgres/PostGIS, but I'm sure it could be done in pyqgis too. Here's an example with one city spreading out to neighbouring polygons :-

• In this case, I created lots of random points, made a voronoi diagram, and saved as a shapefile.
• Next, added an integer field called `generation`, and seeded a couple of cells with the value 1. Other cells set to NULL.
• imported this into postgres using shp2pgsql-gui

The following python will perform the flood fill from one site, one ring at a time, until there is no cell left to fill.

``````import psycopg2

conn = psycopg2.connect("host='localhost' dbname='XXX' user='XXX' password='XXX'")

def growfrom(cell_value):
cursor = conn.cursor()
sql = """
WITH
ring as (select * from voronoi where generation=%s),
unfilled as (select * from voronoi where generation is null)
SELECT
unfilled.gid as geom
FROM
ring, unfilled
WHERE
st_intersects(ring.geom, unfilled.geom);
"""
cursor.execute(sql, (cell_value,))
neighbours = []
for record in cursor.fetchall():
neighbours.append(record[0])
sql = """
UPDATE
voronoi
SET
generation=%s
WHERE
gid = ANY (%s);
"""
cursor.execute(sql, (cell_value+1, neighbours))
conn.commit()
return len(neighbours)  # when this hits zero, stop

def main():
start_from = 1
while True:
neighbours = growfrom(start_from)
print("Added {} neighbours in generation #{}".format(neighbours, start_from))
if neighbours == 0:
break
start_from += 1

if __name__=="__main__":
main()
``````

I've not tried this particular approach on more complex gometries (like census areas); these can have unusual cases (like enclaves, for example). But it seems to work well on voronoi polygons.

Given the end purpose of this, you will need to modify this to start from multiple start points, not just 1. For example, you could make each city start with a multiple of 1000, and grow each one in parallel in that loop. That way polygons can easily be allocated a new field (divide by 1000), and use dissolve to get your country outlines - like this:-

To do this, could use something like this as the main function

``````def main():

def getsequence():
# goes 1000,2000,3000,4000,1001,2001... etc
ix = 0
while ix<1000:
yield 1000+ix
yield 2000+ix
yield 3000+ix
yield 4000+ix
ix+=1

while True:
for start_from in getsequence():
neighbours = growfrom(start_from)
print("Added {} neighbours in generation #{}".format(neighbours, start_from))
``````

This gives a slight bias towards lower-numbered cities, though, so you might want to tweak the generator to make it more random :)

• Thanks, Mr. Kay, but I'm testing this on a firewalled machine and nothing's happening--save for this error: 'Connection refused (0x0000274D/10061) / Is the server running on host "localhost" (::1) and accepting TCP/IP connections on port 5432?' Any other way out? – Routhwick May 1 '17 at 18:23