17
\$\begingroup\$

I have a 2D hexagonal grid map. Each hex cell has a height value used to determine if it's water or ocean. I'm trying to think of a good way to determine and label bodies of water. Oceans and inland seas are easy (using a flood fill algorithm).

But what about bodies of water like the Mediterranean? Bodies of water that are attached to larger ones (where "seas" and "gulfs" differ only by the size of the opening)?

Here's an example of what I'm trying to detect (the blue body of water in the middle of the image, which should be labelled differently from the larger body of ocean on the left, despite being technically connected): world map

Any ideas?

\$\endgroup\$
10
+50
\$\begingroup\$

What you're describing is the Segmentation Problem. I'm sorry to say that it's actually an unsolved problem. But one method I would recommend for this is a Graph-Cut based algorithm. Graph-Cut represents the image as a graph of locally connected nodes. It subdivides connected components of the graph recursively such that the border between the two sub-components is of minimal length using the Max-flow-min-cut theorem and the Ford Fulkerson algorithm.

Essentially, you connect all of the water tiles into a graph. Assign weights to the edges in the graph which correspond to differences between the adjacent water tiles. I think in your case, all the weights could be 1. You will have to play with different weighting schemes to get a desirable result. You might have to add some weight that includes adjacency to coasts, for instance.

Then, find all the connected components of the graph. These are obvious seas/lakes and so on.

Finally, for each connected component, recursively subdivide the component such that the edges connecting the two new sub-components have minimum weight. Keep recursively subdividing until all the sub-components reach a minimum size (i.e like the maximum size of a sea), or if the edges cutting the two components have too high a weight. Finally, label all the connected components that remain.

What this will do in practice is cut the seas from each other at channels, but not accross big spans of oceans.

Here it is in pseudocode:

function SegmentGraphCut(Map worldMap, int minimumSeaSize, int maximumCutSize)
    Graph graph = new Graph();
    // First, build the graph from the world map.
    foreach Cell cell in worldMap:
        // The graph only contains water nodes
        if not cell.IsWater():
            continue;

        graph.AddNode(cell);

        // Connect every water node to its neighbors
        foreach Cell neighbor in cell.neighbors:
            if not neighbor.IsWater():
                continue;
            else:  
                // The weight of an edge between water nodes should be related 
                // to how "similar" the waters are. What that means is up to you. 
                // The point is to avoid dividing bodies of water that are "similar"
                graph.AddEdge(cell, neighbor, ComputeWeight(cell, neighbor));

   // Now, subdivide all of the connected components recursively:
   List<Graph> components = graph.GetConnectedComponents();

   // The seas will be added to this list
   List<Graph> seas = new List<Graph>();
   foreach Graph component in components:
       GraphCutRecursive(component, minimumSeaSize, maximumCutSize, seas);


// Recursively subdivides a component using graph cut until all subcomponents are smaller 
// than a minimum size, or all cuts are greater than a maximum cut size
function GraphCutRecursive(Graph component, int minimumSeaSize, int maximumCutSize, List<Graph> seas):
    // If the component is too small, we're done. This corresponds to a small lake,
    // or a small sea or bay
    if(component.size() <= minimumSeaSize):
        seas.Add(component);
        return;

    // Divide the component into two subgraphs with a minimum border cut between them
    // probably using the Ford-Fulkerson algorithm
    [Graph subpartA, Graph subpartB, List<Edge> cut] = GetMinimumCut(component);

    // If the cut is too large, we're done. This corresponds to a huge, bulky ocean
    // that can't be further subdivided
    if (GetTotalWeight(cut) > maximumCutSize):
        seas.Add(component);
        return;
    else:
        // Subdivide each of the new subcomponents
        GraphCutRecursive(subpartA, minimumSeaSize, maximumCutSize);
        GraphCutRecursive(subpartB, minimumSeaSize, maximumCutSize);

EDIT: By the way, here's what the algorithm would do with your example with a minimum sea size set to around 40, with a maximum cut size of 1, if all the edge weights are 1:

Imgur

By playing with the parameters, you can get different results. A maximum cut size of 3, for instance, would result in many more bays getting carved out from the main seas, and sea #1 would get subdivided in half north and south. A minimum sea size of 20 would result in the central sea getting divided in half as well.

\$\endgroup\$
  • \$\begingroup\$ seems powerful. definitely thought inducing. \$\endgroup\$ – v.oddou Dec 17 '14 at 1:35
  • \$\begingroup\$ Thank you so much for this post. I managed to get something reasonable from your example \$\endgroup\$ – Kaelan Cooter Jun 19 '15 at 21:13
6
\$\begingroup\$

A quick and dirty way to identify a separate but connected body of water would be to shrink all water bodies and see if gaps appear.

In the example above I think that removing all water tiles which have 2 or less water tiles connected to them (marked red) would provide you with the desirable result plus some edge noise. After you have labeled the bodies, you can "flow" the water to its original state and reclaim the removed tiles for the now separate bodies.

enter image description here

Again, this is a quick and dirty solution, it might not be good enough for the later stages of production but it will suffice to "get this working for now" and move on to some other feature.

\$\endgroup\$
5
\$\begingroup\$

Here's a complete algorithm that I think should produce good results.

  1. Perform morphological erosion on the water area — that is, make a copy of the map on which each tile is considered water only if it and all of of its neighbors (or a larger area, if you have rivers wider than one tile) are water. This will result in all rivers disappearing entirely.

    (This will consider the islanded water in the left part of your inland sea to be rivers. If this is a problem, you could use a different rule such as the one vrinek's answer proposes instead; the following steps will still work as long as you have some kind of “delete rivers” step here.)

  2. Find the connected water components of the eroded map and give each one a unique label. (I assume you already know how to do this.) This now labels everything but rivers and shore water (where the erosion had an effect).

  3. For each water tile in the original map, find the labels present on neighboring water tiles in the eroded map and then:

    • If the tile itself has a label in the eroded map, then it is mid-sea water; give it that label in the original map.
    • If you find only one distinct neighboring label, then it is shore or river mouth; give it that label.
    • If you find no labels, then it is a river; leave it alone.
    • If you find multiple labels, then it is a short bottleneck between two larger bodies; you might want either to consider it like a river, or to combine the two bodies under a single label.

    (Note that for this step you must keep separate grids of labels (or have two label fields in one structure) for the eroded map (that you read from) and the original (that you write to), or there'll be iteration-order-dependent errors.)

  4. If you want to label individual rivers uniquely too, then after the above steps, find all remaining connected components of unlabeled-water and label them.

\$\endgroup\$
1
\$\begingroup\$

Following on vrinek's idea, how about growing the land (or shrinking the water) so parts you would originally be connected would be disconnected after the land is grown?

This could be done like so:

  1. Define how much do you want to grow the land: 1 hex? 2 hexes? This value is n

  2. Visit all land nodes, and set all their neighbors up to depth n to land nodes (write to a copy, as to not get an infinite loop)

  3. Run your original floodfill algorithm again to determine what is now connected and what is not

\$\endgroup\$
0
\$\begingroup\$

Do you have an rough idea of where the gulf is? If so, you can modify your flood fill to track the number of neighbouring but unexplored cells (along with a list of visited cells). It starts with 6 in a hex map and whenever that value drops below a certain point, then you know you are hitting a "opening".

\$\endgroup\$

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.