When we left off last time, I still thought this wasn’t going to be that bad. I was wrong.
Matrix: reloaded
So we’re back to square one and I’m looking at the first answer about my problem that I’ve found over at math stackexchange. When I first saw it, I thought I haven’t watched enough Rick&Morty to understand it, but after playing around with it for way longer than I should have I started figuring shit out.
If you plop 4 points into the following equation:
And solve the system of those four equations, you should notice that the variables ‘a’, ‘b’, ‘c’ and ‘d’ are all some fraction or multiplier of ‘e’. Even without knowing the value ‘e’, we can calculate the center of the ellipsis. If we want radius, we need to know ‘e’. Assuming ‘e’ is -1 seems to do the job the way we wanted, though.
Since our convex hull often contains more than 4 points, we try to calculate the ellipse for every combination of 4 points (out of all points on the hull). Note that because we’re lazy, we don’t calculate the hull. We just take upper two corners from each row in the upper half of text and the bottom two corners from each row in the bottom half of text. If the text has odd number of rows, we include all four corners in the convex hull.
⬤ — point not on the ‘convex hull’, therefore we ignore it.
⬤⬤⬤ — Points we assume are on the convex hull. No biggie if they aren’t as we throw out garbage results later
We calculate radii for each combination of 4 points that we have. We check if the new ellipse contains all the points of the hull (either inside or on the edge). We reject the result if it doesn’t. If we don’t reject the result, we compare it with the last result we didn’t reject. If the ellipse is bigger than the last result, we reject it. If not, this is our new result. Repeat until you’ve ran out of combinations.
Sooner or later, though, we run into a problem. What if ‘c’ and ‘d’ are free variables instead of ‘e’? This happens if any of the four points are horizontally or vertically symmetrical relatively to the center of the ellipse. For example, if you plug points 0,0; 4,0; 0,2; 4,2 into the equation, you’ll find that ‘a’ is some fraction of ‘c’ and ‘b’ is some fraction of ‘d’. You can still calculate center from that, but you can’t get the radii. Even worse is the case of 0,2; 2,0; 4,0; 6,2: symmetry across only one axis means you can only get one coordinate of the center because there’s infinitely many solutions.
Since we’re after only one specific solution, for us ‘infinitely many solutions’ equals ‘no solution.
Forsaken cheats
In the second example from above, we could do some additional maths in order to find the center. We’re only interested in the smallest possible ellipse, so we could calculate some limits in order to get the other center coordinate. But word on the streets is that cheating is easier and could get us results that are close enough to what we want.
Turns out breaking symmetry isn’t too hard — we just need to ensure that points in the left and right halves don’t share the same ‘y’ coordinate, and points in top and bottom halves don’t share the same ‘x’ coordinate.
The first bit of this task can be easily achieved: since every row has two points with same ‘y’ coordinate (and since ‘y’ coordinate can’t repeat across multiple rows), we just need to shift one point a bit up and the other a bit down (or keep it at the same place).
Shifting ‘x’ coordinates is a bit more problematic: two different rows can absolutely contain same ‘x’ coordinate — and what is worse, if we shift the ‘x’ coordinate in any way, we may create the situation we’re trying to avoid. However, we know the following things:
- point coordinates are whole numbers only (We get points by reading pixels, and there’s no such thing as ‘half a pixel’)
- only points in the opposite rows are required to have different x and y coordinates
⬤ — point not on the ‘convex hull’, therefore we ignore it.
⬤⬤⬤ — Points of the same color aren’t allowed to share any coordinate.
If two neighbouring rows (e.g. top two rows in text with more than 3 rows) have points that share the same ‘x’ coordinate, it doesn’t really matter because ellipse containing those points would be rejected for being too small anyway.
This allows us to easily apply required offsets:
* upper left: x -= 0.5, y -= 0.5
* upper right: x -= 0.5
* bottom-left: y += 0.5
So I thought I could do it by shifting points a little outward. Turns out that two-line and one-line rows disagree. At the end of the day, “losing” half pixel of space won’t really be noticed when bubble is more than hundred pixels across most of the time — and when it’s not, the radius is still in high double digits. So let’s change that a bit:
- upper left: x -= 0.5, y -= 0.5
- upper right: x -= 0.5
- bottom-left: y += 0.5
Not quite what we want, but better than what we had before.
Let’s try that out a bit more:
Oopsie whoopsie. Fucky wucky.
Turns out I spoke too soon.
The Right Way™
Sometimes, we don’t have enough data to determine where the center is. Sometimes, we will only get enough data to determine one of the center coordinates. For example, if you only have four points to go off, and if said points would form a symmetrical (acute) trapezoid they were to be connected with lines — and since our text is centrally aligned, that happens almost every time we want to draw a bubble around two lines of text — you can still determine horizontal center.
Turns out this comes out handy: we can determine one of the coordinates using the kind of “cheating” approach we used before, but with some twists:
- We split points in two groups: those to the left and those to the right of the horizontal center (top and bottom if we have the vertical center of the ellipse)
- Find the vertical center of the text (the spot halfway through the topmost and lowermost text edge)
- Find the longest diagonal (upper left to lower left or lower left to upper right)
- Find where the diagonal crosses from one half to the other, and flip that point over the vertical center of the text
The last step is important because longer lines will move the center of the ellipse away from center of text, towards themselves — but the point where the diagonal intersects the horizontal center is going to be offset in the opposite direction.
Once we have both coordinates of the center, we still have some leftover data from the matrix that we can use to determine both radii.
However, this approach doesn’t cover all the cases (it fails at least one), and the ‘offset corners by half a pixel’ way of dealing with things doesn’t seem to harm it, so we’ll just keep both in for the time being.
All in all, we’re progressing somewhat nicely. There’s some work to be done when determining the anti-jag parameter of the rectangular selection (but that — as well as padding — will be user-provided arguments/options). The only thing we have to deal with now are the bubbles with one or two lines, where our current tactics for determining the bubble size fails.
Turns out that — spoiler alert — the brute force approach is the only approach that will consistently work. Maybe it should be revisited.