Fast algorithm for finding an optimal font size
| Affects | Status | Importance | Assigned to | Milestone | |
|---|---|---|---|---|---|
| Max TTS |
Fix Committed
|
Undecided
|
Unassigned | ||
| Ubuntu Algorithms Headquarter |
Fix Committed
|
Medium
|
Marek Bardoński | ||
Bug Description
Okay, since I read about Ubuntu Algorithms, I thought I might give it a try.
My problem is probably trivial for someone who studied computer science, but I didn’t. So I could need some assistance with this.
My application MaxTTS has a feature to write text to a canvas (Gtk.DrawingArea). The font size should be as large as possible for the given text, so that the canvas is always optimally filled with text. For long texts, the font size has to be smaller than for short texts, accordingly.
Currently, I am using a very simple linear algorithm that increases/decreases the font size by one until the resulting text fills the canvas. This scales very badly, since it takes much more time if the difference between start font size and the optimal font size is large. This is not really a huge issue, since the calculation is still sufficiently fast, but a) there still is a noticeable lag that I’d like to get rid of, and b) I’d like to learn about more efficient ways to solve such problems.
You can see my current implementation at http://
Any advice appreciated!
| Changed in algorithms-headquarter: | |
| assignee: | nobody → Marek Bardoński (bdfhjk) |
| importance: | Undecided → Medium |
| status: | New → Confirmed |
| Marek Bardoński (bdfhjk) wrote | #1 |
| Frederik Elwert (frederik-elwert) wrote | #2 |
| Changed in algorithms-headquarter: | |
| status: | Confirmed → Fix Committed |
| Changed in max-tts: | |
| status: | New → Fix Committed |
Hi Frederik!
Thanks for posting first, real bug for UAT.
I found two answers:
1. Fast, easy to implement
You can use binary search algorithm[1].
It will reduce number of comparing in worst case from 80 (96-16) to log2 80 = 7, so program in theory can be 10x faster, and changes should be unnoticeable.
2. Very fast, average level of difficulty in implementation
You can use fixed size fonts, calc number of chars and places, where are new line characters, and then use binary search to find optimal font width, in each try calculating if all chars fit in their window. When optimal value will be found, then paint all chars only one time.
I suggest try number 1, if You still have problems try number 2.
If You will have problems with implementing binary search algorithm, please reply, I will help.
Good luck!
[1]http://