I'm trying to scan a constant size image and locate the drawn rectangles in it. The rectangles can come in any size, but only red colored.
This is not where the problem starts.
I'm gonna use an already written function, and I will use it as pseudo code calls later on my code logic.
Rectangle Locate(Rectangle scanArea); // scans for a rectangle in a given scan area.
if no rectagle is found,returns null.
My logic was like this:
Find a first initial red rectangle using the Locate() function with the full image size as an argument.
Now, divide the rest areas, and keep scanning recursively.
The main point in this algorithm's logic is that you never check a checked already area, and you don't have to use any condition because always the scanArea parameter is a new area which you haven't scanned before (and that's thanks to the division technique).
The division process is done like this: right area of the current found rectangle, the bottom area, and the left area.
Here's an image which illustrates that process.
(The white dotted rectangles and the yellow arrows are not part of the image, I've added them only for the illustration.)
As you seen, once a red rectangle found, I keep scanning the right of it, bottom and left. Recursively.
So here's the code for that method:
List<Rectangle> difList=new List<Rectangle>();
private void LocateDifferences(Rectangle scanArea)
{
Rectangle foundRect = Locate(scanArea);
if (foundRect == null)
return; // stop the recursion.
Rectangle rightArea = new Rectangle(foundRect.X + foundRect.Width, foundRect.Y, (scanArea.X + scanArea.Width) - (foundRect.X + foundRect.Width), (scanArea.Y + scanArea.Height) - (foundRect.Y + foundRect.Height)); // define right area.
Rectangle bottomArea = new Rectangle(foundRect.X, foundRect.Y + foundRect.Height, foundRect.Width, (scanArea.Y + scanArea.Height) - (foundRect.Y + foundRect.Height)); // define bottom area.
Rectangle leftArea = new Rectangle(scanArea.X, foundRect.Y, (foundRect.X - scanArea.X), (scanArea.Y + scanArea.Height) - (foundRect.Y + foundRect.Height)); // define left area.
difList.Add(rectFound);
LocateDifferences(rightArea);
LocateDifferences(bottomArea);
LocateDifferences(leftArea);
}
So far everything works alright, it does find every red rectangle. But sometimes, the rectangles saved as few rectangles. For a reason that obvious for me: overlapping rectangles case.
A problematic case for example:
Now, in this case, the program finds the first red region as planned, but then, since the right area starts only in the middle of the full second region, it does not scan from the beginning of the second red rectangle!
In a similar way, I can divide the areas so the bottom area stretches from the start of scanArea to the end, which would be like this:
But now we would have a problem when scanning overlapping rectangles on the right and on the left of the foundRect rectangle, for example, in this kind of case:
I need to get each rectangle in one piece only.
I would like to get any help or suggestion combined with my code logic - because it works great but just needs a little one or two additional conditions in the recursion method I think. I'm not sure what to do and I would really appreciate any help.
If something isn't clear enough, just tell and I'll explain it as best as I can! Thanks!
Of course, this is not the real problem I'm facing against, it is just a little demonstration which could help me solve the real problem that I'm working on (which is a real-time internet project).
Locatefunction works: finding the first(most top-left) red pixel, then it keeps scanning to the right,and then when it finds no more red pixels, it start scanning the height ,keep moving down-easy and simple. It works very fast due to the native methods (such asmemcmp()) used there. The scan function is limited to the scan area parameter. if you have any other suggestion... or if you want to see the full function feel free to ask! I just don't think the bottleneck is there, so i haven't posted it – Slashy