2D rendering - algorithm to identify islands and apply "beaches"?

Question

I'm playing with 2D games programming. My toy project is a sailing game with explorable islands and more, but at the moment I'm trying to find the best way to apply "beaches" (i.e. soft ends) to the otherwise fairly rough islands. Tile size is 64x48.

My present solution is to iterate through each tile and look for surrounding tiles, and based on their surroundings, replace the water-tile with the correct texture.

I realise that this is a very flawed approach as it is:

• Incredibly inefficient as the surround method is invoked for every tile, even those affected by the change
• The order of execution might imply that some tile changes are overwritten

Do you guys have an idea how I might get around and solve this in a better way?

Thank you!

edit

This algorithm is performed when the map is being loaded.

Answer 1

An algorithm to detect borders (but not corners at first) in a single pass per line / row would be:

for each horizontal line
  previousTag = getTag( first line pixel ) // land or water in our example
  for each pixel of the line
    currentTag = getTag( this pixel )
    if ( previousTag == currentTag ) 
       continue // not a border
    else 
       // We got a vertical border, do what is needed

    previousTag = currentTag
  endforeach
endforeach

Same goes for vertical lines (instead of incrementing x, you increment y. We can here also know if we got a corner instead of a vertical border:

for each vertical line
  previousTag = getTag( first line pixel ) // land or water in our example
  for each pixel of the line
    currentTag = getTag( this pixel )
    if ( previousTag == currentTag ) 
       continue // not a border
    else 
       if ( pixel on the right or on the left is a border )
         // we got a corner
       else
         // we got a horizontal border

    previousTag = currentTag
  endforeach
endforeach

This should be a pre-process, unless your terrain is dynamic. Don't do that each frame anyway!