In the part two of this saga, we’ve discovered that not using brute force is not gonna be an option. After our first attempt at brute force failed miserably, we’ll have to find another way.

Me orc, me smash: Brute force revisited

Upon review, it turns out that our first solution was actually kinda close to working. Our algorithm kinda looked like this:

1. Find the center of the ellipse
2. Find aspect ratio of the text
3. Assume that the aspect ratio we found is the same as the aspect ratio of our ellipse
4. Squash text into the square and draw a circle around it
5. Calculate the radius of the circle using maths
6. Unsquash the circle, get ellipse (or two radii that define it)

The obvious problems with this approach were:

• assumption under point #3 is incorrect
• this means the radius we calculated was also wrong, and often too tight

We can work around that. We only really need to add very little on top of what we already have:

4. …
5. Calculate radius of the circle using maths
6. **Increase that radius by some factor in order to give us some breathing room**
7. Unsquash the circle, get ellipse (or two radii that define it)
8. **Try to make ellipse smaller, one small step at a time**
9. Repeat #8 a few times, use the best result you get

Steps 8/9 can be done using a kind of binary search, and it goes roughly like this:

1. Calculate whether all points are in the ellipse for given radii.
2. If all points are inside the ellipse, decrease radii for half of a step
3. If any of the points are outside the ellipse, increase radii for half of a step
4. Decrease step by half
5. If step is sufficiently small, you can stop
6. If step isn’t sufficiently small, go back to #1

In our case, we have two ‘steps’ (each for one of the radii). Before starting our algorith, we determine two values for each of the radii:

• “Radius can’t be bigger than this” number (e.g. width of a given line of text)
• “Radius can’t be smaller than this” number (e.g. half of the width of a given line of text)

Step is the difference between the two (different for each radius). We use the bigger of the two numbers as our radius.

This works great, but we can improve it even further. Inside every step, we can try decreasing size of one radius while keeping the other radius the same. This can help us find smaller, better-fitting ellipses at the expense of some extra calculations (to the tune of O(n²)).

Trying it out

Now that we wrote the code, it’s time to try it out. Results ended up being slightly disappointing:

What is worse: there doesn’t seem to be neither reason nor rhyme to why things don’t work. Our brute force approach was used at least five times and has two failures (where bubble is way too small). Multiline texts — the ones that very probably don’t use the bruteforce approach at all — are often off-center and sometimes even too small (all off-center bubbles are too small, so text doesn’t fit in the ellipse):

What gives?

Upon closer examination, it turns out that some ellipses that should be drawn with brute force method weren’t drawn by brute-force method. Secondly, despite determining ellipse’s radius by brute force, we still always use our matrix to determine one or both center coordinates. Our ‘high maths’ approach is giving us slightly suspect — and possibly even wrong — results.

The one thing to consider when writing code is that computers are generally fairly terrible with very tiny (and very big) numbers. The tinier your number (we’re talking anything past fifth decimal), the less “accurate” it is. The values the matrix calculation spat out contained some very tiny numbers. When those numbers were used to perform further calculations, the errors grew and we got garbage results.

Let’s forget the ‘high maths’ approach for a while and try to brute force everything.

Giving brute force another try

Step 1: determining the center of the ellipse

This one is going to be easy. We still only work with 4 points at the time. To get the ‘center point’, we find the average of the four coordinates. Then, we try to find the intersection between the lines connecting the points at the opposite sides of the quadrangle the four points form. If the point of intersection is mirrored over the ‘center point,’ it gives us the center of our ellipse.

Step 2: apply smash, remove smart

We feed the center of the ellipse we got from step 1 into the brute force algorithm we discussed earlier, run some test and …

Good news is: brute force does find better results than attempt at using high maths. No bubble is drawn off-center, all bubbles are correctly sized. The reason for the crash is a weird point selection: one of the diagonals (in at least one of the 4-point subsets of the last bubble) is vertical. In order to calculate the center of our to-be-ellipse, we need to know the slope of thes line between the opposing sides. There’s a bit of a problem though: if you’re trying to calculate the slope of a vertical line in a coordinate system, you’re going to faceplant into a division by zero.

Computers don’t like dividng by zero.

We can quickly see another thing: if we try to determine the center for our ellipse using these four points, we’ll just get less-than-optimal solution. That means we can skip it — all it would do is waste our time.

Let’s see if that fixed our probem:

And all is right. As far as performance goes, “stopwatch test” says brute-force approach isn’t really that much slower than the “proper”, “high maths” approach.

This leads us to the conclusion:

Lots of people love the “work smart, not hard” approach to things. Sure, using a little bit of brainpower to avoid using a lot of force is nice. But let’s not forget that sometimes, the opposite applies: a little bit of brute force can save us from using lots of brainpower.

Moral of the story: don’t overthink your programs, I guess? Sometimes, simple is better and ‘approximate’ is good enough.