Render the top-down view of a hip roof in ASCII

Question

First, some terminology (source):

• A hip roof is (quoting Wikipedia) "a type of roof where all sides slope downwards to the walls, usually with a fairly gentle slope"
• A slope is a planar surface that is a part of the roof
• A ridge is an edge where two opposite roof slopes meet
• A hip is a convex edge where two slopes belonging to perpendicular walls meet
• A valley is a concave edge where two slopes belonging to perpendicular walls meet
• Hips and valleys shall be collectively referred to as diagonal edges.

Possible input:

 ** * ***
******** 
 ** *  **

Corresponding output:

    +-------+   +---+   +-----------+
    |\     /|   |\ /|   |\         /|
    | \   / |   | V |   | \   ^---< |
    |  \ /  |   | | |   |  \ / \   \|
+---+   V   +---+ | +---+   X   +---+
|\   \  |  /     \|/     \ / \  |
| >---> | <-------X-------V   > |
|/   /  |  \     /|\         /| |
+---+   ^   +---+ | +-------+ | +---+
    |  / \  |   | | |       | |/   /|
    | /   \ |   | ^ |       | /---< |
    |/     \|   |/ \|       |/     \|
    +-------+   +---+       +-------+

A couple more test cases:

** ***   *    *   * *
*       ***   *****  
    ** *****  *****  
* *  *  ***  *** *** 
* ****   *     * *   

Corresponding outputs :

+-------+   +-----------+           +---+               +---+           +---+   +---+
|\     /|   |\         /|           |\ /|               |\ /|           |\ /|   |\ /|
| \---< |   | >-------< |           | V |               | V |           | V |   | X |
| |\   \|   |/         \|           | | |               | | |           | | |   |/ \|
| | +---+   +-----------+       +---+ | +---+           | | +-----------+ | |   +---+
| | |                           |\   \|/   /|           | |/             \| |
| ^ |                           | \   V   / |           | <               > |
|/ \|                           |  \     /  |           |  \             /  |
+---+           +-------+   +---+   \   /   +---+       |   \-----------/   |
                |\     /|   |\   \   \ /   /   /|       |   |\         /|   |
                | >---/ |   | >--->   X   <---< |       |   | \       / |   |
                |/   /| |   |/   /   / \   \   \|       |   |  \     /  |   |
+---+   +---+   +---+ | |   +---+   /   \   +---+   +---+   ^   +---+   ^   +---+
|\ /|   |\ /|       | | |       |  /     \  |       |\   \ / \  |   |  / \ /   /|
| V |   | V |       | | |       | /   ^   \ |       | >---V   > |   | <   V---< |
| | |   | | |       | | |       |/   /|\   \|       |/       /| |   | |\       \|
| | |   | | +-------+ | |       +---+ | +---+       +-------+ | |   | | +-------+
| | |   | |/         \| |           | | |                   | | |   | | |
| ^ |   | /-----------\ |           | ^ |                   | ^ |   | ^ |
|/ \|   |/             \|           |/ \|                   |/ \|   |/ \|
+---+   +---------------+           +---+                   +---+   +---+

Your input will be a bitmap - a 2D array of square pixels - of the area that should be covered by roof. You may assume the boundary of this area will be a Jordan curve - that is, continuous and non-self-intersecting - that is, the roofed area will be continuous, without holes and there will never be four walls meeting at a single point. Valid input formats include a single string with newline separators, a list of strings and a 2D array of chars or booleans.

The rules of building the roof are:

• Each straight segment of the roofed area (henceforth referred to as a wall) shall have exactly one adjoining slope. The slope shall rise away from the wall. Each slope shall have at least one adjoining wall, and all walls adjoining to a slope must be collinear.
• All slopes shall have the same (nonzero) angle against the horizontal surface. That is, they must have the same pitch.
• The slopes shall form a surface whose boundary is the boundary of the roofed area. That is, no surfaces other than the slopes may be used.
• Any scenario where more than one solution (up to vertical scaling) is allowed by this specification is considered a bug in the specification. Any corrections apply retroactively.

Equivalently, the roof may be defined by the rule that each point of the roof is placed as high as possible without exceeding the maximum slope for that roof as measured using the Chebyshev distance in top-down view.

Your output shall be an ASCII art representation of the roof - either a single string containing newline characters or an array of strings, each denoting a single line of the output. The roof shall be rendered in top-down view at a 4x scale - that is, each square of the floor-plan should affect a 5x5 area of the output such that the corners of this 5x5 area are shared with neighboring squares (such that each corner character is affected by four different input squares), as indicated by the example output. Extra whitespace is allowed as long as the output shape is preserved. The characters in output shall be:

• an environment-defined newline marker shall be used (usually U+000A, U+000D or a pair of both) if the output is in the form of a single string
• (U+0020 space) represents a point outside a roofed area or a point interior to a slope
• + (U+002B plus sign) represents a point with two perpendicular walls adjoined to it
• - (U+002D hyphen-minus) represents a wall or a ridge oriented horizontally (east-west)
• / (U+002F solidus) represents a hip or a valley oriented north-east to south-east, or a point adjoined to two of those
• < (U+003C less-than sign) represents a point with two diagonal edges adjoined to it on the east
• > (U+003E greater-than sign) represents a point with two diagonal edges adjoined to it on the west
• \ (U+005C reverse solidus) represents a hip or a valley oriented north-west to south-east, or a point adjoined to two of those
• ^ (U+005E circumflex accent) represents a point with two diagonal edges adjoined to it on the south
• V (U+0056 latin capital letter v) represents a point with two diagonal edges adjoined to it on the north
• X (U+0058 latin capital letter x) represents a point with diagonal edges adjoined to it on all four sides
• | (U+007C vertical bar) represents a wall or a ridge oriented vertically (north-south)

Note that it is not possible for an odd number of diagonal edges to end at the same point (except on walls). We can visualize that by partitioning the neighborhood of each point into north slope + south slope and into east slope + west slope. The boundary between both partitions has to be composed of diagonal edges.

If your environment uses a character encoding incompatible with ASCII, you may use the equivalent characters (same glyph or closest available) in the character encoding your environment uses.

The following (ugly) reference implementation in Ruby is normative with respect to the non-whitespace output. Note particularly the render method:

def pad ary
  row = ary.first.map{-1}
  ([row] + ary + [row]).map{|r| [-1] + r + [-1]}
end

def parse str
  str.split("\n").map{|r| r.chars.map(&{" " => -1, "*" => Float::INFINITY})}
end

def squares ary, size
  ary.each_cons(size).map do |rows|
    rows.map{|row| row.each_cons(size).to_a}.transpose
  end
end

def consmap2d ary, size
  squares(ary, size).map{|sqrow| sqrow.map{|sq| yield sq}}
end

def relax ary
  loop do
    new = consmap2d(pad(ary), 3){|sq| sq[1][1] == -1 ? -1 : sq.flatten.min + 1}
    return new if new == ary
    ary = new
  end
end

def semidouble ary, op
  ary.zip(ary.each_cons(2).map{|r1,r2|r1.zip(r2).map(&op)}).flatten(1).compact.transpose
end

def heightmap str
  relax(semidouble(semidouble(semidouble(semidouble(pad(parse str),:max),:max),:min),:min))
end

def render heightmap
  puts consmap2d(heightmap, 3){|sq|
    next " " if sq[1][1] == -1
    hwall = sq[0][1] == -1 || sq[2][1] == -1
    vwall = sq[1][0] == -1 || sq[1][2] == -1
    next "+" if hwall && vwall
    next "-" if hwall
    next "|" if vwall
    next "+" if sq.flatten.min == -1

    nws = sq[0][1] == sq[1][0]
    nes = sq[0][1] == sq[1][2]
    sws = sq[2][1] == sq[1][0]
    ses = sq[2][1] == sq[1][2]

    next "X"  if nws && nes && sws && ses
    next "V"  if nws && nes
    next "^"  if sws && ses
    next ">"  if nws && sws
    next "<"  if nes && ses
    next "/"  if nes && sws
    next "\\" if nws && ses
    next " "  if sq[0][1] != sq[2][1] || sq[1][0] != sq[1][2]
    next "|"  if sq[0][1] == sq[1][1]
    next "-"  if sq[1][0] == sq[1][1]
    ??
  }.map(&:join)
end

render heightmap $<.read if __FILE__ == $0 

Answer 1

Python 2, 500 bytes

z=input()
W=4*len(z[0])+1
H=4*len(z)+1
R=range
s=[-~W*[0]for _ in R(-~H)]
for y in R(H/4):
 for x in R(W/4):
        for h in R(25):s[y*4+h%5][x*4+h/5]|=z[y][x]
F=[(x/3-1,x%3-1)for x in[1,7,3,5,0,6,8,2]]
exec'for y in R(H):\n for x in R(W):s[y][x]+=0<s[y][x]<=min(s[y+d][x+e]for(e,d)in F)\n'*H
for y in R(H):
 l=''
 for x in R(W):h=s[y][x];a=[s[y+d][x+e]for(e,d)in F[:4]];l+=r' XabcVde^f ||g>h\\+//+<<jk<l//+\\+>>m --^^oVVqrX'[h and int(''.join(`int(n==h)`for n in a),2)*3+((h==1)*2or max(a)==h)+1]
 print l

Tired of golfing it down, and I got to a nice round score, so here it is.

The eight-space indentation is a tab.

Pass a binary matrix over STDIN, like so:

python2.7 roof.py <<<"[[1,1,0,1,1,1,0,0,0,1,0,0,0,0,1,0,0,0,1,0], [1,0,0,0,0,0,0,0,1,1,1,0,0,0,1,1,1,1,1,0], [0,0,0,0,1,1,0,1,1,1,1,1,0,0,1,1,1,1,1,0], [1,0,1,0,0,1,0,0,1,1,1,0,0,1,1,1,0,1,1,1], [1,0,1,1,1,1,0,0,0,1,0,0,0,0,0,1,0,1,0,0]]"