Re: Q: Any ideas for this algorithm???
On Sep 29, 10:49 am, John Harrison <john_androni...@hotmail.com>
wrote:
Somebody wrote:
I have the following:
struct A
{
int left;
int top;
int right;
int bottom;
};
Thats a rectangle. I have an array of rectangles... say
ARR[nCount]... Now, I've got these elements laid out in rows
(not important how),
I would say that is important. It seems like the essense of the problem
to me.
Me too.
[...]
So it seems you have all the rects in order, which each rect
on a row having the same value for top, is that right?
I'd probably tend to use a two dimentional structure. If I
couldn't change the basic structure, something like the
following should be able to handle all cases (supposing that
"top" can be used to identify the row).
std::map< int, int > maxPerRow ;
for ( A* curr = begin ; curr != end ; ++ curr ) {
int& maxBottom = maxPerRow[ curr->top ] ;
maxBottom = std::max( maxBottom, curr->bottom ) ;
}
for ( A* curr = begin ; curr != end ; ++ curr ) {
curr->bottom = maxBottom[ curr->top ] ;
}
Obviously, if you can manage order, or use a two dimensional
structure, the code can be made more efficient. But anyway you
do it, you'll need two passes over each row.
--
James Kanze (GABI Software) email:james.kanze@gmail.com
Conseils en informatique orient=E9e objet/
Beratung in objektorientierter Datenverarbeitung
9 place S=E9mard, 78210 St.-Cyr-l'=C9cole, France, +33 (0)1 30 23 00 34