How to find a specific "shape" in a 2D array?

Question

JavaScript

Hey!
I have a two dimensional array like this:

var matrix = new Array(
[1, 0, 0, 1, 1, 1, 0, 1, 0, 0],
[1, 0, 0, 1, 1, 0, 0, 1, 1, 0],
[0, 1, 1, 1, 0, 1, 0, 0, 0, 1],
[1, 0, 0, 1, 1, 1, 0, 1, 0, 0]
);

It is required to search for certain "shapes" inside an array, for example to find

[0, 0],
[0, 0]

or

[0],
[0],
[0, 0, 0]

Tell me, is there any ready-made algorithms for such a search?

Answer 1

Too few inputs:
- what is the average/maximum field size;
- what is the average / maximum size of the desired element;
- what is invariant between search events: field, searched element or neither.
Depending on the answers, perhaps your problem is easiest to solve by exhaustive search, perhaps it is enough to do pre-calculations (cache), or perhaps powerful optimized algorithms are needed, incl. with heuristics. While there is no clarification on the input data, it is very difficult to answer in detail.

Answer 2

If the length of the strings is less than 32, then you can search using bit masks. But to select the optimal algorithm, you need to know the full set of search masks. Do the figures you are looking for consist only of zeros, or can there be combinations of zeros and ones?

Answer 3

Haar Cascades at your service.

Answer 4

I would look for these patterns as substrings. We build additional an array by where two and three zeros occur in a row, two and three zeros in a column. Then we look for where they form shapes. You can write on the forehead, you can use the ILC.

Answer 5

hit or miss transform
image processing / feature extraction / template matching
feature_detection
there is something similar for the aforge c# library, maybe you can get some ideas there
you can: -
search for a long line from a figure
- build an integral image and search for an enclosing rectangle with the sum within from the figure (then you can also Haar, or something specific: corner - difference of squares)
-calculate the sums in rows and columns, look for projections
of the solution in the forehead:
-walk the figure (and, possibly, the mask) through the array:
4 cycles: 2 by coordinates and 2 by shape
-go around the base point and an array of relative offsets and values:
3 cycles: 2 by coordinates and 1 by points