veltman/README.md

## README.md

      
    Raw
  

              README.md
            
          
    A method for automatically finding the best eligible label position and size for a label that's going to go along a path inside of an area. This is potentially suitable for area charts where the area being labeled has a clear direction the text should "flow" in.
The basic approach is a crude one: test a center point at a certain font size, and work outwards to the left and right and disqualify it if you ever hit the side of the chart or run out of vertical space. If it fits, try a bigger size. If not, try a smaller size. Rinse/repeat until you've either found the largest size that will fit at that position or found that nothing will fit. Repeat with each possible center point until you've found the largest font size you can use, and where to put it.
Notes:

This adds a small optimization of disqualifying any candidate points that involve a sharp angle turn, because text turning at a sharp angle can be pretty hard to read.
Another optimization that's omitted for brevity is to first try to use a flat label if the area is blobby enough (e.g. if your area is basically a circle putting a label "along" its midline doesn't really make sense).
It might be a good idea to optimize for more than just fit - for example, it's probably better to have labels at similar x positions, or to have them read left-to-right from top to bottom rather than having to jump back and forth.
This is a pretty brute force approach and could probably be a lot smarter, but since the operations are all plain arithmetic, it really doesn't seem like a big deal. Even with the loops within loops, this example takes about 10 microseconds to check all the possible positions for an area. You could shave it down further by considering fewer font sizes or fewer x positions.
Measuring the available space vertically is a little bit off since the text might be rotated, but it seems to generally work out OK as long as the area doesn't contain crazy angles. This example tries to get a little more precise by calculating the rotated clearance.

See also:
Automatic label placement along a path #2

Streamgraph label positions #2

Stacked area label placement #2

  
## index.html
<!DOCTYPE html>
<meta charset="utf-8">
<link href="https://fonts.googleapis.com/css?family=Spectral" rel="stylesheet">
<style>
  text {
    font-family: 'Spectral', serif;
    font-size: 16px;
    fill: #222;
    text-anchor: middle;
    text-transform: uppercase;
    letter-spacing: 0.02em;
  }

  path {
    stroke: none;
  }

  .measurable {
    visibility: hidden;
  }

  .midline {
    fill: none;
    stroke: black;
    display: none;
  }

  .hidden {
    display: none;
  }
</style>
<svg width="960" height="500"></svg>
<script src="//d3js.org/d3.v4.min.js"></script>
<script>

const margin = { top: 10, right: 0, bottom: 10, left: 0 },
  chartWidth = 960 - margin.left - margin.right,
  chartHeight = 500 - margin.top - margin.bottom,
  random = d3.randomNormal(0, 3),
  fontSizeRange = [8, 64],
  turtles = ["Leonardo", "Donatello", "Raphael", "Michelangelo"],
  colors = ["#85cddf","#4ab8a7","#fe5f61","#f5c263"];

const svg = d3
  .select("svg")
  .append("g")
  .attr("transform", "translate(" + margin.left + " " + margin.top + ")");

const x = d3.scaleLinear().range([0, chartWidth]),
  y = d3.scaleLinear().range([chartHeight, 0]);

const series = svg
  .selectAll(".area")
  .data(turtles)
  .enter()
  .append("g")
  .attr("class", "area");

series
  .append("path")
  .attr("class", "area")
  .attr("fill", (d, i) => colors[i]);

series
  .append("path")
  .attr("class", "midline")
  .attr("id", (d, i) => "midline-" + i);

series
  .append("text")
  .attr("class", "measurable")
  .attr("dy", "0.35em")
  .text(d => d);

series
  .append("text")
  .attr("class", "along-path")
  .attr("dy", "0.35em")
  .append("textPath")
  .attr("xlink:href", (d, i) => "#midline-" + i)
  .text(d => d);

const stack = d3
  .stack()
  .keys(turtles)
  .order(d3.stackOrderInsideOut)
  .offset(d3.stackOffsetWiggle);

const line = d3.line().curve(d3.curveMonotoneX);

randomize();

function randomize() {
  const data = [];

  // Random-ish walk
  for (let i = 0; i < 12; i++) {
    data[i] = {};
    turtles.forEach(function(turtle) {
      data[i][turtle] = Math.max(0, random() + (i ? data[i - 1][turtle] : 10));
    });
  }

  let stacked = stack(data);

  x.domain([0, data.length - 1]);
  y.domain([
    d3.min(stacked.map(d => d3.min(d.map(p => p[0])))),
    d3.max(stacked.map(d => d3.max(d.map(p => p[1]))))
  ]);

  stacked = stacked.map(series =>
    series.map((p, i) => {
      let px = x(i),
        py1 = y(p[0]),
        py2 = y(p[1]);
      return {
        bottom: [px, py1],
        top: [px, py2],
        mid: [px, (py1 + py2) / 2],
        gap: py1 - py2
      };
    })
  );

  // Draw filled areas
  series
    .data(stacked)
    .select(".area")
    .attr("d", area =>
      [
        line(area.map(p => p.top)),
        line(area.map(p => p.bottom).reverse()).replace("M", "L"),
        "Z"
      ].join("")
    );

  // Update invisible midlines
  series.select(".midline").attr("d", area => line(area.map(p => p.mid)));

  // Position labels along midlines
  series.each(positionLabel);

  setTimeout(randomize, 750);
}

function positionLabel(points) {
  let area = d3.select(this),
    pathText = area.select(".along-path");

  let { width, height } = area
    .select(".measurable")
    .node()
    .getBBox();

  let distances = [],
    gaps = [];

  // Convert list of midpoints into a list of distances between them and their vertical gaps,
  // also interpolate the halfway point between each pair to get higher resolution
  points.forEach(function(point, i) {
    let distanceBefore = i ? distanceBetween(points[i - 1].mid, point.mid) : 0,
      gap = point.gap;

    if (i) {
      // Take this point off the table if it's a sharp turn
      if (i < points.length - 1 && sharpAngle(points[i - 1].mid, point.mid, points[i + 1].mid)) {
        gap = 0;
      }
      gaps.push((gaps[gaps.length - 1] + gap) / 2);
      distances.push(distanceBefore / 2);
    }
    gaps.push(gap);
    distances.push(distanceBefore / 2);
  });

  let { fontSize, offset } = getTextPathPosition(distances, gaps, width, height);

  // It fits!
  if (fontSize) {
    pathText
      .style("display", "block")
      .style("font-size", fontSize + "px")
      .select("textPath")
      .attr("startOffset", offset + "%");
    // It doesn't fit, hide it
  } else {
    pathText.style("display", "none");
  }
}

function getTextPathPosition(distances, gaps, width, height) {
  let bestPos, bestSize, bestMargin;

  for (let i = 1; i < distances.length - 1; i++) {
    let [min, max] = fontSizeRange,
        margin;

    // Binary search for the largest usable font size at center point i
    while (min <= max) {
      let size = Math.floor((min + max) / 2);

      // Text fits
      if (margin = testSize(size, i) > 0) {
        // If it's bigger than the previous winner, or same size with a bigger margin, new winner
        if (!bestSize || size > bestSize || (size === bestSize && margin >= bestMargin)) {
          bestSize = size;
          bestPos = i;
          bestMargin = margin;
        }
        // Try a larger font size
        min = size + 1;
      } else {
        // Try a smaller font size
        max = size - 1;
      }
    }
  }

  // Return the estimated startOffset and font size
  return bestSize
    ? {
        offset: 100 * d3.sum(distances.slice(0, bestPos + 1)) / d3.sum(distances),
        fontSize: bestSize
      }
    : {};

  // Test a given font size at a given center index
  function testSize(s, center) {
    let halfWidth = width * s / 32, // estimated half of text width at this size
      h = height * s / 16, // estimated text height at this size
      paddedHeight = h + Math.max(2, h / 9); // desired vertical clearance - at least 2px, more if it's big

    let minHeight = gaps[center],
      leftPos = center,
      left = 0,
      rightPos = center,
      right = 0;

    // Work left from the center, finding the minimum vertical clearance
    // Stop before the first two points to leave some padding on the end
    while (leftPos >= 2 && left < halfWidth) {
      left += distances[leftPos];
      leftPos--;
      minHeight = Math.min(gaps[leftPos], minHeight);
      // If there's not enough clearance, give up
      if (minHeight < paddedHeight) {
        break;
      }
    }

    // Work right from the center, finding the minimum vertical clearance
    // Stop before the last two points to leave some padding on the end
    while (minHeight >= paddedHeight && rightPos < distances.length - 2 && right < halfWidth) {
      right += distances[rightPos];
      rightPos++;
      minHeight = Math.min(gaps[rightPos], minHeight);
      // If there's not enough clearance, give up
      if (minHeight < paddedHeight) {
        break;
      }
    }

    // If we have room on all sides, return the remaining vertical margin
    if (left >= halfWidth && right >= halfWidth && minHeight >= paddedHeight) {
      return minHeight - h;
    }
    // Doesn't fit
    return 0;
  }
}

function distanceBetween(a, b) {
  let dx = a[0] - b[0],
    dy = a[1] - b[1];

  return Math.sqrt(dx * dx + dy * dy);
}

// Avoid excessively sharp angle turns in text
function sharpAngle(a, b, c) {
  let ab = Math.sqrt(Math.pow(b[0] - a[0], 2) + Math.pow(b[1] - a[1], 2)),
    bc = Math.sqrt(Math.pow(b[0] - c[0], 2) + Math.pow(b[1] - c[1], 2)),
    ac = Math.sqrt(Math.pow(c[0] - a[0], 2) + Math.pow(c[1] - a[1], 2)),
    angle = Math.abs(Math.acos((bc * bc + ab * ab - ac * ac) / (2 * bc * ab))) * 180 / Math.PI;

  return angle < 100 || angle > 260;
}
</script>

## preview.png

      
    Raw
  

              preview.png
            
          
## thumbnail.png

      
    Raw
  

              thumbnail.png
	<!DOCTYPE html>
	<meta charset="utf-8">
	<link href="https://fonts.googleapis.com/css?family=Spectral" rel="stylesheet">
	<style>
	text {
	font-family: 'Spectral', serif;
	font-size: 16px;
	fill: #222;
	text-anchor: middle;
	text-transform: uppercase;
	letter-spacing: 0.02em;
	}

	path {
	stroke: none;
	}

	.measurable {
	visibility: hidden;
	}

	.midline {
	fill: none;
	stroke: black;
	display: none;
	}

	.hidden {
	display: none;
	}
	</style>
	<svg width="960" height="500"></svg>
	<script src="//d3js.org/d3.v4.min.js"></script>
	<script>

	const margin = { top: 10, right: 0, bottom: 10, left: 0 },
	chartWidth = 960 - margin.left - margin.right,
	chartHeight = 500 - margin.top - margin.bottom,
	random = d3.randomNormal(0, 3),
	fontSizeRange = [8, 64],
	turtles = ["Leonardo", "Donatello", "Raphael", "Michelangelo"],
	colors = ["#85cddf","#4ab8a7","#fe5f61","#f5c263"];

	const svg = d3
	.select("svg")
	.append("g")
	.attr("transform", "translate(" + margin.left + " " + margin.top + ")");

	const x = d3.scaleLinear().range([0, chartWidth]),
	y = d3.scaleLinear().range([chartHeight, 0]);

	const series = svg
	.selectAll(".area")
	.data(turtles)
	.enter()
	.append("g")
	.attr("class", "area");

	series
	.append("path")
	.attr("class", "area")
	.attr("fill", (d, i) => colors[i]);

	series
	.append("path")
	.attr("class", "midline")
	.attr("id", (d, i) => "midline-" + i);

	series
	.append("text")
	.attr("class", "measurable")
	.attr("dy", "0.35em")
	.text(d => d);

	series
	.append("text")
	.attr("class", "along-path")
	.attr("dy", "0.35em")
	.append("textPath")
	.attr("xlink:href", (d, i) => "#midline-" + i)
	.text(d => d);

	const stack = d3
	.stack()
	.keys(turtles)
	.order(d3.stackOrderInsideOut)
	.offset(d3.stackOffsetWiggle);

	const line = d3.line().curve(d3.curveMonotoneX);

	randomize();

	function randomize() {
	const data = [];

	// Random-ish walk
	for (let i = 0; i < 12; i++) {
	data[i] = {};
	turtles.forEach(function(turtle) {
	data[i][turtle] = Math.max(0, random() + (i ? data[i - 1][turtle] : 10));
	});
	}

	let stacked = stack(data);

	x.domain([0, data.length - 1]);
	y.domain([
	d3.min(stacked.map(d => d3.min(d.map(p => p[0])))),
	d3.max(stacked.map(d => d3.max(d.map(p => p[1]))))
	]);

	stacked = stacked.map(series =>
	series.map((p, i) => {
	let px = x(i),
	py1 = y(p[0]),
	py2 = y(p[1]);
	return {
	bottom: [px, py1],
	top: [px, py2],
	mid: [px, (py1 + py2) / 2],
	gap: py1 - py2
	};
	})
	);

	// Draw filled areas
	series
	.data(stacked)
	.select(".area")
	.attr("d", area =>
	[
	line(area.map(p => p.top)),
	line(area.map(p => p.bottom).reverse()).replace("M", "L"),
	"Z"
	].join("")
	);

	// Update invisible midlines
	series.select(".midline").attr("d", area => line(area.map(p => p.mid)));

	// Position labels along midlines
	series.each(positionLabel);

	setTimeout(randomize, 750);
	}

	function positionLabel(points) {
	let area = d3.select(this),
	pathText = area.select(".along-path");

	let { width, height } = area
	.select(".measurable")
	.node()
	.getBBox();

	let distances = [],
	gaps = [];

	// Convert list of midpoints into a list of distances between them and their vertical gaps,
	// also interpolate the halfway point between each pair to get higher resolution
	points.forEach(function(point, i) {
	let distanceBefore = i ? distanceBetween(points[i - 1].mid, point.mid) : 0,
	gap = point.gap;

	if (i) {
	// Take this point off the table if it's a sharp turn
	if (i < points.length - 1 && sharpAngle(points[i - 1].mid, point.mid, points[i + 1].mid)) {
	gap = 0;
	}
	gaps.push((gaps[gaps.length - 1] + gap) / 2);
	distances.push(distanceBefore / 2);
	}
	gaps.push(gap);
	distances.push(distanceBefore / 2);
	});

	let { fontSize, offset } = getTextPathPosition(distances, gaps, width, height);

	// It fits!
	if (fontSize) {
	pathText
	.style("display", "block")
	.style("font-size", fontSize + "px")
	.select("textPath")
	.attr("startOffset", offset + "%");
	// It doesn't fit, hide it
	} else {
	pathText.style("display", "none");
	}
	}

	function getTextPathPosition(distances, gaps, width, height) {
	let bestPos, bestSize, bestMargin;

	for (let i = 1; i < distances.length - 1; i++) {
	let [min, max] = fontSizeRange,
	margin;

	// Binary search for the largest usable font size at center point i
	while (min <= max) {
	let size = Math.floor((min + max) / 2);

	// Text fits
	if (margin = testSize(size, i) > 0) {
	// If it's bigger than the previous winner, or same size with a bigger margin, new winner
	if (!bestSize \|\| size > bestSize \|\| (size === bestSize && margin >= bestMargin)) {
	bestSize = size;
	bestPos = i;
	bestMargin = margin;
	}
	// Try a larger font size
	min = size + 1;
	} else {
	// Try a smaller font size
	max = size - 1;
	}
	}
	}

	// Return the estimated startOffset and font size
	return bestSize
	? {
	offset: 100 * d3.sum(distances.slice(0, bestPos + 1)) / d3.sum(distances),
	fontSize: bestSize
	}
	: {};

	// Test a given font size at a given center index
	function testSize(s, center) {
	let halfWidth = width * s / 32, // estimated half of text width at this size
	h = height * s / 16, // estimated text height at this size
	paddedHeight = h + Math.max(2, h / 9); // desired vertical clearance - at least 2px, more if it's big

	let minHeight = gaps[center],
	leftPos = center,
	left = 0,
	rightPos = center,
	right = 0;

	// Work left from the center, finding the minimum vertical clearance
	// Stop before the first two points to leave some padding on the end
	while (leftPos >= 2 && left < halfWidth) {
	left += distances[leftPos];
	leftPos--;
	minHeight = Math.min(gaps[leftPos], minHeight);
	// If there's not enough clearance, give up
	if (minHeight < paddedHeight) {
	break;
	}
	}

	// Work right from the center, finding the minimum vertical clearance
	// Stop before the last two points to leave some padding on the end
	while (minHeight >= paddedHeight && rightPos < distances.length - 2 && right < halfWidth) {
	right += distances[rightPos];
	rightPos++;
	minHeight = Math.min(gaps[rightPos], minHeight);
	// If there's not enough clearance, give up
	if (minHeight < paddedHeight) {
	break;
	}
	}

	// If we have room on all sides, return the remaining vertical margin
	if (left >= halfWidth && right >= halfWidth && minHeight >= paddedHeight) {
	return minHeight - h;
	}
	// Doesn't fit
	return 0;
	}
	}

	function distanceBetween(a, b) {
	let dx = a[0] - b[0],
	dy = a[1] - b[1];

	return Math.sqrt(dx * dx + dy * dy);
	}

	// Avoid excessively sharp angle turns in text
	function sharpAngle(a, b, c) {
	let ab = Math.sqrt(Math.pow(b[0] - a[0], 2) + Math.pow(b[1] - a[1], 2)),
	bc = Math.sqrt(Math.pow(b[0] - c[0], 2) + Math.pow(b[1] - c[1], 2)),
	ac = Math.sqrt(Math.pow(c[0] - a[0], 2) + Math.pow(c[1] - a[1], 2)),
	angle = Math.abs(Math.acos((bc * bc + ab * ab - ac * ac) / (2 * bc * ab))) * 180 / Math.PI;

	return angle < 100 \|\| angle > 260;
	}
	</script>