Hi,
First of all, I should point out that this would be a pre-processing step, so it isn't critical speed wise. I just don't like slowness in general.
What is important is that the rectangles generated are as tight fitting as possible, as their content is used for a realtime application.
FluffyMcDeath wrote:
Thinks a bit more...
Are these areas allowed to be "hollow" e.i. can they enclose a set of out of range pixels?
It's not that complex. Consider the letter C - the algorithm would return the smallest rectangle that the complete letter fits into. A letter O of the same basic size would return the same rectangle.
The shapes are allowed to be hollow, just like the letter O in the above example. As long as the outer boundary is enclosed in the box, that is all that matters.
And how do you start looking? Do you start in the shape, as if you were doing a paint fill, or are you just looking for pixels that satisfy the criteria within the entire pixmap?
(So, could there be more than one match.)
What the existing algorithm does is to first scan down vertically a line at a time. It starts out witth the assumption that we haven't hit an area.
The moment we find a pixel along the current scanline that matches our criteria, the y coord is noted as a 'starting Y ordinate' (yMin), and the method of scanning now changes to look for the next scanline line that doesn't contain a pixel matching our requirements. When one of those is found, the y value is noted as a 'terminating Y ordinate' (yMax).
If we get to the end of the bitmap, it is always terminated as a yMax if we happen to be in an area of "the good stuff".
And so the scan proeeds. At the end, we have a set of yMin/yMax pairs.
We then do a horizontal scan in the same way to locate the corresponding xMin / xMax pairs.
We can correlate these to get a list of rectangles. It isn't perfect in that suppose we had two circles - one large and one small, with their y centres the same but at non-overlapping values of X.
The bounding rectangle for the larger one will be perfect, but the bounding rectangle for the smaller one will be as tall as the larger one. However, this is really a trifling inconvenience for what I have in mind.
And, if you scan one way, haven't you already scanned the other? Really?
Like if you walk the Ys and you know the x where you hit the good stuff and the x where you left.
This is what I was thinking, in a way.
And you could get faster if you took those start and ends and went straight down from there to the next Y
and if you are on the right side (for e.g.) and you go down and your pixel is in range, then go right further to find the edge, else go left.
For the other side, vice versa. If your left and right get to be the same, you've closed out the bottom.
Then from your starting Y go back up the same way to close your top.
Hmm. So you are saying we could basically floodfill the areas when we find them and keep track of the xMin/xMax and yMin/yMax during the fill. That might be a good solution.
