Turn 2D boolean array into (rectilinear) polygons

Question

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 & Requirements

1. 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)
   

2. 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)
   

3. 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)
   

4. 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)
   

5. 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”.

Answer 1

Perl, 345 311 265 chars

s!.!$i{$x++}=$&eq'#'!ge,$x=$r+=64for<>;sub a{$d+=@_||3;$d%=4;$y=$x%64;$z=$x>>6;$c.=", ($y,$z)";}for$x(keys%i){if($c=!$v{$x}&$i{$x}&!$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++} = $& eq '#' !ge, $x = $r += 64 for <>;

# 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 >> 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} & $i{$x} & !$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

Answer 2

Python, 607 characters

The code works by keeping a list of the boundaries discovered so far as it processes # symbols in input order. The boundaries are stored in a table E which maps edges (4-tuples of x_start,y_start,x_end,y_end) to a list of edges which form the boundary of a polygon. As we process each new #, it may be connected to a polygon above (p) or to its left (q). The code finds p and q using E and then merges the boundary of the current # (r) with p and q, if they exist. The case where p==q generates holes.

import sys
x=y=N=0
E={}
def P(L):
 if L:print ', '.join(map(lambda z:str(z[:2]),L))
while 1:
 r,a,b,c=[(x,y,x+1,y),(x+1,y,x+1,y+1),(x+1,y+1,x,y+1),(x,y+1,x,y)],(x+1,y,x,y),(x,y,x,y\
+1),sys.stdin.read(1)
 if not c:break
 p,q=E.get(a),E.get(b)
 if'#'==c:
  if p:
   i=p.index(a)
   if q:
    j=q.index(b)
    if p==q:
     if i<j:P(p[i+1:j]);p[i:j+1]=r[1:3]
     else:P(p[i+1:]+p[:j]);p[i:]=r[1:3];p[0:j+1]=[]
    else:p[i:i+1]=r[1:3]+q[j+1:]+q[:j]
   else:p[i:i+1]=r[1:]
  elif q:j=q.index(b);q[j:j+1]=r[:3];p=q
  else:p=r
  for e in p:E[e]=p
 x+=1
 if'\n'==c:y+=1;x=0
for L in E.values():
 if L:P(L);L[:]=[]