identifying custom shapes in a 2D grid

Question

Dear stackoverflowers.

So, let's say there's a grid, whose values at certain x and y represent whether there is a tile there (1) or it's missing (0).

For example,

100110100010
100100111110
111110000000
000010000000

And there are some already known shapes A, B and C, for example,

(A)  (B)  (C)
  1  1     1
111, 111, 11

So what I am trying to achieve is to identify which 1's on a grid belong to which shape. All of 1's should be used up, exact number of shapes is known, but rotation (no mirroring) is allowed, so I guess it's better to add rotated versions and think, that some shapes won't be found on grid.

So, the expected result would be (it's known that it should be exactly 1xA, 2xB, 2xC):

A00CC0B000C0
A00C00BBBCC0
AABBB0000000
0000B0000000

If there are several possible matches, any would suit, as long as every tile gets allocated to it's own shape.

Moreover, finding out whether a tile is present or not ("uncovering") is an expensive operation (but results are cached, tiles don't appear out of nowhere), so I am actually seeking for a way to identify them with as minimum number of "uncoverings" as possible. (It's okay if it's not optimum, just identifying shapes would be great).

Obviously, set of known shapes might change (but it will be known by the time of implementing and it will stay constant, so it's possible to tune up code for a particular set of tiles or develop some search strategies), but it won't be large (~5-6) and grid is quite small too (~15x15).

Thanks!

you could possibly use this, http://stackoverflow.com/questions/16326318/finding-blocks-in-arrays, or this, http://stackoverflow.com/questions/17795711/creating-sets-of-similar-elements-in-a-2d-array/, to start with and then try to match the shapes with the collected objects. — גלעד ברקן, Sep 05 '13 at 16:20
@groovy I've thought somebody will just come up with a link or two describing similar problem and solution/algorithm or some hints (better that a bruteforce algorithm), as I believe am I not the first trying to solve this kind of a problem. Neither it's a homework, nor a freelance work, I am not asking for a full code, I've just provided as much info as possible :) — , Sep 05 '13 at 18:12
Ok, so I looked both of suggestions, I don't think BFS/DFS or Disjoint-Sets will do any good here, or at least I can't come up quickly with an idea how they might be useful here. — , Sep 05 '13 at 18:24

score 0 · Accepted Answer · edited May 23 '17 at 11:49

Using the ideas here and/or here (I guess using this one, the object types would be 0 and 1), one way to do it might be to try and match your own patterns against the catalog of collected objects. To take you own example,

100110100010
100100111110
111110000000
000010000000

Shapes A, B and C:

(A)           (B)             (C)
  1      1     1       111     1      11
111  or  1     111  or   1     11  or  1 
         11

The first collected object might be,

1  11
1  1
11111
    1    

=> represented as a set of numbers: [(0,0),(0,1),(0,2),(1,2)..etc]
   (the objects need not start or include (0,0) but object 
    bounds seem needed to calibrate the pattern matching)

Testing object A against the top left of the object would match [(0,0),(0,1),(0,2),(1,2)]. After A is matched, the program must find a way to calibrate the remaining points - the bottom right corner will effectively be measured as (2,3) rather than (4,3) - testing the bottom right of the remaining points in the object would match object B. Continue in a similar vein to match all, trying different combinations if a total match is not found.

Yep, I've thought in a similar fashion but wondered whether there's a more effective algorithm (maybe some prior data processing?). Thanks for putting all ideas concisely! — , Sep 05 '13 at 19:41
hmm, not sure about prior data processing, but i remembered you may be able to pattern-match fast using bit-representation, as in this test for a tic-tac-tow win: http://stackoverflow.com/questions/18548265/testing-tic-tac-toe-win-condition/18549674#18549674 — גלעד ברקן, Sep 05 '13 at 21:22

identifying custom shapes in a 2D grid

1 Answers1