Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Finding an object in an array

  1. Feb 23, 2009 #1
    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: May 4, 2017
  2. jcsd
  3. Feb 24, 2009 #2
    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.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook