Skip to content

Instantly share code, notes, and snippets.

@mieko
Created September 29, 2014 05:09
Show Gist options
  • Save mieko/df86aa23c21d658a3552 to your computer and use it in GitHub Desktop.
Save mieko/df86aa23c21d658a3552 to your computer and use it in GitHub Desktop.
Marching Squares in Ruby (with Inline C implementation)
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment