Haxx0rm4ster
- 37
- 0
Finding an "object" in an array
Say I have a vector of 64 cells. Each cell can have a value of 0-7 (each represents a color). Inside this vector I may have an "object" which would be defined as a set of consecutive non-zero (zero=black) cells with the same value. The object is no longer than 45 consecutive cells and no smaller than 25. This object however might have some of its parts overlapped by another one
like in the following picture:
http://img54.imageshack.us/img54/8366/captureu.png
However the object does not have 2 consecutive cells that are overlapped.
What'd be an efficient way to find out whether there IS an object in the vector or not?
It doesn't have to be completely accurate, but the more accurate and efficient, the better.
I thought of getting 4 cells from 2 areas in the picture say cells # 20 21 22 23 and 40 41 42 43 then if cells 21,22 or 21,23 or 20,22 are of equal value (and not black/0) there could be an "object." If no object was identified in that first area, then I'd check the second one.
However if for example 20,22 are the same color, it'll raise a false alarm even though the rest of the cells in the entire vector maybe black.
And the huge catch, is that this is part of a bigger project I have to code in MIPS, so the algorithm would have to be assembly friendly, and take as few instructions as possible.
This is my current MIPS assembly implementation. Maybe if I can't get help with a better algorithm, I may be advised on how to implement it more efficiently. I'm focusing more on the dynamic instruction length of the algorithm than anything else.
http://pastebin.com/d75241b9e
Say I have a vector of 64 cells. Each cell can have a value of 0-7 (each represents a color). Inside this vector I may have an "object" which would be defined as a set of consecutive non-zero (zero=black) cells with the same value. The object is no longer than 45 consecutive cells and no smaller than 25. This object however might have some of its parts overlapped by another one
like in the following picture:
http://img54.imageshack.us/img54/8366/captureu.png
However the object does not have 2 consecutive cells that are overlapped.
What'd be an efficient way to find out whether there IS an object in the vector or not?
It doesn't have to be completely accurate, but the more accurate and efficient, the better.
I thought of getting 4 cells from 2 areas in the picture say cells # 20 21 22 23 and 40 41 42 43 then if cells 21,22 or 21,23 or 20,22 are of equal value (and not black/0) there could be an "object." If no object was identified in that first area, then I'd check the second one.
However if for example 20,22 are the same color, it'll raise a false alarm even though the rest of the cells in the entire vector maybe black.
And the huge catch, is that this is part of a bigger project I have to code in MIPS, so the algorithm would have to be assembly friendly, and take as few instructions as possible.
This is my current MIPS assembly implementation. Maybe if I can't get help with a better algorithm, I may be advised on how to implement it more efficiently. I'm focusing more on the dynamic instruction length of the algorithm than anything else.
http://pastebin.com/d75241b9e
Last edited by a moderator: