Jump to content
  • Advertisement
Sign in to follow this  
Telastyn

Algorithm question: Size to fit.

This topic is 4880 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
Advertisement
[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
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!