# Algorithm question: Size to fit.

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

## 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 on other sites
I'm not understanding your problem at all :/
I can't see what exactly you are trying to find.
Maybe a illustration of the problem would help?

##### Share on other sites
It sounds to me like pack-rat theory. [wink]

##### Share on other sites
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?

##### Share on other sites
 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 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 on other sites
Quote:
 Original post by smart_idiotYou 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 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 on other sites
Quote:
 Original post by Drew_Benton 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 on other sites
Quote:
 Original post by TelastynAh, 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

1. 1
2. 2
Rutin
21
3. 3
4. 4
frob
14
5. 5

• 12
• 9
• 9
• 17
• 20
• ### Forum Statistics

• Total Topics
632600
• Total Posts
3007340

×