need help with CRect operator less than

[SlimGradey]

hello,
i have a struct with x,y width,height, and page number in a vector, i'm trying to make a sort by page or by width and height of the rects...
sorting by page seems to work fine... but i cant figure out the right combo of checks to make the rects go in order... right now its saying 2x8 is smaller than 4x4... i need it to say like, 1x1,2x2,3x2,2x4,4x4,2x8,4x8,8x8...
hopefully you know what i saying...
thx so much...

[Philip Nicoletti]

Are you trying to sort by area ?

Compare width * height

Edit : I guess I still don't understand what you are looking for.

If you are comparing areas, then 2x8 and 4x4 would be equal ...
so they could be in any order.

[SlimGradey]

here's some code i was trying out....

BOOL operator < (const CRect &lhs, const CRect &rhs)
{
	BOOL val = FALSE;

	if(lhs.Width() < rhs.Width() && lhs.Height() < rhs.Height())
	{
			val = TRUE;
	}
	else if(lhs.Width() < rhs.Width() && lhs.Height() == rhs.Height())
	{
			val = TRUE;
	}
	else if(lhs.Width() == rhs.Width() && lhs.Height() < rhs.Height())
	{
			val = TRUE;
	}
	else if(lhs.Width() < rhs.Height() && lhs.Height() < rhs.Width())
	{
			val = TRUE;
	}
	else if(lhs.Width() > rhs.Height() || lhs.Width() > rhs.Width())
	{
			val = FALSE;
	}
	else {
			val = FALSE;
	}

	return val;
};

BOOL operator < (const CRect &lhs, const CRect &rhs)
{
	return (BOOL)((lhs.Width() < rhs.Width()) && (lhs.Height() < rhs.Height()));
}

BOOL operator < (const CRect &lhs, const CRect &rhs)
{
	BOOL val = FALSE;

		if(lhs.Width() < rhs.Width())
		{
			if(lhs.Height() < rhs.Height())
			{
				val = TRUE;
			}
			else
			{
				val = FALSE;
			}
		}
		else if(lhs.Height() < rhs.Height())
		{
			if(lhs.Width() < rhs.Width())
			{
				val = TRUE;
			}
			else
			{
				val = FALSE;
			}
		}
		else
		{
			
			val = FALSE;
		}
	

	return val;
};

struct _Records
{
	int X;
	int Y;
	int Width;
	int Height;
	int Page;


	bool operator < (const _Records &other) const
	{
		CRect lhs(0,0,Width,Height);
		CRect rhs(0,0,other.Width,other.Height);
		return (BOOL)(lhs<rhs);
	}

};

i'm trying to put the smallest rects first... my thinking is like if you have
two rects in real and you line them up and if a part sticks out pass the
edges then its bigger... and if they are equal or one side is less than
should be smaller... but cant figure out how to code it right...
i want the largest side of the rect to pair up with bigger rects...
2x8 should pair up with 8x8.. since w2 is smaller than w8, it should be
first... 2x4 should pair with 4x4... so order would be 2x4,4x4,2x8,8x8
example if you have a 2inch x 8inch , and a 4inch by 4inch piece of paper,
no matter which way you rotate that 4x4 piece cant make it fit inside the
2x8 piece... so 2x8 is bigger than...

confusing stuff hehe...
hope we can figure something out...
thanks...

[Philip Nicoletti]

Ad how would the following two rects be ordered ?

2x8 and 3x5

Neither can fit inside the other.

[SlimGradey]

based on physical looks, 2x8 is the bigger one...
an also 8 is the bigger of the numbers... so needs to
be placed lower... 3x5 would be first..
1x5,2x5,3x5,1x8,2x8... values range from 1x1 to 256x256...

i wonder if figuring out which of the numbers are the highest value
on each and do less than on those... so 2x8 highest is 8, 3x5 highest
is 5.... so return(5 < 8)...

i'm gonna try do a test, maybe that way works or close...

thanks...

[Philip Nicoletti]

By your latest criteria ...

200x200 would come before 1x201

[Philip Nicoletti]

Maybe you want to order by perimeter ?

[SlimGradey]

i'm trying to sort the rects to fill a 256x256 page with all the
largest rects first on the page, then each page will have smaller and
smaller rects...

i dont know much about perimeters, maybe thats what i need...

[SlimGradey]

i tried this and things still seems randomly sorted

BOOL operator < (const CRect &lhs, const CRect &rhs)
{
	int p1 = 2*(lhs.Width() + lhs.Height());
	int p2 = 2*(rhs.Width() + rhs.Height());
	return (p1<p2);
};

[SlimGradey]

i think i might have close to what i looking for now...
things sorted little better... or best i can do...
what i did was make a new struct same as the other but
added a cstring... and do the sorting on that string.. %03dx%03d
i find out which of the width or height has the largest value
and put that number first in the string... then sort them...
then i clear my previous data and apply the new sorted items
to the old vector...

struct rect_dimension
{
	CString str;
	int X;
	int Y;
	int W;
	int H;
	int Page;

	bool operator < (const rect_dimension &rhs)
	{
		return (bool)(str < rhs.str);
	};
};

////////////////////////////////




	vector<rect_dimension>_rd;


	for(int i=0; i<m_records.size(); i++)
	{
		CString str;
		int w = m_records.at(i).Width;
		int h = m_records.at(i).Height;

		if(w>h)
			str.Format("%03dx%03d",w,h);
		else
			str.Format("%03dx%03d",h,w);
		
		rect_dimension rd;
		rd.str	= str;
		rd.X	= m_records.at(i).X;
		rd.Y	= m_records.at(i).Y;
		rd.W	= m_records.at(i).Width;
		rd.H	= m_records.at(i).Height;
		rd.Page    = m_records.at(i).Page;

		_rd.push_back(rd);
	}

	sort(_rd.rbegin(),_rd.rend());

	m_records.clear();

	for(int b=0; b<_rd.size(); b++)
	{
		_Records t;
		t.X          = _rd.at(b).X;
		t.Y          = _rd.at(b).Y;
		t.Width  = _rd.at(b).W;
		t.Height = _rd.at(b).H;
		t.Page   = _rd.at(b).Page;

		m_records.push_back(t);

	}

maybe thats it... let me know of any other ideas...
thx so much...

[Philip Nicoletti]

Just to be clear ...

As I mentioned in a previous post on that method ...

you would consider a 200x200 CRect to be smaller than a 1x201 CRect ?

If that is what you want .. fine. But it does not seem natural to me.

[SlimGradey]

right... seems to be what i need... i guess...
these rects represents textures, and i'm butting them up against each
other on a 256x256 page... a rect of 1x201 would have 1 pixel out passed 200x200..
i want all the peices to fit tightly together... all the largest first...
right now sorting the rects seems ok by looks i think, now i need to work on sorting the textures based on the rect info now, and see how well they get
placed... wish i knew how few other apps optimize their textures...
and place them almost perfect...
right now i'm just able to place them at random, they'll look for the first
empty space big enough for it...
but now i'm trying to add a sort function, incase the user wants
to sort largest or smallest textures first...it will loop through the old
textures and generate and replace the pages with the new layout...
if cant get this right, i'll just let the user only sort the list of textures
by page number hehe...
thx again...

[VladimirF]

It looks like you are making a very light attempt to a heavy optimization.
Try googling for “cutting stock problem algorithm”.