Finding an object in an array

  • #1

Main Question or Discussion Point

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 [Broken]

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 [Broken]
 
Last edited by a moderator:

Answers and Replies

  • #2


As they say, DISREGARD THAT, I SUCK ....

What an incredible epiphany. I guess I just needed some rest.
A valid row would be characterized by two consecutive non-zero cells that would be either in the areas from cells 20-25 or 40-45.
 

Related Threads on Finding an object in an array

Replies
13
Views
16K
Replies
6
Views
3K
Replies
4
Views
620
Replies
3
Views
592
Replies
1
Views
2K
  • Last Post
Replies
4
Views
14K
  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
9
Views
6K
  • Last Post
Replies
10
Views
3K
Top