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