Optimal algorithm for segmenting set of integers into labels for a chart axis?

Question

Say you get values anywhere from 0 to 1,000,000,000, and you want to plot 30 days. So one particular chart may have a set like:

[ 1, 465, 123, 9, ... ]

While another chart can have a set with much larger numbers:

[ 761010, 418781, ... ]

Is there an "optimal algorithm" that can take those values and segment them into "clean" numbers? Sorry for the wording, don't know the right terminology, I will try to explain.

By "optimal algorithm", I mean both in terms of minimum number of computational steps, given that it creates labels (say for the y-axis) that are simplest from a human perspective.

For example, say you always want to divide the y-axis into 5 labels. You could do this:

var max = Math.max.apply(Math, values); // 465 (from the first set of values)
var interval = max / 5;
var labels = [ interval * 0, interval * 1, interval * 2, ... ];

But that creates labels like:

[ 0, 93, 186, ... ]

And that would be complex for humans to understand. What would be better (but still not ideal) is to create labels like:

[ 0, 125, 250, 375, 500 ]

But that's still to specific. Somehow it should figure out that a better segmentation is:

[ 0, 200, 400, 600, 800 ]

That way, it's divided into more intuitive chunks.

Is there a standard way to solve this problem? What algorithm works best?

Answer 1

Some maths

var getLabelWidth = function(sep, max_value){

    var l = (""+max_value).length;

    var av = max_value/sep/Math.pow(10,l-2); // get the length max 2 digit
    /// 15.22

    var width = (Math.ceil(av)*Math.pow(10,l-2)); // do a ceil on the value retrieved 
    // and apply it to the width of max_value.
    // 16 * 10 000    
    return width;
}
console.log(getLabelWidth(2,59));  // 30 :  [0, 30, 60]

console.log(getLabelWidth(2,100)); // 50 :  [0, 50, 100]
console.log(getLabelWidth(2,968)); // 490 : [0, 490, 980]

console.log(getLabelWidth(3,368)); // 130 : [0, 130, 260, 390]
console.log(getLabelWidth(3,859)); // 290 : [0, 290, 580, 870]
console.log(getLabelWidth(3,175)); // 60 :  [0, 60, 120, 180]
console.log(getLabelWidth(3,580)); // 200 : [0, 200, 400, 600]
console.log(getLabelWidth(3,74));  // 25 :  [0, 25, 50, 75]

console.log(getLabelWidth(4,1111)); // 300 :[0, 300, 600, 900, 1200]
console.log(getLabelWidth(4,761010)); // 200 000: [0, 200000, 400000, 600000, 800000]

It could be improved a little bit i guess,

sorry for my bad english .

Answer 2

For reference, here's what I ended up doing.

function computeLabels(count, max) {
  var magnitude = orderOfMagnitude(max);
  var multiplier = magnitude * count;
  // 1
  if (multiplier >= max) return buildLabels(count, multiplier);
  // 2
  multiplier *= 2;
  if (multiplier >= max) return buildLabels(count, multiplier);
  // 5
  multiplier *= 5;
  if (multiplier >= max) return buildLabels(count, multiplier);
  // 10, don't think it will ever get here but just in case.
  multiplier *= 10;
  if (multiplier >= max) return buildLabels(count, multiplier);
}

function buildLabels(count, multiplier) {
  var labels = new Array(count);
  while (count--) labels[count] = formatLabel(count * multiplier);
  return labels;
}

function formatLabel(value) {
  if (value > 10e5) return (value / 10e5) + 'M'; // millions
  if (value > 10e2) return (value / 10e2) + 'K'; // thousands
  return value; // <= hundreds
}

function orderOfMagnitude(val) {
  var order = Math.floor(log10(val) + 0.000000001);
  return Math.pow(10, order);
}

After drawing it out on paper, the "desirable" labels seemed to follow a simple pattern:

1. Find the max value in the set.
2. Get the order of magnitude for it.
3. Multiply the order of magnitude by the number of ticks.
4. Iterate: If that previous calculation is greater than the max value, then use it. Otherwise, multiply the value times 2 and check. If not, try times 5. So the pattern is, 1, 2, 5.

This gives you labels that are like:

• 10, 20 (2 ticks)
• 20, 40
• 50, 100
• 100, 200
• 200, 400
• 500, 1000
• ...
• 10, 20, 30 (3 ticks)
• 20, 40, 60
• 50, 100, 150 (don't like this one too much but oh well)
• 100, 200, 300
• 10, 20, 30, 40 (4 ticks)
• ...

It seems like it can be improved, both in producing better quality "human readable" labels, and in using more optimized functionality, but don't quite see it yet. This works for now.

Would love to know if you find a better way!