[2 days left] What’s wrong with your cloud strategy? Learn why multicloud solutions matter with Nimble Storage.Register Now

x
?
Solved

how does paint do?

Posted on 2003-11-07
9
Medium Priority
?
259 Views
Last Modified: 2010-04-01
Hi,

I want to make a "surface selection" function, which would work exactly as "fill" function of paint, photoshop, etc... So my function look like:

DWORD TWPICTURE::Mark4Linked(const DWORD x,const DWORD y,const TWCOLOR &col,const VALUE &threshold)
{
      DWORD notsim=0,res=0,offs=width*y+x;
      if(workbuf[offs]) return 0;
      static TWCOLOR c1;
      workbuf[offs]=1;
      if((y>0) && (!workbuf[offs-width]))
      {
            GetPixel(offs-width,c1);
            if(col.IsSimilar(c1)>=threshold) res=Mark4Linked(x,y-1,col,threshold);
            else ++notsim;
      }
      if((y<height-1) && (!workbuf[offs+width]))
      {
            GetPixel(offs+width,c1);
            if(col.IsSimilar(c1)>=threshold) res+=Mark4Linked(x,y+1,col,threshold);
            else ++notsim;
      }
      if((x>0) && (!workbuf[offs-1]))
      {
            GetPixel(offs-1,c1);
            if(col.IsSimilar(c1)>=threshold) res+=Mark4Linked(x-1,y,col,threshold);
            else ++notsim;
      }
      if((x<width-1) && (!workbuf[offs+1]))
      {
            GetPixel(offs+1,c1);
            if(col.IsSimilar(c1)>=threshold) res+=Mark4Linked(x+1,y,col,threshold);
            else ++notsim;
      }

      if(notsim) workbuf[offs]=2;
      return res;
}

workbuf is a buffer, same size as the picture, initialized with 0. i want to "mark" the pixels inside the shape with 1, and the boudaries pixels with 2. It works pretty well, but only for small surfaces.
if the surface is too big, i got a stack overflow. Should I increase the size of the stack, or is there another way for my pixels selection?

best regards,

Raph
0
Comment
Question by:ralph78
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 5
  • 4
9 Comments
 
LVL 13

Expert Comment

by:SteH
ID: 9700239
Since you are using recursion the stack can easily be filled. Do you need recursion or could you try a looping approach. Depending on how big the images are allowed to be it might be that the stack can't be big enough.

Idea 1)
Start from the central point and compare in a loop in one direction (up/down or left/right) until you hit the border of the surface. If both ends are known switch direction and start from all points on the line but not the boundary a next scan. After a number of direction changes the shape should be found.

Idea 2)
scan the entire image whether pixels are similar to the one you want. In the next step just find the pixel connected to the central one in the workbuf.
0
 

Author Comment

by:ralph78
ID: 9706595
hummm.... idea 1 is not recursive???
once i know my 1st segment, i have to recurse for each point of this segment and so on for all new segments, isn't it? so my problem is same...
0
 
LVL 13

Expert Comment

by:SteH
ID: 9713422
It can be recursive. But I had in mind to do a number of loops for it. Each loop starts from the result of the preceeding one but is not called from within the first loop.

Xstart = x;
Ystart = y;
GetPixel (y*width+x, c1);
while (col.IsSimilar (c1)) {
     workbuf[y*width+x] = 1;
     ++x;
     GetPixel (y*width+x,c1);
}
// TODO: set last value in workbuf to 2.
x = Xstart; // y remained

GetPixel (y*width+x, c1)
while (col.IsSimilar (c1)) {
    workbuf[ ...];
    --x;
    GetPixel (...)
}
// TODO: set last value in workbuf to 2.

for (firstvalue with 2, lastvalue with 2, ++ind) {
    while () {
        ++y
    }
    while () {
        --y
    }
}  

The next iteration is in the non recursive approach more complex than the last one but feasable. So you are right in the sense that you have to start a test from each point of the first iteration but it doesn't need to be recursion.
0
VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

 

Author Comment

by:ralph78
ID: 9718018
ehhh... yes, i have benn thinking to this solution, unfortunately we won't consider shapes like this:

                       +-----------+    +--+
                       |  x           |     |   |
                       |               |___|   |
                       +--------------------+
 (x is the start point)

nor like this

                        +-----------------+
                        | x    +----+       |
                        |       |___|       |
                        +-----------------+

(sorry for poor drawing)
I partialy solved my problem by increasing the size of my stack, but, particularly if the shape is big, recursion remains a problem.
0
 
LVL 13

Expert Comment

by:SteH
ID: 9720670
The shpaes you've drawn are the difficult ones. If you don't have to consider them, be happy! In that case you can limit the number of loops.

But I still prefer the other solution; compare all pixels whether they are similar. This shifts the problem to find a closed object around your starting point. An approach would be to start from x which you set to 2, all other similar pixels are 1. Now you go up from every pixel with a 2 until either you hit the border or a 0 pixel and set those values to 2. Just go in all directions until the you can't increase a pixel in any direction.
0
 

Author Comment

by:ralph78
ID: 9720899
i meant your solution can't consider the shapes i drawn, but i HAVE to;-)

as for the 2sd solution, it's esactly the same problem, except that you pulled IsSimilar out of the detection function. (but i still do have to recurse!)
0
 
LVL 13

Expert Comment

by:SteH
ID: 9720998
No, the shapes can be found in my approach as well:

before: only start pixel is one:
000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000
000000000000100000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000

first loop: up and down
000000000000000000000000000000000000000000000000000000
000000000000100000000000000000000000000000000000000000
000000000000100000000000000000000000000000000000000000
000000000000100000000000000000000000000000000000000000
000000000000100000000000000000000000000000000000000000
000000000000100000000000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000

second loop: left and right
000000000000000000000000000000000000000000000000000000
000001111111111111111111111111111111110000000000000000
000001111111111111110000000000000000000000000000000000
000001111111111111110000000000000000000000000000000000
000001111111111111110000000000000000000000000000000000
000001111111111111110000000000000000000000000000000000
000000000000000000000000000000000000000000000000000000

third loop: up and down
000000000000000000000000000000000000000000000000000000
000001111111111111111111111111111111110000000000000000
000001111111111111110000000000111111110000000000000000
000001111111111111110000000000011111110000000000000000
000001111111111111110000000000001111110000000000000000
000001111111111111110000000000000111110000000000000000
000000000000000000000000000000000000000000000000000000

forth loop: left and right
000000000000000000000000000000000000000000000000000000
000001111111111111111111111111111111110000000000000000
000001111111111111110000000000111111111000000000000000
000001111111111111110000000000011111111100000000000000
000001111111111111110000000000001111111110000000000000
000001111111111111110000000000000111111111000000000000
000000000000000000000000000000000000000000000000000000

This is a way for the first of your examples. You can't stop after the second loop for those, correct but you can stop when you can't add for two consecutive loops. It gets a bit more complicated if you consider spapes like the following as a single object but still possible. But I think you won't find those with your recursion neither.

00000000000000
00111000000000
00000111100000
00000000000000

0
 

Author Comment

by:ralph78
ID: 9729872
ok, i got your point, but you still need recursion, else i don't understand how u can determine how many loop you need, nor the stop condition.

0
 
LVL 13

Accepted Solution

by:
SteH earned 200 total points
ID: 9730140
To determine when to stop one idea would be:
Write a function for each direction which does a loop into that direction. This function returns the number of new pixels found.

int count = 0;
do {
     count += loop_left ();
     count += loop_down ();
     count += loop_right ();
     count += loop_up ();
} while (count > 0);
// here no new pixels where found.

Looking into the other approach:

for (i=0;i<width;++i) {
    for (j=0;j<height;++j) {
         GetPixel (j*width+i, c1);
         if (col.IsSimilar (c1)) {
             workbuf[j*width+i] = 1;
         }
    }
}

Fills the workbuf with all pixels which are similar to c1.
Now go from start position left until you hit the border. Change the value to 2 and set the dreiction you came from to down. Now look right forward and left with respect to the direction you came from. And change the first encountered 1 to 2 in the workbuf and continue.
Repeat this procedure by going to the right from the starting point. If you find a 2 there you're done. Otherwise you continue on the border as before but starting up. In the case you start down here you need to exchange looking left and right from before.
0

Featured Post

VIDEO: THE CONCERTO CLOUD FOR HEALTHCARE

Modern healthcare requires a modern cloud. View this brief video to understand how the Concerto Cloud for Healthcare can help your organization.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Often, when implementing a feature, you won't know how certain events should be handled at the point where they occur and you'd rather defer to the user of your function or class. For example, a XML parser will extract a tag from the source code, wh…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.
Suggested Courses

656 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question