http://math.stackexchange.com/q/1940277/86776

inverse.rb

# inverse
#
# http://math.stackexchange.com/q/1940277/86776

load "set.rb"

SX = 25
SY = 25

def empty_graph()
  Set.new
end

def add(g, x, y)
  g.add([x, y])
end

def random_graph()
  g = empty_graph()
  y_old = -1
  (0..(SX-1)).each do |x|
    if y_old >= (SY-1)
      break
    end
    y = y_old
    begin
      # random value from [0, 4]
      y += rand(5)
    end until y > y_old
    if y < SY
      add(g, x, y)
    end
    y_old = y
  end
  g
end

def invert(g)
  gi = empty_graph()
  g.each do |p|
    pi = [p[1], p[0]]
    gi.add(pi)
  end
  gi
end

def interpolate(g)
  g2 = empty_graph()
  n = g.size
  if n == 0
    return g2
  elsif n == 1
    c = g.to_a[0][1]
    (0..(SX-1)).each do |x|
      g2.add([x,c])
    end
    return g2
  end
  a = g.to_a
  i = 0
  begin
    pi = a[i]
    xi = pi[0]
    yi = pi[1]
    pip = a[i+1]
    xip = pip[0]
    yip = pip[1]
    (xi..(xip-1)).each do |x|
      lambda = (x - xi) * (1.0 / (xip - xi))
      x2 = ((1-lambda) * xi + lambda * xip).round
      y = ((1-lambda) * yi + lambda * yip).round
      g2.add([x2,y])
    end
    i += 1
  end while i + 1 < n
  g2
end

def plot_line()
  print '+' + '-' * (2*SX) + "+\n"
end

def plot(g)
  puts "size #{SX} x #{SY}"
  plot_line()
  y = SY - 1
  begin
    print "|"
    (0..(SX-1)).each do |x|
      print g.include?([x,y]) ? '()' : '  '
    end
    print "|\n"
    y -= 1
  end until y < 0
  plot_line()
end

g = random_graph()
puts "#{g.to_a}"
gi = invert(g)
puts "#{gi.to_a}"
plot(g)
plot(gi)
gi2 = interpolate(gi)
plot(gi2)