Algorithm to find the largest land-mass a city is connected to?

Question

I have a black and white picture of the world map.

I convert the pixels to a grid of binary values (0 for water, and 1 for land) indexed by coordinates (i, j). Now, say I randomly pick a point on land, and this time it's somewhere in Texas, USA. I want to know the (i, j) coordinates of all the points I can travel to without having to cross water. In this case, it would be any (i, j) in all of North and South America (minus any surrounding islands).

(The motivation behind this is that I'm trying to implement an SIR infection model in c in parallel.)

Many thanks for your help.

Edit: I'd also be interested if there are any approximate methods (I'm not overly fussed if some tiny offshore islands were included by mistake.), perhaps by a meshing method like quadtrees? Thanks again.

Answer 1

You're looking for a flood fill algorithm. It can be done recursively, or manually maintaining a stack, or using a queue.