Finding an object in an array

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:
Re: Finding an "object" in an array

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 for: Finding an object in an array

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top