Island Golf #1: Circumnavigation This is the first in a series of Island Golf challenges. Next challenge

Given an island in ASCII-art, output an optimal path to circumnavigate it.

Input

Your input will be a rectangular grid consisting of two characters, representing land and water. In the examples below, land is # and water is ., but you may substitute any two distinct characters you wish.

...........
...##......
..#####....
..#######..
.#########.
...#######.
...#####.#.
....####...
...........


There will always be at least one land tile. The land tiles will all be contiguous (i.e. there's only one island). The water tiles will also be contiguous (i.e. there are no lakes). The outer border of the grid will all be water tiles. Land tiles will not be connected diagonally: i.e., you will never see something like

....
.#..
..#.
....


Output

Your code must output the same grid, with a shortest circumnavigation drawn on it. In the examples below, the circumnavigation path is drawn with o, but you may substitute any character as long as it is distinct from your land and water characters.

A circumnavigation is a simple closed curve, drawn entirely on water tiles, that fully encircles all land tiles on the grid. Diagonal connections are allowed. For instance, this is a circumnavigation of the above island (but not a shortest one):

.ooooo.....
o..##.oo...
o.#####.o..
o.#######o.
o#########o
ooo#######o
..o#####.#o
..oo####..o
....oooooo.


The length of a circumnavigation is computed as follows: For every pair of adjacent tiles on the path, if they are connected horizontally or vertically, add 1; if they are connected diagonally, add √2. The length of the above path is 22 + 7√2 (≈ 31.9).

A shortest circumnavigation is a circumnavigation with the shortest possible length. Your program should output any one path that satisfies this condition. For most islands, there will be multiple possible solutions. Here is one solution for the above island, with length 10 + 13√2 (≈ 28.4):

...oo......
..o##oo....
.o#####oo..
.o#######o.
o#########o
.o.#######o
..o#####.#o
...o####.o.
....ooooo..


Details

Your solution may be a full program or a function. Any of the default input and output methods are acceptable.

Your input and output may be a multiline string or a list of strings. If your language has a character type distinct from single-character strings, you may substitute "list of characters" for "string" in the previous sentence. If your language needs to input the height and/or width of the grid, you may do so. Your output may (optionally) have a single trailing newline. As mentioned above, you may use any three distinct characters in place of #.o (please specify in your submission which characters you're using).

Test cases

A. Islands with unique shortest circumnavigations:

...
.#.
...

.o.
o#o
.o.

......
.####.
......

.oooo.
o####o
.oooo.

......
......
..##..
...#..
......
......

......
..oo..
.o##o.
..o#o.
...o..
......

.......
.#####.
...#...
...#...
.#####.
.......

.ooooo.
o#####o
o..#..o
o..#..o
o#####o
.ooooo.

.......
...#...
...#...
.#####.
...#...
...#...
.......

...o...
..o#o..
.o.#.o.
o#####o
.o.#.o.
..o#o..
...o...

.......
.#####.
.##..#.
..#..#.
.......

.ooooo.
o#####o
o##..#o
.o#..#o
..oooo.


B. Example of an island with multiple possible solutions:

........
....##..
...####.
..###...
.#####..
.#####..
..##....
........


Possible outputs:

....oo..
...o##o.
..o####o
.o###.o.
o#####o.
o#####o.
.o##oo..
..oo....

....oo..
...o##o.
..o####o
.o###.o.
o#####o.
o#####o.
.o##.o..
..ooo...

....oo..
...o##o.
..o####o
.o###..o
o#####.o
o#####o.
.o##oo..
..oo....

....oo..
...o##o.
..o####o
.o###..o
o#####.o
o#####o.
.o##.o..
..ooo...


C. Large test case as a Gist



This is code-golf: the shortest code in each language wins.
Mathematica (version 9), 165 bytes

The nice, short ConvexHullMesh function that Greg Martin used was only introduced in Mathematica version 10, so I thought I'd make an attempt without it, using my ancient Mathematica version 9. I managed to get it slightly shorter, though! It's a function that takes and returns a list of strings (with ., # and o as the symbols).

""&lt;&gt;#&amp;/@("o"MorphologicalTransform[MorphologicalComponents[#,Method-&gt;"ConvexHull"],Max[#(1-#[[2,2]])CrossMatrix@1]&amp;]+"#"#/.{0-&gt;"."})&amp;[Characters@#/.{"."-&gt;0,"#"-&gt;1}]&amp;


Explanation:


First, Characters@# /. {"."-&gt;0, "#"-&gt;1} turns the input into a matrix of 0s and 1s.
"o"MorphologicalTransform[MorphologicalComponents[#,Method-&gt;"ConvexHull"],Max[#(1-#[[2,2]])CrossMatrix@1]&amp;]+"#"# then uses Mathematica's powerful (but extremely byte-heavy…) image processing capabilities to first fill in the island's convex hull (which is the shape you'd get if you stretched a piece of string around it), and then take its boundary. We then multiply this matrix by the string "o" to get a matrix of 0s and "o"s (thanks to Mathematica's impressive adaptability about types), and add this to "#" times the matrix of the island.
Finally, ""&lt;&gt;#&amp; /@ (... /. {0-&gt;"."}) turns this matrix of "o"s, "#"s and 0s into a matrix of "o"s, "#"s and "."s, and joins each row into a string.


When we test this on example B, we get the output

{"....oo..",
 "...o##o.",
 "..o####o",
 ".o###..o",
 "o#####o.",
 "o#####o.",
 ".o##oo..",
 "..oo...."}


[Edit, thanks to Greg Martin:] If we're allowed to use arrays of characters instead of lists of strings, we can trim this down to 144 bytes:

"o"MorphologicalTransform[MorphologicalComponents[#,Method-&gt;"ConvexHull"],Max[#(1-#[[2,2]])CrossMatrix@1]&amp;]+"#"#/.{0-&gt;"."}&amp;[#/.{"."-&gt;0,"#"-&gt;1}]&amp;