Sign in to follow this  

Algorithm question: Size to fit.

This topic is 4688 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I have a problem which I am pondering how to solve, which may be more difficult than I imagined. It does seem to be something generic enough though [ala travelling salesman] that it might have a proper name. Anyways, the problem is this: I have a list of objects, each defined as a rectangle. I have another rectangle, in which all of these objects must fit. The objects may wrap around [like text], but may not change order. Their sizes may change, but all of the objects' sizes must remain in proportion. So, is there any better algorithm than 'start at tiny scale, and increase scale until not all objects fit' or something like binary partition of the scaling. [ie: can this be calculated explicitly rather than progressively better guesswork?]

Share this post


Link to post
Share on other sites
[edit] God I type so slow...[/edit]
That's a tough one! I do not know what binary partition of the scaling is exactly, but it may be what I am going to describe. If you use some 'binary search' technique, let's say if you start out with one scale, you first test to see if the objects can fit. If not, you know a max and you divide by two and do the same thing over. If they all do fit, I think you know one min, so you could multiple by two instead and test. That is the best method I could think of really. It would be more efficient than progressively guessing.

Also there could be some obscure math formula that might exist to help you acheive this. I would suggest just mass google'ing for geometric formulas. Hope this helps a bit.

- Drew

Share this post


Link to post
Share on other sites
Eh, the text analogy is probably the best way to describe it, even though the situation is not text.

Say I give you the phrase "how now brown cow" and a box. How would you find the maximum font size you can have without having the box clip any of the text?

Share this post


Link to post
Share on other sites
Quote:
Original post by smart_idiot
You can't just set your rectange to the size of the first, then go through the rest and extend if they're outside of it?


The box is fixed, and cannot be changed.

Share this post


Link to post
Share on other sites
box_width=text_width/text_height*box_height

At least I think. You can make the text any size for that calculation, all that's important is the ration between it's width and it's height.

If that makes the text too long, then you can swap the width and height around to figure out how high to make the text instead so it'll fit.

Or do I have that backwards? I've confused myself.

Share this post


Link to post
Share on other sites
Quote:
Original post by Drew_Benton
[edit] God I type so slow...[/edit]
That's a tough one! I do not know what binary partition of the scaling is exactly, but it may be what I am going to describe. If you use some 'binary search' technique, let's say if you start out with one scale, you first test to see if the objects can fit. If not, you know a max and you divide by two and do the same thing over. If they all do fit, I think you know one min, so you could multiple by two instead and test. That is the best method I could think of really. It would be more efficient than progressively guessing.

Also there could be some obscure math formula that might exist to help you acheive this. I would suggest just mass google'ing for geometric formulas. Hope this helps a bit.

- Drew


Ah, yes, that is what I meant.

The generic psuedocode solution I did:


min_factor=0;
max_factor;
cur_factor;

max_factor=(area_of_bounds / sum_area_of_objects);
while ( max_factor - min_factor > some_value && iterations < some_other_value ){
cur_factor=(max_factor+min_factor)/2;
scale_objects(cur_factor);
if (objects_fit(box)){
// then the factor is good, set it as min.
min_factor=cur_factor;
}else{
// too big.
max_factor=cur_factor;
}
iterations++;
}
return(min_factor);

Share this post


Link to post
Share on other sites
Quote:
Original post by Telastyn
Ah, yes, that is what I meant.
The generic psuedocode solution I did:


Awesome! Now, here's another idea of that implementation. Instead of working with areas and such, how about working with the verticies of the rectangles? You can then calculate whether the verticies fall outside of the bounds of the box. I think, but am not sure, this will be faster and more optimizable then using areas, since area is determined by the verticies, you are just going one hierarchy above it.

You could possible make something so you know you only need to test certain rectangles - notely, those around the edges. This can save you more processing time as well.

- Drew

Share this post


Link to post
Share on other sites
I'm going to try this again.

1) There's a bunch of boxes.
2) These boxes need to be moved and scaled to fit inside another box.

Step one: Create a box to contain all the smaller boxes like I said before.

Step two: Translate all the boxes so that the top/left point of the big box and the bountry box match, and treat this point as the origin.

Step three: Scale the boxes by the ratio between the big box's height and the bountry box's height. If that makes it too wide, then instead do it for the width.

Step four: Profit?

And if that's still not what you mean, ignore me. I'm leaving.

Share this post


Link to post
Share on other sites
Quote:
Original post by smart_idiot
I'm going to try this again.

1) There's a bunch of boxes.
2) These boxes need to be moved and scaled to fit inside another box.

Step one: Create a box to contain all the smaller boxes like I said before.

Step two: Translate all the boxes so that the top/left point of the big box and the bountry box match, and treat this point as the origin.

Step three: Scale the boxes by the ratio between the big box's height and the bountry box's height. If that makes it too wide, then instead do it for the width.

Step four: Profit?

And if that's still not what you mean, ignore me. I'm leaving.


I think that's a great idea and much easier than what I suggested. However, I, at least, did not interpret your posts to that idea[wink].

Share this post


Link to post
Share on other sites
The short answer is that I am, sort of.

The long answer is that it is difficult in my design to do that.

All of my render objects derive from a base render object [basero]. There's essentially 2 paths that they can take. 1 path is rendered with vertices/textures, the other path is defined with a rect, and either renders text in that rect or is a mouse target.

So that my list class can nicely arrange the two different branches, the basero class has virtually inherited things like center(),size(),getrect(),move(),moveto()... so that both branches have a unified interface. If an image [vertex/texture] is non-square, it's getrect() implimentation returns a rect structure which wholy contains the vertices:



+-----------+
| /\ |
| / \ |
| / \ |
| / \ |
| / \|
|/ /|
|\ / |
| \ / |
| \ / |
| \ / |
| \/ |
+-----------+


The original max_factor calculation uses areas, as the "best" factor will be the one where all the objects fit snuggly together and fully within the box [ie, scaled_object_area==box_area]

The actual test to see if the objects fit uses the above functions to move the rectanges next to one another progressively, wrapping as needed [like spelling out non-uniformly sized text]. Since I can't really guess where there wrapping will take place, I can't guarantee which objects are near the edges...

Share this post


Link to post
Share on other sites

This topic is 4688 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this