Partial Flood Fill

Question

I'm writing a voronoi-based world generator in which I distinguish between geographic features like mountains, lakes, forests, and oceans.

Each feature is given an id so it can be identified and referenced. I use a flood fill algorithm to determine what features cells belong to.

I've realized a couple similar cases where I'd like to split a feature into multiple smaller ones. The most straightforward example is that of two big forests connected by a narrow strip of forest. Realistically, it should be treated as two forests, separated from each other around the narrow strip but my fill algorithm just plows right through and labels everything as part of one large forest.

I'd like to eventually label them "West 100 Acre Wood" and "East 100 Acre Wood", giving them the knowledge that they're deriving from the same continuous body of forest. I've looked up partial flood fill logic but my search has gotten stuck due to my lack of subject terminology.

If you'd like to see the code I'm working with: https://github.com/olinkirkland/map

Answer 1

After you find a connected region, you can trace around the interior using the right-hand rule (https://en.wikipedia.org/wiki/Maze_solving_algorithm#Wall_follower).

To find single-pixel paths that would make good splitting points, then, you can look for pixels in this interior path that are visited twice (once in each direction). If the path length is long enough on both sides of the split, then you can split the region into two at that pixel and maybe try again with the smaller regions.

If you want to find split points that are more than one pixel wide, or ensure that the forests on either side are "beefy" enough, I would suggest a pixel-based approach that combines this with the other methods:

1. BFS to remove pixels that are less than w away from the boundary.

2. Find each remaining connected region. Each will be the "center" of a forest.

3. Check each center to make sure it has pixels far enough from the edge to be the center of a forest.

4. Add the removed pixels back, connecting them to the closest center.

Answer 2

You would typically use a "morphological opening" see Wikipedia definition which is a morphological erosion followed by a dilation. If you imagine a white foreground object of interest on a black background, the erosion will erode (nibble away at the edges of) the object and the dilation will expand/fatten the edges back out - thereby removing small strips and narrow connections.

You can do it with the Scikit-Image module in Python, or with OpenCV in Python or C++. I choose to just do it at the command-line in Terminal here using ImageMagick which is installed on most Linux distros and is available for macOS and Windows.

So, using this map image:

I load it, invert/negate it to make the forest white, then apply the morphological opening I mentioned and then invert it back and save:

magick convert map.png -negate -morphology open disk:5 -negate result.png 

Answer 3

You could use a technique from image processing which uses blurring and applying a threshold of 50%. This way, thin connections and sharp spikes are reduced and features generally get rounder while the overall size of objects shouldn't change in one specific direction. Here's an image of what the process looks like when applied repetitively:

Separation of forests by blurring and applying a threshold

The top image represents your original situation with two forests which are connected by a thin corridor. The process step by step removes the corridor.

You can adjust some parameters in this process, e. g. the blurring radius and the number of steps, so you can tweak it to your needs.