Strategize Algorithm

[curran]

Related to https://github.com/leebyron/streamgraph/issues/3

The algorithm should find the maximum size possible, and position the label in the center of available space.

Prior art:

Stacked area label placement #2 by Noah Veltman

function getBestLabel(points) {

  var bbox = this.getBBox(),
      numValues = Math.ceil(x.invert(bbox.width + 20)),
      bestRange = -Infinity,
      bestPoint;

  for (var i = 1; i < points.length - numValues - 1; i++) {

    var set = points.slice(i, i + numValues),
        floor = d3.min(set, d => y(d[0])),
        ceiling = d3.max(set, d => y(d[1]));

    if (floor - ceiling > bbox.height + 20 && floor - ceiling > bestRange) {
      bestRange = floor - ceiling;
      bestPoint = [
        x(i + (numValues - 1) / 2),
        (floor + ceiling) / 2
      ];
    }
  }

  return bestPoint;
}

Streamgraph label positions by Noah Veltman

function getBestLabel(points) {
  var bbox = this.getBBox(),
      numValues = Math.ceil(x.invert(bbox.width + 20)),
      finder = findSpace(points, bbox, numValues);

  // Try to fit it inside, otherwise try to fit it above or below
  return finder() ||
    (points.top && finder(y.range()[1])) ||
    (points.bottom && finder(null, y.range()[0]));
}

function findSpace(points, bbox, numValues) {

  return function(top, bottom) {
    var bestRange = -Infinity,
      bestPoint,
      set,
      floor,
      ceiling,
      textY;

    // Could do this in linear time ¯\_(ツ)_/¯
    for (var i = 1; i < points.length - numValues - 1; i++) {
      set = points.slice(i, i + numValues);

      if (bottom != null) {
        floor = bottom;
        ceiling = d3.max(set, d => y(d[0]));
      } else if (top != null) {
        floor = d3.min(set, d => y(d[1]));
        ceiling = top;
      } else {
        floor = d3.min(set, d => y(d[0]));
        ceiling = d3.max(set, d => y(d[1]));
      }

      if (floor - ceiling > bbox.height + 20 && floor - ceiling > bestRange) {
        bestRange = floor - ceiling;
        if (bottom != null) {
          textY = ceiling + bbox.height / 2 + 10;
        } else if (top != null) {
          textY = floor - bbox.height / 2 - 10;
        } else {
          textY = (floor + ceiling) / 2;
        }
        bestPoint = [
          x(i + (numValues - 1) / 2),
          textY
        ];
      }
    }

    return bestPoint;
  };

I'd describe the problem as something like this: Given an aspect ratio for a rectangle, and a polygon bounded on the top and bottom by X-monotone curves, find the rectangle of that aspect ratio of maximum size that fits inside of the polygon.

Ideally the solution would also center the rectangle in the available space, but I'm not quite sure how to phrase that bit, geometrically speaking.

Algorithm sketch:

• Measure text to find aspect ratio
• Use Bisection method to search for the maximum scale within some epsilon, using the following function as a test:
  • Find the first instance of a rectangle with the given scale and aspect ratio.
• Find the best point to place a label of the maximum scale and aspect ratio

Note that the algorithm should handle timeseries data where intervals are not consistant, such as the data in Syrian Refugees by Settlement Type.

[curran]

Related work by @fil http://thebulletin.org/global-nuclear-power-database

[Fil]

The relevant code for my case was:

                var labels = series.map(function (d) {
                        var v = 4,
                            best = 0,
                            candidate = null;
                        for (var i = 0; i < d.length; i++) {
                            for (var j = d[i][0] + 2; j < d[i][1] - 2; j++) {
                                var score = 0;
                                for (var k = 1; k < d.length; k++) {
                                    if (!d[i + k] || !d[i - k] || d[i + k][0] > j - v || d[i + k][1] < j + v || d[i - k][0] > j - v || d[i - k][1] < j + v)
                                        break;
                                    score++;
                                }
                                score *= Math.sqrt(1 + j);
                                if (score >= best) {
                                    candidate = [i, j];
                                    best = score;
                                }
                            }
                        }
                        if (best > 1) {
                            return {
                                year: d[candidate[0]].data.year,
                                height: candidate[1],
                                label: d.key
                            };
                        }
                    })
                    .filter(function (d) {
                        return !!d;
                    });

[curran]

@Fil Thanks a ton for posting that! I will study it.

[curran]

More related work, from New York Times (HT @1wheel)

https://www.nytimes.com/interactive/2016/08/08/sports/olympics/history-olympic-dominance-charts.html?_r=0

[curran]

I think I've strategized enough. The algorithm is working, and the remaining task is to use Bisection method to get more precision with fewer iterations https://en.wikipedia.org/wiki/Bisection_method