I've got a procedurally generated map using Voronoi cells, with a defined sea level and a believable height map.

So far, I've been successful in labelling certain geographic features: land, ocean, lakes, rivers, estuaries, confluences, mountains, and biomes. Biomes include tundra, boreal forest, grassland, and temperate forest. There are also a couple other biomes there but for my purposes they aren't important right now.

I'd like to label bays, and straits next, but I'm at a loss on how to do this properly. A bay is a recessed, coastal body of water that directly connects to the ocean.

A strait is a naturally formed, narrow waterway that connects two parts of the ocean. Basically, where two pieces of land almost touch and there's ocean on both sides. Also called a "channel".

For determining features, I can loop through any feature by type like this:

for each (var feature:Object in geography.getFeaturesByType(Geography.LAND))
 // loop through lands
 for each (var cell:Cell in feature.cells)
 // loop through cells
 for each (var neighbor:Cell in cell.neighbors)
 // loop through a cell's neighbors
 trace(neighbor.hasFeatureType(Geography.LAND));

Here's a rough idea using image processing transformations to isolate the features of interest:

1. Apply a flood fill from an ocean cell to make a mask of all ocean cells. Depending on how your rivers are set up, you might need an extra elevation or clearance criterion to keep the ocean mask from flowing inland. ;)

2. 
   

   Apply a local smoothing to the edge of this mask, keeping the connectedness/topology the same, but smoothing out small noisy coastline features that can be distracting. This lets us focus on big bays over tiny inlets. You can use the width of your filter kernal / number of iterations to finely control the scale of features you preserve.

   
   
   

   Here I applied a median filter a few times. Cellular automata are another popular way to erode smooth shapes from a noisy input.

   
   

3. Turn the mask into a distance field, where each cell stores its distance from the smoothed coastline.

Now we see some promising feature highlights. In a signed distance field, both bays and straits show up as sharp ridges, with distance falling off to the sides. We can use an edge detection filter to pop out these ridges:

You can then distinguish between bays and straits by following the ridge to determine its connectivity. A bay is a ridge that runs toward the coast, getting shallower and shallower (in distance from land) until it ends in a point. A strait is a ridge that connects a high-distance region to another high-distance region, going through a lower-distance region along the way.

Or, another way is to assign each island an ID (connected component search), then when you're making your distance field, propagate "closest island ID" alongside the distance frontier. A bay or inlet is then a ridge in water adjacent to the same landmass on both sides, while a channel is a ridge that separates water adjacent to two different landmasses.

You can set minimum & maximum distance-to-shore or length-of-ridge constraints to control which features to label, if you need to exclude excessively narrow/wide straits for instance.

Basically, you need to think about what you mean, precisely, by a bay or strait, and why you want to differentiate them (is it for AI calculations, or to label landmarks, or something else?). Play around with a few definitions to find the one that looks best to you. Then, formulate conditions to check on your Voronoi cells. A few suggestions:

Bay

• Any ocean cell that only connects to a single other ocean cell


• OR: Any ocean cell that connects to more land than ocean cells, with all ocean cells next to each other


• OR: Same as above, but with a criterion based on border length (e.g. twice as much land as water border)

Strait

• Any ocean cell that connects to exactly two ocean cells which are not next to each other


• OR: Any ocean cell that connects to two land cells that don't belong to the same landmass (you need to find out which land cells are connected first, and assign IDs to each landmass)


• OR: March around the border, and count land/water and water/land transitions. You need at least two of each.


• Depending on your method and what you want to do with the categories, you might want to eliminate straits that only lead to a bay, or label them as bay instead.