3

I'm working on a component that needs to draw chart-like structures like this:

enter image description here

One issue I have is when multiple values are too close with each other. Here's an illustration:

enter image description here

The last values for the blue, green, and purple charts are so close that one can barely decipher the 61.0 corresponding to the latest blue value, and there is practically no way to read the green's 48.0.

In terms of the design, I imagine that when the values are close enough, they should push each other, in order to avoid visual collisions. In this example, the blue 61.0 should be displayed 15 – 20 points higher, the purple 50.0 should be slightly raised, and the green 48.0 should be lowered.

Are there common approaches for this sort of problems?

If not, what would be a good approach?

I could imagine a decent one which would work for a maximum of two values. If they are close enough, one just needs to push them apart proportionally.

When it comes to three values or more, things start to get complicated. I would likely try to do it in iterations: check how raising or lowering each value by one point affects the others, and do it with all the values until I get somewhere. But, obviously, this approach would be terribly slow.

2
  • 4
  • Not really an answer to your question but often these kinds of components have a select/hover capability which shows you the exact value in a popup as you move a pointer along the line. Also simply making the text smaller (not sure why the rightmost values are so large,) and maybe make them larger on hover.
    – JimmyJames
    Oct 10, 2023 at 14:56

2 Answers 2

4

I would likely try to do it in iterations: check how raising or lowering each value by one point affects the others, and do it with all the values until I get somewhere. But, obviously, this approach would be terribly slow.

You are on the right track, but your assumption that this kind of approach will be terribly slow is only true when trying this in a unsystematic way. Fortunately, iterative approaches for such kind of optimization problems are well-studied, and there are lots of algorithms among one can pick, hopefully one which is fast enough for your purpose.

I would recommend to start phrasing this as a continuous optimization problem (assuming x and y coordinates of the text positions are non-discrete real values), though it is also possible to use discrete optimization techniques by restricting the problem space to integer coordinates. I will also describe a general approach here using y and y coordinates, and overlaps between arbitrary pairs of text labels. In case you want optimize only y positions and ignore overlaps between different columns, just set the x variables in the following description to fixed values, and optimize column-wise.

So let us start with the objective function. For each of the texts T_1, ..., T_n there is a desired position (xd_1, yd_1), ..., (xd_n, yd_n). Your goals are

  1. each text should be placed as nearby to its desired position as possible

  2. the texts (or their bounding boxes) shall not overlap, or at least the amount of overlapping should be minimized

Hence, the objective function f(x_1,y_1,...,x_n,y_n) should have two summands f1and f2:

  • f1 should be the sum of the distance-squares from the desired positions

    f1(x_1,y_1,...,x_n,y_n) = sum((x_i - xd_i)^2 + (y_i - yd_i)^2)  with i=1...n
    
  • f2 should be the the sum of the pairwise intersectional areas of the bounding box rectangles - or even better, their squares, to make the function more smooth, which has some advantages for the algorithmic approaches:

    f2(x_1,y_1,...,x_n,y_n) = sum((A_i_j)^2) with 1<= i < j<=n 
                              and A_i_j = "common area of the boxes around T_i and T_j"
    

    f2 can be calculated efficiently by sorting the points in x direction first and do the area calculation only for boxes where the x coordinates are in a sufficiently small interval to make overlaps possible (this helps to avoid quadratic run-time complexity).

To favor no overlapping against placing the texts at their desired position, give f2 a much higher weight W than f1:

  f= f1 + W * f2

(for example, you can try W = n * 10000, I guess you have to experiment a bit here).

I guess it is clear how to take more criteria into account here in case one has to, by adding more summands.

Now, we have an objective function for an unconstrained, non-linear optimization problem, and the goal is to find a global minimum by some iterative optimization algorithm. Such iterative methods require a good starting value, for which you may use the desired positions (xd_i,yd_i), or some heuristically choosen, non-overlapping positions (as scetched in @DavidT's answer).

For the kind of function I scetched above, it should be possible to calculate the partial derivations, hence the approach I would recommend to start with is the Gradient descent method. A more sophisticated method is the BFGS algorithm. It will require higher effort to implement, but will be usually a lot more efficient. Both algorithms are too complex to be explained here in full, but their main idea is to

  • calculate the "change rate" of f at the current position when only one coordinate changes (a.k.a partial derivations). BFGS takes also second derivations - or approximations for them - into account.

  • build a search direction from those partial derivations

  • minimize f along the search direction, so finding a new search position

  • repeat the former steps until the algo reaches a local minimum.

This outline is not just suitable for the kind of graphs you asked specificially, but for any kind of diagram where one wants to place texts in a 2D plane nearby to desired positions in a mostly non-overlapping fashion.

Hope this was clear enough, if not, feel free to ask.

2

Assuming you only have a problem with vertical squishing (not horizontal). I would be tempted to try a very simply approach and see what it looks like:

  • Given a particular horizontal column, sort all the label you need to place lowest value first.
  • Place the first label immediately above the line it corresponds to.
  • Place each of the remaining labels at position max(top of previous label, immediately above the line it corresponds to). **

** - Assuming Y axis increases as it goes up.

The goals of this are:

  • Ensure the label doesn't obscure its own line.
  • The order of the labels is the same as the order of the lines for a given column.
  • Keep labels from overlapping.
  • Attempt to keep the labels close to the corresponding lines.
  • Don't confuse the user by sliding labels horizontally.

Placing all the labels behind the graph lines may also help the user to visualize the graph - at the expense of making the labels harder to read.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.