2

I would like to find nearest "nice" tiling of "ruler" given rough number of tiles and range to display. To be more specific about "nice" the width of tiles should be like on money: 1,2,5,10,20... etc. Or more precisely 1*10eN, 2*10eN or 5.0*10eN where N is integer (=values like 0.1 are also valid).

Preferred language is C#.

For example if I wanted to display range from -1 to 12 and wanted roughly 3 tiles on ruler, the output of the algorithm would be 3 tiles, 10 units wide from value -10 (to 20).

In cause the algorithm would decide to take tile width 2 and values from -2 to 12, the number of tiles would be 6 which is worse approximation of 3 tiles than 3 tiles(for 1st option). Or if width was 5, and ruler from -5 to 15, the number if tiles would be 4 which is "further away" from 3 tiles than 3 tiles(for 1st option).

class Tiling {
 double width;
 double from;
 double count;
}

Tiling findTiling(double range_from, double range_to, double aprox_tiles)
{ /*???*/}

enter image description here

As real-world example, open your favourite image editor and look at legend of axes as you zoom - the numbers on ruler change but the total number of tiles of ruler on screen keep roughly the same. This problem is similar except the range(in case of image editor pixels of image from 0 to width/height) does not start from zero and the resolution can go below 1 unit (pixel).

wondra
  • 3,271
  • 3
  • 29
  • 48
  • 1
    I don't understand the problem statement. Can you please clarify? – Maria Ines Parnisari Dec 20 '15 at 18:54
  • @miparnisari Imagine you had plank to measure and task to find folding ruler of *n* parts. The problem is to find a folding ruler that has the closest number of parts to *n* that can measure the plank. Naturally, folding rulers have "nice" numbers on them. – wondra Dec 20 '15 at 19:01
  • Simplified, range has "two ends", you would "translate" the plank to 0 when measuring effectively reducing it to "one end" - you cant do that with range. – wondra Dec 20 '15 at 19:06
  • Is it me or is this completely incomprehensible? – m69's been on strike for years Dec 20 '15 at 20:14
  • 1
    @m69 I must admit, if you dont take your time to imagine the problem on a picture it might seem confusing - I just added image to save everybodys time, does that help you? – wondra Dec 20 '15 at 21:10
  • So to rephrase this, you are looking for an algo that decides a length of a tile so that a given number (`approx_tiles`) of tiles placed next to each other aggregate to a length bigger than a given length `range_to - range_from`. With the tile sizes limited to a given set of numbers. Is there also any limitation on what points should the tiles be placed to (e.g. tiles of size 2 only start at positions that are multiples of 2)? – Zdeněk Jelínek Dec 20 '15 at 21:44
  • @ZdeněkJelínek exactly, including the limitation. Just note to bigger than: bigger than on "both ends". For example range from -1 to 12 could be aggregated by 3 tiles of length 5 starting from -5, the sum is greater than 13, but it would not fully "cover" the range i.e. from 10 to 12 would not be covered. – wondra Dec 20 '15 at 21:55
  • Look at Incongruous answer here: http://stackoverflow.com/questions/8506881/nice-label-algorithm-for-charts-with-minimum-ticks – MBo Dec 21 '15 at 09:18

1 Answers1

2

Something like this should do it: divide the range by the preferred number of tiles. Take Log10 of this number and then modulo 1, and this tells you whether to use a multiple of 1, 2 or 5: 

0        ->  1
0.30103  ->  2
0.69897  ->  5
1        -> 10

This method suggests 4 tiles of size 5 for your example, instead of 3 tiles of size 10; you can tweak it further by changing the crossover values, if you prefer fewer tiles.

Code example in javascript (I don't speak C#): 

function findTiling(range_from, range_to, aprox_tiles) {
    var scale = Math.log((range_to - range_from) / aprox_tiles) / Math.LN10;
    var scale10 = Math.floor(scale);
    var scale125 = (scale + 100) % 1;
    if (scale125 < 0.150515) scale = 1       // 0
    else if (scale125 < 0.5) scale = 2       // 0.30103
    else if (scale125 < 0.849485) scale = 5  // 0.69897
    else scale = 10;                         // 1
    scale *= Math.pow(10, scale10);
    var from = Math.floor(range_from / scale) * scale;
    var to = Math.ceil(range_to / scale) * scale;
    return {width: scale, from: from, count: Math.round((to - from) / scale)};
}

var tiling = findTiling(-1, 12, 3);
document.write(tiling.width + " ; " + tiling.from + " ; " + tiling.count + "<BR>");
var tiling = findTiling(8, 88, 10);
document.write(tiling.width + " ; " + tiling.from + " ; " + tiling.count + "<BR>");
var tiling = findTiling(-100, 500, 3);
document.write(tiling.width + " ; " + tiling.from + " ; " + tiling.count + "<BR>");
var tiling = findTiling(-1, -0.9, 7);
document.write(tiling.width + " ; " + tiling.from + " ; " + tiling.count + "<BR>");
var tiling = findTiling(-1, -0.9, 8);
document.write(tiling.width + " ; " + tiling.from + " ; " + tiling.count + "<BR>");
m69's been on strike for years
  • 11,835
  • 3
  • 34
  • 57
  • Much better than my current iterative solution minimizing the error - it was a mess on ~50 lines. – wondra Dec 21 '15 at 11:46