Image searching...

[FireSBurnsmuP]

Alright, I'm developing a program that is going to take in .pbm image files, manipulate them, and output them in .ppm (P3) format.

That's all fine and good; I've got that down.
However, I'm looking for suggestions on good and efficient ways to figure out if 2 points ( row , col ) are connected in an object within an object. By object I mean a region of all one colour, that has no diagonal connectivity. If I figure this out fast enough, I will implement a diagonal-connectivity checker as well.

Any suggestions? I was thinking about using an STL stack to store my moves, in case I end up at a dead end, so I can go back a few moves and take another possible road. something like this (but I don't think this is efficient enough for me.), conceptually.
push all possible moves in order W , S , E , N - impossible moves are moves that go outside the region.
These will be something like a struct I'll call move, like this:

struct point
{
     int row;
     int col;
};
struct move
{
     point here;
     point next;
};

pop off the last possibility and go that way.
repeat.
if I run out of possibilities for moves (a dead end) pop and set my position to the next in the first alternative possibility and go forth.

However, it seems to me that if I were to go that way, with the specific order of directions to take, it would be horribly inefficient.

Any ideas? I'll be much obliged. I just wanna bounce ideas.

[Duoas]

I'm not sure exactly what you are trying to do.

What exactly do you mean by "moves"? By "object" do you mean a raster color run (a horizontal line of the same color)?

What is the purpose of doing this? The ppm format is as horribly inefficient as pbm, the only real difference is that it stores RGB colors instead of on/off. It has no compression or organization other than a simple list of pixels in raster order.

If you can explain it better with pictures, I don't mind.

[FireSBurnsmuP]

The reason I'm using these formats is that they're a good place to start off. I'll eventually make this program able to handle many types of pictures, but I've got to start somewhere ^_^

Alright, time for some ascii-art goodness.
I'll start with a small binary picture. [ ][X] for off/on

10x5
0 1 2 3 4 5 6 7 8 9
0[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
1[ ][X][ ][ ][ ][ ][X][X][X][ ]
2[ ][X][X][ ][ ][ ][X][ ][X][ ]
3[ ][X][X][X][ ][ ][X][X][X][ ]
4[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]

Alright. there's the picture. Now I'm looking for the best (efficiency) algorithm in c++ to test if the pixels (1,1) and (7,1) are connected.

As of now, the program attempts to go N, if that doesn't work it goes E, if that doesn't work it goes S, and if that doesn't work it goes west. It does this until it can no longer go anywhere.
I would like it to go in an order that changes depending on what direction the destination is from the starting point, but that ends up being inefficient in other ways. any ideas are good, thanks.

Or, should I start by checking how many borders I cross between the start and end, going directly at each other? in this case, I would pass 2 boundaries, meaning either the region wraps like a U to the destination or there are two regions involved.
What do you think?

[edit] apparently it doesn't like my ascii-art. You get the idea, though. it's a triangle seperated from a square with a hole in it.

[Duoas]

Ah, I get it. Google "flood fill algorithms".

To get ASCII art to look right just put it in [[I][/I]code[I][/I]] tags:

10x5
  0  1  2  3  4  5  6  7  8  9
0[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
1[ ][X][ ][ ][ ][ ][X][X][X][ ]
2[ ][X][X][ ][ ][ ][X][ ][X][ ]
3[ ][X][X][X][ ][ ][X][X][X][ ]
4[ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]

Good luck.