Marching Squares in Ruby (with Inline C implementation)

marching_squares.rb

class MarchingSquares
  STATE = { "0000" => :r, "1100" => :r, "0011" => :l, "1110" => :r,
            "0100" => :r, "1000" => :u, "1011" => :u, "1001" => :u,
            "0101" => :d, "1010" => :u, "0111" => :l, "0110" => :l,
            "0001" => :d, "0010" => :l, "1101" => :d, "1111" => :r }

  def self.find_shape(grid, w, h)
    edge_pos = grid.index('1')
    return nil if edge_pos.nil?

    y, x = edge_pos.divmod(w)

    starting_point = [x,y]
    results = []
    last_direction = nil

    begin
      # simulate a border around the image if coordinates are <0 or >w
      window = [[x-1,y-1], [x,y-1], [x-1, y], [x,y]].map do |ox, oy|
        (ox < 0 || oy < 0 || ox == w || oy == h) ? '0' : grid[oy*w+ox]
      end.join

      direction = STATE[window]
      results << [x,y] if direction != last_direction

      case direction
        when :u; y -= 1;
        when :d; y += 1;
        when :l; x -= 1;
        when :r; x += 1;
      end
      last_direction = direction
    end until [x,y] == starting_point
    results
  end

  begin
    require 'inline'
    inline :C do |builder|
      builder.prefix <<-'EOD'
        typedef enum {
          DIR_U, DIR_D, DIR_L, DIR_R
        } state_dir_t;

        typedef union {
          char c[4];
          int  i;
        } state_key_t;

        typedef struct {
          state_key_t  key;
          state_dir_t  dir;
        } state_entry_t;

        static const state_entry_t state_map[] = {
          {"0000", DIR_R}, {"1100", DIR_R}, {"0011", DIR_L}, {"1110", DIR_R},
          {"0100", DIR_R}, {"1000", DIR_U}, {"1011", DIR_U}, {"1001", DIR_U},
          {"0101", DIR_D}, {"1010", DIR_U}, {"0111", DIR_L}, {"0110", DIR_L},
          {"0001", DIR_D}, {"0010", DIR_L}, {"1101", DIR_D}, {"1111", DIR_R}
        };

        enum {
          STATE_MAP_LEN = sizeof(state_map) / sizeof(*state_map)
        };
      EOD

      builder.c_singleton <<-'EOD'
        static
        VALUE find_shape(const char* grid, int w, int h) {
          VALUE result;
          int i = 0;
          int x = 0, y = 0, fx = 0, fy = 0;

          state_key_t window = {"xxxx"};
          state_dir_t dir      = 0,
                      last_dir = 0;

          /* find first edge */
          for(i = 0; i != w * h; i++) {
            if(grid[i] == '1') {
              y = i / w;
              x = i % w;
              break;
            }
          }

          if(i == w * h) {
            return Qnil;
          }

          /* set initial/terminating position */
          fx = x;
          fy = y;

          result = rb_ary_new();

          do {
            #define VIEW(ox, oy) ((ox < 0 || oy < 0 || ox == w || oy == h) \
                                     ? '0' : grid[(oy) * w + (ox)])
            window.c[0] = VIEW(x-1, y-1);
            window.c[1] = VIEW(  x, y-1);
            window.c[2] = VIEW(x-1,   y);
            window.c[3] = VIEW(  x,   y);
            #undef VIEW

            /* Based on the window we we're looking at, find the next step */
            dir = 0;
            for(i = 0; i != STATE_MAP_LEN; i++) {
              if(window.i == state_map[i].key.i) {
                dir = state_map[i].dir;
                break;
              }
            }

            if(dir != last_dir) {
              rb_ary_push(result, rb_ary_new3(2, INT2NUM(x), INT2NUM(y)));
            }

            switch(dir) {
              case DIR_U: y--; break;
              case DIR_D: y++; break;
              case DIR_L: x--; break;
              case DIR_R: x++; break;
            }
            last_dir = dir;
          } while(! (y == fy && x == fx));
          return result;
        }
      EOD
    end
  rescue LoadError
  end
end