Turn 2D boolean array into (rectilinear) polygons Challenge

Write a program which, given a 2-dimensional boolean array (equivalently, a monochromatic bitmap), outputs a series of polygons that describe the outline of the region that is “true” (1).

The input is provided as a sequence of '#' (hash), ' ' (space) and \n (newline) characters. Lines may differ in length, in which case the missing parts are assumed to be spaces. The output should be a (newline-separated) list of polygons, each polygon represented by a (comma-separated) list of coordinates.

Examples &amp; Requirements


The co-ordinates must be listed in clockwise order. Input:

#


Acceptable outputs include:

(0,0), (1,0), (1,1), (0,1)

(1,0), (1,1), (0,1), (0,0)

(1,1), (0,1), (0,0), (1,0)

(0,1), (0,0), (1,0), (1,1)

Disjoint regions must return multiple polygons. Input:

# #


Example output (actual output must consist of two lines):

(0,0), (1,0), (1,1), (0,1)
(2,0), (3,0), (3,1), (2,1)

Holes in a polygon must be listed as a separate polygon, but in anti-clockwise order. Input:

###
# #
###


Example output:

(0,0), (3,0), (3,3), (0,3)
(1,1), (1,2), (2,2), (2,1)

You are free to choose whether diagonally adjacent vertices join up or not. Input:

#
 #


Example output:

(0,0), (1,0), (1,1), (0,1)
(1,1), (2,1), (2,2), (1,2)


or

(0,0), (1,0), (1,1), (2,1), (2,2), (1,2), (1,1), (0, 1)

The lists of coordinates need not be optimally short. For example:

##


Acceptable outputs:

(0,0), (2,0), (2,1), (0,1)

// Redundant coordinates along a straight line are acceptable
(0,0), (1,0), (2,0), (2,1), (1,1), (0,1)

// Duplicate start- and end-point are acceptable
(0,0), (2,0), (2,1), (0,1), (0,0)



As usual, shortest program “wins”.
Perl, 345 311 265 chars

s!.!$i{$x++}=$&amp;eq'#'!ge,$x=$r+=64for&lt;&gt;;sub a{$d+=@_||3;$d%=4;$y=$x%64;$z=$x&gt;&gt;6;$c.=", ($y,$z)";}for$x(keys%i){if($c=!$v{$x}&amp;$i{$x}&amp;!$i{$x-1}){$i{($x+=(1,64)[$d^3])-(64,65,1)[$d]}?$i{$x-(65,1,0,64)[$d]}?a 1:($x-=(64,1)[$d]):a while$d||!$v{$x}++;print substr$c.$/,3}}


Limitations

Assumes that the input is no wider than 64 characters (but its height is in principle unbounded). This can be extended to 512 or 8192 or any other power of two by changing the relevant constants, making the code only slightly longer.

Slightly more readable version

Some credit goes to mob because the first line is my re-use of his idea in lasers. The rest is entirely my work.

# Read “%i”nput (this line is essentially mob’s idea, see above)
s!.! $i{$x++} = $&amp; eq '#' !ge, $x = $r += 64 for &lt;&gt;;

# Subroutine to add a vertex to the current polygon and change the current “$d”irection
sub a
{
    $d += @_ || 3;
    $d %= 4;
    $y = $x % 64;
    $z = $x &gt;&gt; 6;
    $c .= ", ($y,$z)";
}

for $x (keys %i)
{
    # Go to the next “upward-pointing” edge that we haven’t already “%v”isited.
    if ($c = !$v{$x} &amp; $i{$x} &amp; !$i{$x-1})
    {
        # We’re going in the “$d”irection of 0=up, 1=left, 2=down, 3=right
        $i{($x += (1,64)[$d^3]) - (64,65,1)[$d]}
        ?  $i{$x - (65,1,0,64)[$d]}
           ?  a 1               # take a 90° turn to the left
           : ($x -= (64,1)[$d]) # move straight ahead
        : a                     # take a 90° turn to the right

        # Only stop if the current “$d”irection is “up” and we encounter a “%v”isited edge
        # (which necessarily is the one we started from)
        while $d || !$v{$x}++;

        # Remove “1, ” and output this polygon
        print substr $c.$/, 3
    }
}


Edits


(345 → 312) Realised there’s no need to update $x when taking a turn because the next iteration will already do it
(312 → 311) Change 1=down,2=left to 1=left,2=down and update $d via XOR instead of directly
(311 → 265) Remove repetition of the innermost expression and use arrays to parametrise it